網頁

2015年3月18日 星期三

為什麼使用輾轉相除法來求2整數之最大公因數,不必考慮2數大小的順序?

輾轉相除法求2數最大公因數的函式

int gcd(int a, int b)
{
int temp = 1;
while (temp != 0)
{
temp = a % b;
a = b;
b = temp;
}
return a;
}

假設有2703 407
先看看,如果輸入大小順序為 703, 407  (a > b)


a = 703;
b = 407;
temp = 1;

其在迴圈執行的過程為 :

round 1 :
temp = a % b; 703 % 407 = 296;
a = b; a = 407;
b = temp; b = 296

round 2 :
temp = a % b; 407 % 296 = 111;
a = b; a = 296;
b = temp; b = 111

round 3 :
temp = a % b = 296 % 111 = 74;
a = b; → a = 111
b = temp; b = 74

round 4 :
temp = a % b = 111 % 74 = 37;
a = b; → a = 74
b = temp; b = 37

round 5 :
temp = a % b = 74 % 37 = 0;
a = b; → a = 37
b = temp; → b = 0
此時 temp = 0,因此退出迴圈,最後回傳 a,即為2數之最大公因數。

再看看,如果輸入大小順序為 407, 703 (a < b)

a = 407;
b = 703;
temp = 1;

其在迴圈執行的過程為 :
round 1 :
temp = a % b; 407 % 703 =407;
a = b; a = 703
b = temp; b = 407

round 2 :
temp = a % b = 703 % 407 = 296;
a = b; a = 407;
b = temp; b = 296

round 3 :
temp = a % b = 407 % 296 = 111;
a = b; → a = 296
b = temp; b = 111

round 4 :
temp = a % b = 296 % 111 = 74;
a = b; → a = 111
b = temp; b = 74

round 5 :
temp = a % b = 111 % 74 = 37;
a = b; → a = 74
b = temp; b = 37

round 6 :
temp = a % b = 74 % 37 = 0;
a = b; → a = 37
b = temp; b = 0
此時 temp = 0,因此退出迴圈,最後回傳 a,即為2數之最大公因數。


        從以上過程中可以發現,因為程式碼在取得餘數後,便交換2數,所以無論2數的大小先後順序為何,並不會讓答案有所差別,只有差在多跑一次那交換2數大小的迴圈。

沒有留言:

張貼留言