靈感編程：最大公約數算法解析
給定兩個正整數，求其最大公約數，相信這是每一個寫代碼的同學絕壁遇見過的練習，當然解法也非常多，下面先給出一個沒有經過任何算法處理的程序：
- public static int getResult(int a,int b){
- int max = (a>b)?a:b;
- int result=0;
- for(int i = 1;i < max;i++){
- if(a%i == 0 && b%i == 0){
- result=i;
- }
- }
- return result;
- }
這樣當然是可以解出來的，但是要循環遍歷其中較大的正整數，如果兩個數量都非常大的話，效率是非常低的，每當遇到效率低下的程序，我們必然會想到優化，算法優化總是很靠譜的一種方法。下面就列出幾種添加算法的方法來解決最大公約數的問題。
解法一：
輾轉相除法，假設求正整數 num1,num2 的最大公約數，假設f(x,y)為兩者的最大公約數,取 k = x / y (取整)，b = x % y (取余)；則 x = k y + b ;那么能同時被x ，y整除的數必然也同時能被 b , y 整除，能被b ， y整除的數也能同時被x，y整除，也就是說，x，y的最大公約數就是b，y的最大公約數，則有 f (x , y) = f(y , x%y) (x>=y>0),這樣遞歸運算，比如
f(42,30) = f(30,12) = f(12 , 6) = f(6,0) = 6; 這樣將運算次數直接降低了很多。下面附上代碼：
- int result = ((y == 0) ? x : gcd(y, x % y));
- return result;
- }
解法二：
解法一雖然很好的解決了求公約數的問題，但是算法中包含有除法，在計算機中除法的開銷是很大的，能不能不用除法呢。可以這樣考慮，一個數能被x , y整出，必然也能被x-y，y整出，也就是一個數被x，y整出是這個數被x-y，y整出的充分必要條件。那么f(x, y) = f(x-y , y);這樣計算的話，就可以把大整數之間的取模運算轉換為大整數之間的減法運算。由于f（x，y）= f（y，x），為了避免求出一個正數和一個負數的最大公約數，要靈活運用f（x，y）= f（y，x）,迭代進行，直到一方為0；比如：
f(42,30) = f(30,12) = f(18 , 12)= f(12 , 6) = f(6,6)= f(6 , 0) = 6;這樣運算跟上面的方法比起來，優化了大數據取模的問題，但是運算次數會增大，代碼如下：
private static int gcd(int x, int y) {
- if (y == 0) {
- return x;
- }
- if (x < y) {
- return gcd(y, x);
- } else {
- return gcd(x - y, y);
- }
- }
解法三：
解法一的不足之處在于復雜的大數據除法運算，解法二雖然干掉了大數據的除法運算，但是增加了操作次數。兩種方法都不是非常的完美，那么我們就用第三種方法來解決，第三種方法使用的二進制方案，估計很多同學看到01100100就要放棄了，千萬不要，其實這東西不難。
對于x，y來說，有x=k * x1,y = k * y1 ,則f(x ,y) = f(k * x1,k * y1) = k * f(x1 ,y1);此為一。
另外，如果 x = p * x1,且p為素數，y%p != 0,則f（x ，y）= f(p * x1, y) = f(x1 ,y);此為二。
由一和二兩個公式，我們可以計算公約數了：
設p=2：
假設x，y都是偶數：f（x，y）= 2f(x»1,y»1);
假設x是偶數，y是奇數：f(x,y) = f(x»1,y);
假設x是奇數，y是偶數：f(x,y) = f(x,y»1);
假設x，y都是奇數：f(x,y) = f(y,x-y);—這是根據解法二中推出來的
下面還以42 和 30 為例：
f(42,30) = f(101010,11110) = 2f(10101,1111) = 2f(1111,110)=2 * f(1111,11) = 2 f (1100,11) = 2f(110,11)=2 f(11,11) = 2 f(0,11) = 2 3=6
括號中均為二進制表達，這樣最壞的情況下，復雜度也就是log 2(max(x,y));—-2是底數，尼瑪，這格式弄不出來。
下面附上代碼：
- if (x < y) {
- return gcd(y, x);
- }
- if (y == 0) {
- return x;
- }
- if (isEven(x)) {
- if (isEven(y)) {
- // x，y都為偶數，f(x,y)=2*f(x/2,y/2)
- return gcd(x >> 1, y >> 1) << 1;
- } else {
- // x偶數,y奇數，f(x,y)=f(x/2,y)
- return gcd(x >> 1, y);
- }
- } else {
- if (isEven(y)) {
- // x奇數，y偶數，f(x,y)=2*f(x,y/2)
- return gcd(x, y >> 1);
- } else {
- // x，y都為奇數，f(x,y)=f(x-y,y)
- return gcd(x - y, y);
- }
- }
- }
- public static boolean isEven(int x) {
- return (x % 2 == 0) ? true : false;
- }
以前根本沒有想過這么些玩意，第一次看算法，頓時感覺高大上啊，不過的確，看到這樣解決以前常用來解決的公約數問題，的確眼前一亮啊，希望大家多多給意見哦~
