D奈老師的部落格

這個問題我認為原理非常的簡單...我在學Java的第一週就可以把他做出來
不過後來時間久了就忘記要把這個問題的解法丟上來

趁著現在比較有空的時間把教學簡單的打一下


首先從兩個整數的最大公因數開始
整數的最大公因數就是能夠同時整除他們的最大整數
求最大公因數的方法有很多種，其中一種方法叫做輾轉相除法
我們直接拿30跟18這兩個整數做例子
30/18=1餘12
18/12=1餘6
12/6=2

由於6整除了，所以30跟18的最大公因數就是6

從例子我們知道做法就是如果兩數沒有整除，就把原來的除數當做被除數，把餘數當做除數繼續除下去，直到兩數整除為止

於是我們可以知道求a,b兩數的最大公因數，相當於求b與a,b的餘數的最大公因數
以下就是簡單的範例，我們用一般的while迴圈展示輾轉相除法的演算法
另外使用遞迴當做參考

public class Gcd {



 public static void main(String[] args) {  

  //demo1

  System.out.println(gcd(18,12));

    

  //demo2

  System.out.println(gcd2(30,18));  



 }



 public static int gcd(int m, int n){

  int result = 1;

  while(m%n!=0){

   result=n;   

   n=m%n;

   m=result;

  }

  result=n;

  

  return result;

 }

 

 public static int gcd2(int m, int n){

  if(m%n==0){

   return n;

  } else {

   return gcd2(n,m%n);

  }  

 } 

}

接下來三個整數的最大公因數就是將前兩個最大公因數跟第三個數字做最大公因數
四個整數的最大公因數則是將三個整數的最大公因數與第四個數字做最大公因數...
以此類推
以下程式碼就只用while迴圈當範例，遞迴的寫法請自情參考兩個整數的程式碼

public class Gcd {



 public static void main(String[] args) {

  

  //demo1

  int[] x = new int[] {18,12,30};  

  System.out.println(dogcd(x));  

  

  //demo2 

  int[] y = new int[] {15,18,30,42,9};

  System.out.println(dogcd(y));

 }

 

 public static int dogcd(int[] input){

  for(int i=0;i<input.length-1;i++){

   input[i+1] = gcd(input[i],input[i+1]);

      

  }  

  return input[input.length-1];

 }



 public static int gcd(int m, int n){

  int result = 1;

  while(m%n!=0){

   result=n;   

   n=m%n;

   m=result;

  }

  result=n;

  

  return result;

 }
  

}