编程之美读书笔记 -最大公约数 (二)
{
//如果a < b
if(a < b){
return GCD(b,a);
}
if(b == 0){
return a;
}
//若x,y都为偶数
if(IsEvenOdd(a) == 1 && IsEvenOdd(b) == 1){
return 2 * GCD(a>>1,b>>1);
}
//若x,y都为奇数
else if(IsEvenOdd(a) == 0 && IsEvenOdd(b) == 0){
return GCD(b,a-b);
}
//若x是偶数y是奇数
else if(IsEvenOdd(a) == 1 && IsEvenOdd(b) == 0){
return GCD(a>>1,b);
}
//若x是奇数y是偶数
else{
return GCD(a,b>>1);
}
}
int main(){
int a,b;
scanf("%d %d",&a,&b);
printf("%d\n",GCD(a,b));
}
#include
//判断奇偶性
int IsEvenOdd(int n){
if(n % 2 == 0){
return 1;
}
else{
return 0;
}
}
int GCD(int a,int b)
{
//如果a < b
if(a < b){
return GCD(b,a);
}
if(b == 0){
return a;
}
//若x,y都为偶数
if(IsEvenOdd(a) == 1 && IsEvenOdd(b) == 1){
return 2 * GCD(a>>1,b>>1);
}
//若x,y都为奇数
else if(IsEvenOdd(a) == 0 && IsEvenOdd(b) == 0){
return GCD(b,a-b);
}
//若x是偶数y是奇数
else if(IsEvenOdd(a) == 1 && IsEvenOdd(b) == 0){
return GCD(a>>1,b);
}
//若x是奇数y是偶数
else{
return GCD(a,b>>1);
}
}
int main(){
int a,b;
scanf("%d %d",&a,&b);
printf("%d\n",GCD(a,b));
}
这个算法的好处就是用移位操作来代替除法操作，大大节约时间。