本文實例講述了Java求解兩個非負整數最大公約數算法。分享給大家供大家參考，具體如下：
代碼功能：
1.Java實現（完整源碼附測試用例）；
2.求解兩個非負整數p，q（p>=q)的最大公約數；
3.循環法以及遞歸法兩種求解思路；
完整源碼：
/* GCD:Greateast Common Divisor */public class GCD{ public static void main(String args[]){ /* Test Case */ int p = 32; int q = 24; System.out.println("The greatest divisior of "+p+" and "+q+" is /n"+ "[ gcd1 ] : "+gcd1(p,q)+"/n"+"[ gcd2 ] : "+ gcd2(p,q)); } // (q % gcd ==0 AND p% gcd ==0 [gcd from q to 1]) public static int gcd1(int p,int q){ int gcd=1; int d=q; while(d>0){ d--; if(q%d==0 && p%d==0){ gcd = d; break; } } return gcd; } // gcd(p,q)=gcd(q,p%q)[if q=0,gcd=p] public static int gcd2(int p,int q){ if(q==0) return p; int r = p%q; //System.out.println("("+q+","+r+")"); return gcd2(q,r); }}運行截圖：
代碼解釋：
循環法gcd1(p,q)
自然語言描述：循環法求解兩個非負整數p，q（p>=q）的最大公約數，即求解q的公約數中為p的公約數的最大值。令d（被除數）從p開始遞減（遞減step = 1）d始終為“即將滿足條件的最大值”，當d滿足條件（既可以被p整除又可以被p整除時），d即p與q的公約數，d即為p、q的最大公約數；
遞歸法gcd2(p,q)
自然語言描述： 遞歸法求解兩個非負整數p，q（p>=q）的最大公約數，當q等於0時，最大公約數為p；否則，對p、q取餘得r=p%q，p、q的最大公約數即為q、r的最大公約數；
代碼心得：
關於循環法，一開始我想到的是，寫一個求解公約數的方法、用整型數組存儲一個非負整數的全部公約數，然後比較找出p、q中共同的那個最大的公約數也就是兩個數的最大公約數了，後來想想，既然是求最大，那麼就直接從後往前遞減豈不是更省事兒，從後往前遞減就可以保證這個數一直是當前最大，因為比它大的傢伙都不符合條件（能同時被p、q整除）被淘汰掉了啦，就免去了最初需要的找最大這個麻煩，雖然求最大值方法多多，但是如果自己已經或者原本就是就不需要去證明和尋找了哈哈，怎麼感覺有點在說哲學；
關於遞歸法，我能依靠我的直覺完全理解的還只有那句p、q的最大公約數就是q、r（r=p%q）的最大公約數這個環的開始，但是還是不太理解環的結束條件q為0，返回p;
雖然是很簡單的求解最大公約數算法，但是非要用兩種思路來寫一下，主要還是為了再感受一下我不是很熟悉的遞歸法，以前看求解漢諾塔和斐波那契數的遞歸算法那明白白的公式亮在那裡，就在感慨，這完全就是數學啊！今天學習到的這個，感觸居然比那時候還要震撼，不知道發生了什麼問題奇妙地就解決了。我到時沒太在意什麼內存啊、效率之類的指標，只是覺得能想到這個的傢伙真的太聰明，對他們而言計算機也好、編程語言也好，真正做到了只是解決問題的工具。有人說，遞歸是讓人腦去思考讓計算機去計算的算法，感覺真的是很貼切的說法呢。
參考資料
圖靈程序設計叢書:算法(第4版)塞奇威克(Robert Sedgewick) (作者), 韋恩(Kevin Wayne) (作者), 謝路雲(譯者)
更多關於java算法相關內容感興趣的讀者可查看本站專題：《Java數據結構與算法教程》、《Java操作DOM節點技巧總結》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》
希望本文所述對大家java程序設計有所幫助。