三个数最大公约数python代码while 3个数最大公约数怎么求 |
您所在的位置：网站首页 › 求最大公约数python代码循环 › 三个数最大公约数python代码while 3个数最大公约数怎么求 |
|
如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数（Greatest Common Divisor，简写为GCD）。例如，自然数12和30的公约数有1、2、3、6，其中6就是12和30的最大公约数。 求最大公约数有多种方法，常见的有辗转相除法、短除法、更相减损法、质因数分解法等。 1．辗转相除法。 辗转相除法的基本做法是用较大的数除以较小的数，若余数为0，则其中较小的数（即除数）就是最大公约数；若余数不为0，则用前面较小的除数和得出的余数构成新的一对数，继续做上面的除法，直到出现能够整除的两个数（余数为0）。 下面以求48和27的最大公约数为例，求解过程如下： 48 ÷ 27 = 1余 21 27 ÷ 21 = 1余6 21 ÷ 6 =3余3 6 ÷ 3=2 所以3就是48和27的最大公约数。 辗转相除法使用到的原理也很简单，假设用f（x, y）表示x，y的最大公约数，取k = x/y，b = x%y，则x = ky + b，如果一个数能够同时整除x和y，则必能同时整除b和y；而能够同时整除b和y的数也必能同时整除x和y，即x和y的公约数与b和y的公约数是相同的，其最大公约数也是相同的，则有f（x, y）= f（y, x%y）（y > 0），如此便可把原问题转化为求两个更小数的最大公约数，直到其中一个数为0，剩下的另外一个数就是两者最大的公约数。 采用辗转相除法编写的求两个整数m和n的最大公约数的函数及测试主程序如下。 #include int gcd(int m,int n) { int r=m%n; while (r!=0) { m = n; n = r; r = m%n; } return n; } int main() { int m,n,t; while (scanf("%d %d",&m,&n)!=EOF) { t = gcd(m,n); printf("%d\n",t); } return 0; }这个函数也可以写成递归的形式，如下。 int gcd(int m,int n) { if (m%n==0) return n; return gcd(n,m%n); }2．短除法。 短除法是不断地找两个数的最小公约数，直到找不到为止，然后把所有的最小公约数乘起来，就是最大公约数。 下面以求48和36的最大公约数为例，操作如下： 从除1外的最小的约数2开始试探起 48 ÷ 2 = 24 36 ÷ 2 =18 ，2是约数 24 ÷ 2 = 12 18 ÷ 2 =9 ， 2还是约数 12 ÷ 3 = 4 9 ÷ 3 =3 ， 3是约数 4和3不存在公约数，结束。 所以，2×2×3=12就是48和36的最大公约数。 采用短除法编写的求两个整数m和n的最大公约数的函数如下。 int gcd(int m,int n) { int i,r = 1; for (i=2;i (9,6) -> (3,6) -> (3,3)所以，3就是24和15的最大公约数。 采用更相减损法编写的求两个整数m和n的最大公约数的函数如下。 int gcd(int m,int n) { int t; while (m!=n) { if (m>1, b>>1)；当a为偶数，b为奇数时，gcb(a,b) = gcb(a/2, b) = gcb(a>>1, b) 当a为奇数，b为偶数时，gcb(a,b) = gcb(a, b/2) = gcb(a, b>>1) 当a和b均为奇数，利用更相减损术运算一次，gcb(a,b) = gcb(b, a-b)，此时a-b的结果必然是偶数，又可以继续进行移位运算。 采用 Stein算法编写的求两个整数m和n的最大公约数的函数如下。 int gcd(int m,int n) { int p=1,t; while (m%n!=0) { if (m>1; n=n>>1; } else { m=m>>1; } } else { if (n%2==0) { n=n>>1; } else { m=m-n; m=m>>1; } } } return p*n; }这一算法可以写成递归的形式，如下。 int gcd(int m,int n) { if (m < n) { int tmp = m; m = n; n = tmp; } if (m%n==0) return n; if (m % 2 == 0 && n % 2 == 0) return 2*gcd(m >> 1, n >> 1); else if (m%2 == 0 && n%2 != 0) return gcd(m >> 1, n); else if (m%2 != 0 && n % 2 == 0) return gcd(m, n >> 1); else if (m % 2 != 0 && n % 2 != 0) return gcd(n, (m - n) >> 1); }【例1】最大最小公倍数。 问题描述 已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。 输入 输入一个正整数N（1 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |