[C/C++] 最大公因數 - GCD (greatest common divisor)

最大公因數 - GCD

最近喵在寫演算法的時候, 偶然發現這最大公因數還蠻好用的

但在說這之前

我們還是來複習一下最大公因數

定義:

    兩個或多個整數共同具有的最大因數 (引用自wiki - 最大公因數)

簡單的說呢, 用兩個整數 a, b 為例子

如果存在一個 c 使得

a = p * c

b = q * c

而不存在任何一個數字比 c 大

則 c 即為最大公因數

恩...

恩.......

感覺應該不太複雜, 大致上可以理解的喵~

根據以上的這個說明

我們可以寫出以下這個程式

1 2 3 4 5 6 7 8

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

是不是有點跳太快了~ 別急
讓喵來一步步的推導

推導 - 初心

一開始看到這個最大公因數, 我們不仿把焦點先放在公因數上面

假設兩數分別為 a, b

則存在一個公因數c可以使得

a = p * c
b = q * c

要滿足上述式子的公因數可以有好幾個, 但最小的很明顯, 就是 c = 1

但為了要求得最大公因數, 因此我們要強制的讓 p, q兩個除了 c 以外沒有其他的公因數

如果p,q有其他公因數 c', 那我們可以把c'提出來跟 c 一起結合成為新的 c

接著我們試著把兩個數字相減看看

d = a - b = (p * c) - (q * c) = (p - q) * c

這時候~ 可以看出一個現象, 那就是 d 也是 c的倍數

d = r * c , r = (p - q)

現在我們從兩個數字(a,b)變成三個數字 (a, b, d)
可以肯定的是 d 應該是比 a or b 還小
==> 那如果拿a, b當中比較小的出來, 在跟d互減, 越減越小
最後會出現什麼狀況?

記得當中的 p and q 兩個整數
其中我們強置地讓數字較大者減去數字較小者~
這樣減完之後最小的一個數字應該就是0
此時 p = q = 1  (因為最大公因數的時候, 我們已經把 p and q當中有共同因數的部分提出了)


根據以上推導, 可以得出一個初心版本的gcd
初始條件, a and b
結束條件 a - b = 0

1 2 3 4 5 6 7 8 9

int gcd_draft(int a, int b) { int big = a > b ? a : b; int small = a > b ? b : a; int diff = big - small; if (diff > 0) { return gcd_draft(diff, small); } return big; }

推導 - 進階

熟悉了初心版本之後, 仔細推敲會發現, 其實兩數相減, 如果一個數字大另外一個數字很多,
那就會一直重複著 a - b, 最後得到一個 d = (a - b) <  b, 其實這就相當於 d = a % b

因此進階版本就是直接取餘數得到答案

以下貼上整個程式碼

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

#include <stdio.h> int gcd ( int a, int b ) { int c; while ( a != 0 ) { c = a; a = b%a; b = c; } return b; } int gcd_draft(int a, int b) { int big = a > b ? a : b; int small = a > b ? b : a; int diff = big - small; if (diff > 0) { return gcd_draft(diff, small); } return big; } int main() { int a = 30; int b = 21; printf("GCD of %d, %d is %d\n", a, b, gcd(a,b)); printf("GCD_Draft of %d, %d is %d\n", a, b, gcd_draft(a,b)); return 0; }