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

    万次阅读 多人点赞 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;
    }

     

    展开全文
  • 求最大公约数

    2019-11-05 18:43:42
    题目描述 两个数能同时被一个数所整除,这个数就是公约数。例如,12和20的公约数有1,2,4。其中4是12和20的最大公约数。...也可以用穷举法求最大公约数。 #include<stdio.h> int measure(int x,int y)...

    题目描述

    两个数能同时被一个数所整除,这个数就是公约数。例如,12和20的公约数有1,2,4。其中4是12和20的最大公约数。

    输入

    输入两个正整数,用逗号分隔。

    输出

    输出这两个数的最大公约数。

    样例输入
    24,60

    样例输出
    12

    提示

    可以用辗转相除法计算最大公约数;也可以用穷举法求最大公约数。

    #include<stdio.h>
    int measure(int x,int y);
    int main()
    {
    	int m,n,max;
    	scanf("%d,%d",&m,&n);
    	max=measure(m,n);
    	printf("%d\n",max);
    	return 0;
    }
    int measure(int x,int y)
    {
       	int i;
        for(i=x;i>=2;i--)
        {
    		if(x%i==0&&y%i==0) 
    	   		break; 
       	}
    	return i;
    }
    
    展开全文
  • java怎么求最大公约数?最大公约数①定义几个自然数公有的约数,叫做这几个数的公约数;其中最大的一个,叫做这几个数的最大公约数。②辗转相除法又称“欧几里得算法”,是求最大公约数的算法求两个数的最大公约数:...

    4d15f88e8e18cc925beea970367655a5.png

    java怎么求最大公约数?

    最大公约数

    ①定义

    几个自然数公有的约数,叫做这几个数的公约数;其中最大的一个,叫做这几个数的最大公约数。

    ②辗转相除法

    又称“欧几里得算法”,是求最大公约数的算法

    求两个数的最大公约数:如果m > n,令余数remainder = m%n,如果余数不为0,则令m = n, n = remainder,再次remainder = m%n,直到remainder = 0,此时n就是最大公约数。

    求多个数的最大公约数:先求出其中两个数的最大公约数,再求这个最大公约数与第三个数的最大公约数,依次求下去,直到最后一个为止,最后所得的那个最大公约数,就是所求的几个数的最大公约数

    ③代码实现public static int maxCommonDivisor(int m, int n) {

    if (m < n) { // 保证被除数大于除数

    int temp = m;

    m = n;

    n = temp;

    }

    while (m % n != 0) { // 在余数不能为0时,进行循环

    int temp = m % n;

    m = n;

    n = temp;

    }

    return n; // 返回最大公约数

    }

    展开全文
  • python怎么求最大公约数和最小公倍数一、求最大公约数用辗转相除法求最大公约数的算法如下:两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。比如10和25,25除以10商2余5,那么10和...

    python怎么求最大公约数和最小公倍数

    一、求最大公约数

    用辗转相除法求最大公约数的算法如下:

    两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。比如10和25,25除以10商2余5,那么10和25的最大公约数,等同于10和5的最大公约数。

    具体代码如下:def gongyue(a, b):

    """

    欧几里得算法----辗转相除法

    :param a: 第一个数

    :param b: 第二个数

    :return: 最大公约数

    """

    # 如果最终余数为0 公约数就计算出来了

    while(b!=0):

    temp = a % b

    a = b

    b = temp

    return a

    二、求最小公倍数

    求出a,b的最大公约数后,利用gongbei(a,b) = (a*b)/gongyue(a,b) 计算出两个数的最小公倍数:# 求两个数的最小公倍数

    def gongbei(a,b):

    return a * b / gongyue(a, b)

    展开全文
  • 求最大公约数 & 最大公约数

    千次阅读 2020-10-06 21:57:20
    最大公约数 (辗转相除法.): 以小数除大数,如果能整除,那么小数就是所最大公约数.否则就用余数来除刚才的除数;再用这新除法的余数去除刚才的余数.依此类推,直到一个除法能够整除,这时作为除数的...
  • 辗转相除法求最大公约数约数如果数 a 能被数 b 整除,a 就叫做 b 的倍数,b 就叫做 a 的约数。最大公约数最大公约数就是两个数中,大家都能相约且最大的数。辗转相除法辗转相除法又名欧几里得算法(Euclidean ...
  • 辗转相除法代码代码并不难,很多人都会写。public static int f(int a, int b){ while(b !...a b6 88 66 22 0求最大公约数步骤两个数的最大公约数是指能同时整除它们的最大正整数。 设两数为a、b(a≥b),求...
  • python怎么求最大公约数和最小公倍数一、求最大公约数用辗转相除法求最大公约数的算法如下:两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。比如10和25,25除以10商2余5,那么10和...
  • python怎么求最大公约数和最小公倍数一、求最大公约数用辗转相除法求最大公约数的算法如下:两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。比如10和25,25除以10商2余5,那么10和...
  • //求最大公约数和最小公倍数 /*求最大公约数方法:辗转相除法 始终用较大数除以较小数,然后用余数代替较大数 整除时的除数就是最大公约数 举例:222 407求最大公约数 222 407(407除以222余数185) 222 185(222除以...
  • 详细内容python怎么求最大公约数和最小公倍数一、求最大公约数用辗转相除法求最大公约数的算法如下:两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。比如10和25,25除以10商2余5,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,477
精华内容 6,190
关键字:

求最大公约数