輾轉相除法求2數最大公因數的函式
int
gcd(int
a, int
b)
{
int
temp = 1;
while
(temp != 0)
{
temp
= a % b;
a
= b;
b
= temp;
}
return
a;
}
假設有2數
703
及 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數大小的迴圈。
沒有留言:
張貼留言