程式設計之美---最大公約數問題

該文出自于程式設計之美中關于最大公約數問題一章。

任意給定兩個數字，得到其最大公約數 GCD（greatest common divisor）,如果兩個數字都很大怎麼解決。

分析：最大公約數早在公元前300年，歐幾裡得的《幾何原本》裡就提出了一個高效率算法---輾轉相除法。

解法一：

假設f(x,y)表示x,y的最大公約數，取k=x/y,b=x%y，則x=ky+b，如果一個數字能同時整除x,y，那麼必能夠同時整除b,y；而能夠同時整除b,y的數必能夠同時整除x,y,即x,y的公約數與b,y的公約數是相同的，其最大公約數也是相同的，則必有f(x,y)=f(y,x%y)(x>=y>0)，進而把兩個數字的最大公約數轉化為求兩個更小數字的最大公約數，直到其中一個數字為0，剩下的另一個數字就是兩者最大的公約數。

例如： f(42,30) = f(30,12) = f(12,6) = f(6,0) = 6

代碼如下：

解法二：

由于輾轉相除法中存在一個最大的問題是，取模運算（其中用到了除法運算）是非常昂貴的開銷，成為了算法的瓶頸。根據解法一的思路分析，假設一個數能夠同時整除x,y，則必能夠同時整除x-y,y；而同時能夠整除x-y,y的數字也必能夠同時整除x,y，即x,y的公約數與x-y,y的公約數相同，其最大公約數也是相同的 即：f(x,y) = f(x-y,y)。這樣做就不需要進行大量的去摸運算，而轉化為減法運算。

例如：f(42,30) = f(30,12) = f(12,18) = f(12,6) = f(6,6,)=f(6,0) = 6

<a></a>

解法三：

解法一處理大整數整除問題比較複雜，解法二處理雖然将大整數問題除法轉換為減法運算，降低了複雜度，但是他的問題在于減法疊代次數太多了。最好的方法就是解法一和解法二結合使用。

分析: 對于 y和x來說，如果y = k*y1, x = k*x1。那麼有 f(y,x)=k*(y1,x1)。另外，如果x = p*x1,假設p是素數，且y%p!=0(即y不能夠被p整除)，那麼f(x,y)=f(p*x1,y)=f(x1,y);根據以上兩點，我們可以對算法進行改進，最簡單的就是取素數2，因為對于素數2同時可以轉化為移位運算，避免大整數除法。

取p = 2;

若：x,y均為偶數， f(x,y) = 2*f(x/2,y/2)=2*f(x&gt;&gt;1,y&gt;&gt;1)

若：x為偶數，y為奇數，f(x,y)=f(x/2,y) = f(x&gt;&gt;1,y);

若：x為奇數，y為偶數，f(x,y)=f(x/2,y) = f(x,y&gt;&gt;1);

若：x,y均為奇數，f(x,y)=f(y,x-y),那麼就存在f(x,y)=f(y,x-y)之後，(x-y)是一個偶數，下一步一定會有除以2的操作了。

是以這樣的複雜度為 O(log2(max(x,y)));

例如：

f(42,30) = f(1010102,111102)

　　　　  =2*f(101012,11112)

　　　　  =2*f(11112,1102)

　　　　  =2*f(11112,112)

　　　　  =2*f(11002,112)

 　　　　 =2*f(112,112)

              =2*f(02,112)

　　　　　= 2*112

　　　　   =6

本文轉自NewPanderKing51CTO部落格，原文連結：http://www.cnblogs.com/newpanderking/p/3953223.html ，如需轉載請自行聯系原作者