当前位置:编程学习 > C/C++ >>

编程之美读书笔记 -最大公约数

问题:
 
求两个数的最大公约数
 
解法一:
 
欧几里得辗转相除法:
 
f(x,y) = 易做图(x,y), 取k = x / y, b = x % y,则:x = k*y + b;  www.zzzyk.com
如果一个数能整除x,y,则它也能整除b,y; 而且能整除b,y的数必能整除x,y,即x,y和b,y的公约数是相同的,其最大公约数也是相同的,即f(x,y) = f(y ,x % y) (x>=y>0)
 
 
 
 
例如,计算a = 1071和b = 462的最大公约数的过程如下:从1071中不断减去462直到小于462(可以减2次,即商q0 = 2),余数是147:
1071 = 2 × 462 + 147.
然后从462中不断减去147直到小于147(可以减3次,即q1 = 3),余数是21:
462 = 3 × 147 + 21.
再从147中不断减去21直到小于21(可以减7次,即q2 = 7),没有余数:
147 = 7 × 21 + 0.
此时,余数是0,所以1071和462的最大公约数是21
 
 
递归算法:
 
 
[cpp] 
#include<stdio.h>    
  
//递归形式    
int 易做图(int a,int b)  
{   
    if(b == 0){  
        return a;  
    }  
    else{  
        //a,b和b,a%b有相同的最大公约数   
        return 易做图(b,a%b);  
    }  
  
}   
  
int main(){  
    int a,b;  
    scanf("%d %d",&a,&b);  
    printf("%d\n",易做图(a,b));  
}  
 
#include<stdio.h> 
 
//递归形式 
int 易做图(int a,int b)
if(b == 0){
return a;
}
else{
//a,b和b,a%b有相同的最大公约数
return 易做图(b,a%b);
}
 
 
int main(){
int a,b;
scanf("%d %d",&a,&b);
printf("%d\n",易做图(a,b));
}
例如易做图(1071, 462)的计算过程是:
 
函数的第一次调用计算易做图(462, 1071 mod 462) = 易做图(462, 147);
 
下一次调用计算           易做图(147, 462 mod 147) = 易做图(147, 21),
 
在接下来是                   易做图(21, 147 mod 21) = 易做图(21, 0) = 21。
 
 
非递归算法: 
 
[cpp] 
#include<stdio.h>    
  
//非递归形式    
int 易做图(int a,int b)  
{   
    int temp = a;  
    while(b){  
        a = b;  
        b = temp % b;  
    }  
    return a;  
}   
  
int main(){  
    int a,b;  
    scanf("%d %d",&a,&b);  
    printf("%d\n",易做图(a,b));  
}  
 
#include<stdio.h> 
 
//非递归形式 
int 易做图(int a,int b)
int temp = a;
while(b){
a = b;
b = temp % b;
}
return a;
 
int main(){
int a,b;
scanf("%d %d",&a,&b);
printf("%d\n",易做图(a,b));
}
解法二: 
 
在解法一中我们用到了取模运算。在大整数中取模运算(涉及到除法运算)是非常高贵的开销。
 
我们想想避免用取模运算。
 
类似前面的分析,一个数能整除x,y则必能同时整除x - y,y。能同时整除x - y,y 则必能同时整除x,y。即x,y的公约数和x-y,y的公约数是一样的,其最大公约数也是一样的。
 
 
[cpp] 
#include<stdio.h>    
  
int 易做图(int a,int b)  
{   
    //如果a < b   
    if(a < b){  
        return 易做图(b,a);  
    }  
    if(b == 0){  
        return a;  
    }  
    else{  
        return 易做图(a - b,b);  
    }  
}   
  
int main(){  
    int a,b;  
    scanf("%d %d",&a,&b);  
    printf("%d\n",易做图(a,b));  
}  
 
#include<stdio.h> 
 
int 易做图(int a,int b)
//如果a < b
if(a < b){
return 易做图(b,a);
}
if(b == 0){
return a;
}
else{
return 易做图(a - b,b);
}
 
int main(){
int a,b;
scanf("%d %d",&a,&b);
printf("%d\n",易做图(a,b));
}此解法用减法而不是除法,这样迭代的次数比除法要多,当遇到f(10000000,1)的情况时这不是一个好方法。
 
 
 
 
解法三:
 
分析:
 
对于x,y,如果y = k * y1,x = k * x1,则f(y,x) = K*f(x1,y1);
 
如果x = p * x1, 假设p是素数,且 y % p != 0 ,即y不能被p整除,则f(x,y) = f(x1,y).
 
可以利用上面两点进行改进。因为2是素数,同时对于二进制表示的大整数而言可以很容易的将除以2和乘以2的算法转换为移位运算,从而避免大整数除法。
 
可以充分利用2进行分析:
若x,y都为偶数(2肯定是公约数),则f(x,y) = 2*f(x / 2,y / 2) = 2*f(x>>1,y>>1);
若x为偶数,y为奇数(2肯定不是公约数),则f(x,y) = f(x / 2, y / 2) = f(x>>1, y)
若x为奇数,y为偶数2肯定不是公约数),则f(x,y)= f(x, y / 2) = f(x, y>>1)
若x,y都为奇数(2肯定不是公约数),则f(x,y) = f(y, x-y)    (x-y肯定为偶数) = f(y, (x-y)/2)
 
 
 
 
[cpp] 
#include<stdio.h>    
//判断奇偶性   
int IsEvenOdd(int n){  
    if(n % 2 == 0){  
        return 1;  
    }  
    else{  
        return 0;  
    }  
}  
  
int 易做图(int a,int b)  
{   
    //如果a < b   
    if(a < b){  
        return 易做图(b,a);  
    }  
    if(b == 0){  
        return a;  
    }  
    //若x,y都为偶数   
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,