輾轉(zhuǎn)相除法
倆個(gè)正整數(shù)的最大公約數(shù)等于他們的余數(shù)和較小數(shù)之間的最大公約數(shù)
package gcl;
public class Gcl_1 {
/**
* 求最大公約數(shù) 轉(zhuǎn)轉(zhuǎn)相除法
*
* 缺點(diǎ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
更相減損法
倆個(gè)正整數(shù)的最大公約數(shù)等于他們的差值和較小數(shù)之間的最大公約數(shù)
package gcl;
public class Gcl_2 {
/**
* 更相減損法
*
* 缺點(diǎn) ，如果倆數(shù)差距太大運(yùn)算次數(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
位移法
當(dāng)倆個(gè)數(shù)字中任意一個(gè)數(shù)字是偶數(shù)時(shí)要通時(shí)進(jìn)行右移，也就是除2操作，如果同時(shí)右移，這就要保留乘2，因?yàn)檫@是倆個(gè)數(shù)字的公約數(shù)。
package gcl;
public class Gcl_3 {
/**
* 通過位運(yùn)算進(jìn)行除2操作，當(dāng)倆個(gè)數(shù)字都不偶數(shù)時(shí)進(jìn)行更相減損法
*
* 判斷一個(gè)數(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));
}
}
三種方法對(duì)比，輾轉(zhuǎn)取模太慢，更相倆個(gè)數(shù)差距過大需要運(yùn)算次數(shù)太多，而位運(yùn)算則結(jié)合了倆種的優(yōu)點(diǎn)，
