本文實(shí)例講述了Java求解兩個(gè)非負(fù)整數(shù)最大公約數(shù)算法。分享給大家供大家參考，具體如下：

代碼功能：

1.Java實(shí)現(xiàn)（完整源碼附測(cè)試用例）；
2.求解兩個(gè)非負(fù)整數(shù)p，q（p>=q)的最大公約數(shù)；
3.循環(huán)法 以及 遞歸法兩種求解思路；

完整源碼：

/* 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);
 }
}

運(yùn)行截圖：

代碼解釋：

循環(huán)法 gcd1(p,q)

自然語(yǔ)言描述 ：循環(huán)法求解兩個(gè)非負(fù)整數(shù)p，q（p>=q）的最大公約數(shù)，即求解q的公約數(shù)中為p的公約數(shù)的最大值。令d（被除數(shù)）從p開始遞減（遞減step = 1）d始終為“即將滿足條件的最大值”，當(dāng)d滿足條件（既可以被p整除又可以被p整除時(shí)），d即p與q的公約數(shù)，d即為p、q的最大公約數(shù)；

遞歸法 gcd2(p,q)

自然語(yǔ)言描述： 遞歸法求解兩個(gè)非負(fù)整數(shù)p，q（p>=q）的最大公約數(shù) ，當(dāng)q等于0時(shí)，最大公約數(shù)為p；否則，對(duì)p、q取余得r=p%q，p、q的最大公約數(shù)即為q、r的最大公約數(shù)；

代碼心得：

關(guān)于循環(huán)法，一開始我想到的是，寫一個(gè)求解公約數(shù)的方法、用整型數(shù)組存儲(chǔ)一個(gè)非負(fù)整數(shù)的全部公約數(shù)，然后比較找出p、q中共同的那個(gè)最大的公約數(shù)也就是兩個(gè)數(shù)的最大公約數(shù)了，后來(lái)想想，既然是求最大，那么就直接從后往前遞減豈不是更省事兒，從后往前遞減就可以保證這個(gè)數(shù)一直是當(dāng)前最大，因?yàn)楸人蟮募一锒疾环蠗l件（能同時(shí)被p、q整除）被淘汰掉了啦，就免去了最初需要的找最大這個(gè)麻煩，雖然求最大值方法多多，但是如果自己已經(jīng)或者原本就是就不需要去證明和尋找了哈哈，怎么感覺有點(diǎn)在說哲學(xué) ；

關(guān)于遞歸法，我能依靠我的直覺完全理解的還只有那句p、q的最大公約數(shù)就是q、r（r=p%q）的最大公約數(shù)這個(gè)環(huán)的開始，但是還是不太理解環(huán)的結(jié)束條件 q為0，返回p;

雖然是很簡(jiǎn)單的求解最大公約數(shù)算法，但是非要用兩種思路來(lái)寫一下，主要還是為了再感受一下我不是很熟悉的遞歸法，以前看求解漢諾塔和斐波那契數(shù)的遞歸算法那明白白的公式亮在那里，就在感慨，這完全就是數(shù)學(xué)啊！今天學(xué)習(xí)到的這個(gè)，感觸居然比那時(shí)候還要震撼，不知道發(fā)生了什么問題奇妙地就解決了。我到時(shí)沒太在意什么內(nèi)存啊、效率之類的指標(biāo)，只是覺得能想到這個(gè)的家伙真的太聰明，對(duì)他們而言計(jì)算機(jī)也好、編程語(yǔ)言也好，真正做到了只是解決問題的工具。有人說，遞歸是讓人腦去思考讓計(jì)算機(jī)去計(jì)算的算法，感覺真的是很貼切的說法呢。

參考資料

圖靈程序設(shè)計(jì)叢書:算法(第4版) 塞奇威克 (Robert Sedgewick) (作者), 韋恩 (Kevin Wayne) (作者), 謝路云 (譯者)

更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點(diǎn)技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》

希望本文所述對(duì)大家java程序設(shè)計(jì)有所幫助。

最新評(píng)論