Zerojudge a024. 最大公因數(GCD) C++多種解法（內建函數遞迴迴圈）題解

Jul 12, 2024

法一內建函數，最方便

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
  int a, b;
  cin >> a >> b;

  int gcd = __gcd(a, b);
  cout << gcd << endl;

  return 0;
}

此程式碼首先包含了必要的頭文件 <iostream> 和 <algorithm>。<iostream> 頭文件用於輸入輸出，<algorithm> 頭文件提供了 __gcd() 函數來計算兩個整數的最大公因數。

在 main() 函數中，首先使用 cin 語句從標準輸入讀取兩個整數 a 和 b。然後，使用 __gcd() 函數計算 a 和 b 的最大公因數，並將結果存儲在變量 gcd 中。最後，使用 cout 語句將 gcd 的值輸出到標準輸出。

以下是一些注意事項：

程式碼假設輸入的兩個整數是有效的，即它們都大於 0 且小於 2^31。如果輸入的整數不符合此條件，程式碼可能會產生錯誤結果。
程式碼使用 __gcd() 函數來計算最大公因數。__gcd() 函數是 C++ 標準函式庫中提供的函數，它使用歐幾里得算法來計算兩個整數的最大公因數。

法二遞迴函數，可讀性高

int gcd(int a, int b) {
  if (b == 0) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}

int main() {
  int a, b;
  cin >> a >> b;

  int gcd = gcd(a, b);
  cout << gcd << endl;

  return 0;
}

此程式碼使用遞迴函數 gcd() 來計算最大公因數。函數 gcd() 的第一個參數是較大的整數，第二個參數是較小的整數。函數的基線情況是當第二個參數為 0 時，此時返回第一個參數。否則，函數將遞迴調用自身，使用第二個參數作為第一個參數，並使用第一個參數模第二個參數的結果作為第二個參數。

以下是此版本的程式碼的優點：

程式碼比使用 __gcd() 函數的版本更具可讀性。

但是，遞迴函數也有一些缺點：

遞迴函數可能會導致堆棧溢出，如果輸入整數非常大。
遞迴函數可能比非遞歸版本更慢。

第二種算法的 gcd 遞迴部分使用了歐幾里得算法來計算兩個整數的最大公因數。歐幾里得算法是一種古老的算法，其基本思想是：

兩個整數的最大公因數等於它們的較小公倍數的除數。

在 gcd 遞迴函數中，首先檢查第二個參數是否為 0。如果為 0，則第一個參數就是兩個整數的最大公因數，函數直接回傳第一個參數。否則，函數將遞迴呼叫自身，使用第二個參數作為第一個參數，並使用第一個參數模第二個參數的結果作為第二個參數。

具體來說，函數的遞迴呼叫可以理解為以下步驟：

將較大的整數（第一個參數）除以較小的整數（第二個參數），得到餘數。
將餘數作為新的第二個參數，將原來的第二個參數（較小的整數）作為新的第一個參數。
遞歸調用 gcd 函數，計算新的第一個參數和新的第二個參數的最大公因數。
函數返回遞迴呼叫得到的最大公因數。

例如，假設我們要計算 48 和 18 的最大公因數。

首先，將 48 除以 18，得到餘數 12。
然後，將 12 作為新的第二個參數，將 18 作為新的第一個參數。
遞歸調用 gcd 函數，計算 18 和 12 的最大公因數。
函數返回遞迴呼叫得到的最大公因數 6。

因此，48 和 18 的最大公因數是 6。

遞迴演算法的優點是簡潔易懂，但缺點是可能導致堆疊溢位。在實際應用中，如果輸入整數非常大，可以使用非遞迴版本的歐幾里得算法來避免堆疊溢位。

法三迴圈法，效能最好

// (3ms, 324KB)
#include <iostream>

using namespace std;

int main() {
  int a, b;
  cin >> a >> b;

  while (b != 0) {
    int temp = a % b;
    a = b;
    b = temp;
  }

  cout << a << endl;

  return 0;
}

程式碼說明：

首先，我們包含 <iostream> 標頭檔，以使用 cin 和 cout 函數進行輸入和輸出。
然後，我們定義兩個整數變數 a 和 b 來存儲輸入的兩個整數。
接下來，我們使用歐幾里得算法來計算最大公因數。歐幾里得算法是一種遞歸算法，但我們可以使用迴圈來實現。該算法的思路是：不斷將較大的數除以較小的數，直到較小的數為 0。此時，較大的數即為最大公因數。
在迴圈中，我們首先使用 a % b 運算子來求得 a 除以 b 的餘數。然後，我們將 a 的值賦給 b，將 b 的值賦給 temp。這樣，在下一輪迴圈中，我們將使用較小的數（temp）來除以較大的數（a）。
補充說明，兩數的交換
```
int temp = a % b; 
a = b;
b = temp;
```
1. 程式碼片段的作用

這段程式碼的作用是將兩個整數變數 a 和 b 的值進行交換。

2. 程式碼片段的詳細解釋
- int temp = a % b;
這行程式碼首先將 a 除以 b 的餘數存儲在變數 temp 中。例如，如果 a 為 18，b 為 6，那麼這行程式碼將把 0 存儲在 temp 中。
- a = b;
這行程式碼將 b 的值賦給 a。例如，如果 b 為 6，那麼這行程式碼將把 6 存儲在 a 中。
- b = temp;
這行程式碼將 temp 的值賦給 b。例如，如果 temp 為 0，那麼這行程式碼將把 0 存儲在 b 中。

3. 程式碼片段的執行示例

假設 a 的初始值為 18，b 的初始值為 6。那麼，這段程式碼將執行以下步驟：
1. 將 a 除以 b 的餘數存儲在 temp 中。在這個例子中，temp 的值為 0。
2. 將 b 的值賦給 a。現在，a 的值為 6。
3. 將 temp 的值賦給 b。現在，b 的值為 0。
因此，在執行這段程式碼之後，a 的值為 6，b 的值為 0。
當 b 為 0 時，迴圈結束。此時，a 的值即為最大公因數。
最後，我們使用 cout 函數輸出最大公因數。

以下是程式碼的輸入輸出範例：

輸入：
18 36

輸出：
6

在這個範例中，輸入的兩個整數是 18 和 36，它們的最大公因數是 6。

法一 內建函數，最方便

法二 遞迴函數，可讀性高

法三 迴圈法，效能最好

法一內建函數，最方便

法二遞迴函數，可讀性高

法三迴圈法，效能最好