輾轉(zhuǎn)相除法
倆個正整數(shù)的最大公約數(shù)等于他們的余數(shù)和較小數(shù)之間的最大公約數(shù)
package gcl;
public class Gcl_1 {
/**
* 求最大公約數(shù) 轉(zhuǎn)轉(zhuǎn)相除法
*
* 缺點 取余操作效率低
*/
public static int gcl(int a,int b){
int max = a>b?a:b;
int min = a<=b?a:b;
if(max%min==0){
return b;
}
return gcl(max,max%min);
}
public static void main(String[] args) {
// System.out.println(gcl(10,5));
System.out.println(gcl(10000000,5));
}
}
結(jié)果
5
更相減損法
倆個正整數(shù)的最大公約數(shù)等于他們的差值和較小數(shù)之間的最大公約數(shù)
package gcl;
public class Gcl_2 {
/**
* 更相減損法
*
* 缺點 ，如果倆數(shù)差距太大運算次數(shù)過多
*/
public static int gcl2(int a,int b){
int max =a>b?a:b;
int min = a<=b?a:b;
if(max==min){
return min;
}
return gcl2(max-min,min);
}
public static void main(String[] args) {
System.out.println(gcl2(10,5));
}
}
結(jié)果
5
位移法
當倆個數(shù)字中任意一個數(shù)字是偶數(shù)時要通時進行右移，也就是除2操作，如果同時右移，這就要保留乘2，因為這是倆個數(shù)字的公約數(shù)。
package gcl;
public class Gcl_3 {
/**
* 通過位運算進行除2操作，當倆個數(shù)字都不偶數(shù)時進行更相減損法
*
* 判斷一個數(shù)是否是偶數(shù)， 3 &1 0010 &0001 =0 即和1 做與操作等于0及是偶數(shù)
*/
public static int gcl3(int a, int b){
int max = a>b?a:b;
int min = a<=b?a:b;
if(a==b){
return b;
}else if((a&1)==0 && (b&1)==0){
return gcl3(a>>1,b>>1)*2;
}else if((a&1)!=0 && (b&1)==0){
return gcl3(a,b>>1);
}else if((a&1)==0 && (b&1)!=0){
return gcl3(a>>1,b);
}else{
return gcl3(a,a-b);
}
}
public static void main(String[] args) {
System.out.println(gcl3(5,10));
}
}
三種方法對比，輾轉(zhuǎn)取模太慢，更相倆個數(shù)差距過大需要運算次數(shù)太多，而位運算則結(jié)合了倆種的優(yōu)點，
