精华内容
下载资源
问答
  • 求最大公约数(辗转相除法

    万次阅读 多人点赞 2019-06-03 16:20:50
    最大公约数(Greatest Common Divisor)指两个或多个整数共有约数中最大的...求最大公约数有多种 方法,常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数,a,b的 最小...

    最大公约数(Greatest Common Divisor)指两个或多个整数共有约数中最大的一个。

    也称最大公因数、最大公因子,a, b的最大公约数记为(a,b),同样的,a,b,c的最大 公约数记为(a,b,c),多个 整数的最大公约数也有同样的记号。求最大公约数有多种 方法,常见的有 质因数分解法、 短除法、 辗转相除法、 更相减损法。与最大公约数相对应的概念是 最小公倍数,a,b的 最小公倍数记为[a,b]。

    再来介绍一下辗转相除法:

    辗转相除法又叫欧几里得算法,是欧几里得最先提出来的.辗转相除法的实现,是基于下面的原理(在这里用(a,b)表示a和b的最大公因数):
      (a,b)=(a,ka+b),其中a、b、k都为自然数.………………①
      也就是说,两个数的最大公约数,将其中一个数加到另一个数上,得到的新数,其公约数不变,比如(4,6)=(4+6,6)=(4,6+2×4)=2.要证明这个原理很容易:如果p是a和ka+b的公约数,p整除a,也能整除ka+b.那么就必定要整除b,所以p又是a和b的公约数,从而证明他们的最大公约数也是相等的.
      基于上面的原理,就能实现我们的迭代相减法:
      (78,14)=(64,14)=(50,14)=(36,14)=(22,14)=(8,14)=(8,6)=(2,6)=(2,4)=(2,2)=(0,2)=2
      基本上思路就是大数减去小数,一直减到能算出来为止,在作为练习的时候,往往进行到某一步就已经可以看出得值.迭代相减法简单,不过步数比较多,实际上我们可以看到,在上面的过程中,由(78,14)到(8,14)完全可以一步到位,因为(78,14)=(14×5+8,14)=(8,14),由此就诞生出我们的辗转相除法.
      用辗转相除法求(a,b).设r0=b,r1=a,反复运用除法算式,得到一系列整数qi,ri和下面的方程:
      相当于每一步都运用原理①把数字进行缩小,上面右边就是每一步对应的缩小结果,可以看出,最后的余数rn就是a和b的公约数.迭代相减法和辗转相除法在本质上是一样的,相对来说,减法比较简单(需要10步),但是除法步数少(仅需4步).

    因此可以通过这个原理来求出最大公约数: 

    #include<iostream>
    #include<cstdio>
    using namespace std;
    
    int fun(int m,int n){
    	int rem;			//余数,当余数为0的时候,最后的m即为最大公约数
    	//先用较小的数对较大的数取余,再用余数对较小的数求余,直到余数为零 
    	while(n > 0){
    		rem = m % n;
    		m = n;
    		n = rem;
    	}
    	return m;			//将结果返回			
    }
    int main(){
    	int n,m;
    	cin>>m>>n;
    	cout<<"m和n的最大公约数为:"<<fun(m,n)<<endl;
    	return 0; 
    } 

    因为到余数为零结束,所以还可以将程序简化一下用递归来求:

    int fun(int m,int n){
    	if(n==0) return m;
    	return fun(n,m%n);
    }

    再简化一下,用一行代码来求:

    int gcd(int m, int n) {
        return n ? gcd(n, m % n) : m;
    }

    展开全文
  • 辗转相除法证明辗转相除法证明辗转相除法证明辗转相除法证明
  • 辗转相除法

    千次阅读 多人点赞 2020-12-22 17:36:37
    求两个数的最小公约数经常使用辗转相除法。 代码很简单,如下所示: #include<stdio.h> int main() { int M,N; scanf("%d %d",&M,&N); int a=M,b=N; if(M<N)//先调整大小,使M为两数中较大...

    求两个数的最小公约数经常使用辗转相除法。

    代码很简单,如下所示:

    #include<stdio.h>
    int main()
    {
        int M,N;
        scanf("%d %d",&M,&N);
        int a=M,b=N;
        if(M<N)//先调整大小,使M为两数中较大者,N为较小者
        {
            int t=M;
            M=N;
            N=t;
        }
        int r=M%N;//求得余数
        while(r!=0)
        {
            M=N;
            N=r;
            r=M%N;
        }//当r不为0,退出循环,得到N为最大公约数
        M=a*b/N;//M为最小公倍数
        printf("%d %d\n",N,M);//打印最大公约数,最小公倍数
        return 0;
    }

    但道理却有点绕,我们应当去追寻其本质的道理,溯其根本才得以善用之。

    设有未知数X和Y,且X>Y,现求其最大公约数(能同时整除X和Y的最大的自然数),

    X/Y   商Q 余R,解答问题的关键在于:若X和Y存在最大公约数Z,则对任意mX+nY都能被Z整除,即Z是其因数。

    若R==0,我们可以轻易知道最大公约数就是除数Y

    若R!=0,可得X-QY(为mX+nY的结构其中m=1,n=-Q)=R>0,由上可知,Z必定为R的因数。

    综上,(X,Y)=Z,(Y,R)=Z,其中(X>Y>R),Z为三者的最大公约数。

    现令X=Y,Y=R。重复X/Y=商Q余D,

    若D!=0 ,Y-QR=D>0,Z必定为D的因数,Z也为R的因子,亦可得(R,D)=Z,可得(X,Y)=(Y,R)=(R,D)=Z

    若D==0,即Y和R的最大公因数为R自身,(X,Y)=(Y,R)=Z=R。

    因此求最大公约数算法为:

    1. 比较M和N大小,使M为较大者
    2. R=M%N,R为M取N的余数
    3. 若R==0,易知M和N的最大公约数为N
    4. 若R!=0,令M=N,N=R,跳到(2)

     

     

     

     

     

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 18,560
精华内容 7,424
关键字:

辗转相除发