Java如何求解兩個非負整數最大公約數算法

這篇文章主要為大家展示了“Java如何求解兩個非負整數最大公約數算法”，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“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;

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

以上是“Java如何求解兩個非負整數最大公約數算法”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！