申論題 - 阿摩線上測驗

申論題資訊

試卷：99年 - 099年地方四等_資訊處理#31651
科目：程式設計
年份：99年
排序：0

申論題內容

三、請用 C 語言，設計一個函式 int gcd(int x, int y)。gcd 函式會回傳整數 x 及 y 的「最大公因數」，請用遞迴（recursive）的方式來完成 gcd 函式。（15 分）

詳解 (共 2 筆)

詳解提供者：hchungw

在C語言中，計算兩個整數的最大公因數（Greatest Common Divisor, GCD）通常使用輾轉相除法，也稱為歐幾裡得演算法。以下是一個遞迴方式實現的gcd函數：

#include <stdio.h>

int gcd(int x, int y) {
if (y == 0)
return x;
else
return gcd(y, x % y);
}

int main() {
int num1 = 28;
int num2 = 35;
printf("The GCD of %d and %d is %d.\n", num1, num2, gcd(num1, num2));
return 0;
}
在這個gcd函數中：

當y變成0時，遞迴終止，返回x作為結果。
如果y不為0，函式呼叫自身，新的參數是y和x % y（x除以y的餘數）。
遞迴會一直進行，直到y等於0，此時的x就是兩個數的最大公因數。

詳解提供者：Triple w.

遞迴計算 gcd(48, 18)
遞迴計算 gcd(18, 12)
遞迴計算 gcd(12, 6)
遞迴計算 gcd(6, 0)
最大公因數（遞迴）: 6
非遞迴計算 gcd(48, 18)
當前被除數: 48, 除數: 18
當前被除數: 18, 除數: 12
當前被除數: 12, 除數: 6
最大公因數（非遞迴）: 6