什么是辗转相除法

什么是辗转相除法

问题一：什么叫做辗转相除法？举几个例子 辗转相除法最大的用途就是用来求两个数的最大公约数。
用（a,b）来表示a和b的最大公约数。
有定理： 已知a,b,c为正整数，若a除以b余c，则（a,b）=(b,c)。 （证明过程请参考其它资料）
例：求 15750 与27216的最大公约数。
解：
∵27216=15750×1+11466 ∴（15750，27216）=（15750，11466）
∵15750=11466×1+4284 ∴（15750，11466）=(11466,4284)
∵11466=4284×2+2898 ∴(11466,4284)=（4284，2898）
∵4284=2898×1+1386 ∴（4284，2898）=（2898，1386）
∵2898=1386×2+126 ∴（2898，1386）=（1386，126）
∵1386=126×11 ∴（1386，126）=126
所以（15750，27216）=216
辗转相除法比较适合用来求两个比较大的数的最大公约数 。问题二：什么是辗转相除法 用辗转相除法（即欧几里得算法）求两个正整数的最大公约数。
解析：
设两个数m,n，假设m>=n，用m除以n，求得余数q。若q为0，则m为最大公约数；若q不等于0，则进行如下迭代：
m=n,n=q,即原除数变为新的被除数，原余数变为新的除数重复算法，直到余数为0为止。余数为0时的除数n，即为原始m、n的最大公约数。
迭代初值：m，n的原始值；
迭代过程：q=m%n;
m=n;
n=q;
迭代条件：q!=0
例如：m=8;n=6
q=m%n(8%6==2)
m=n(m==6)
n=q(n==2)
因为：(q==2)!=0，重复算法：
q=m%n(6%2==0)
m=n(m==2)余数为0时的除数n为最大公约数，n值赋给了m，所以输出m的值
n=q(n==0)
因为：q==0 所以最大公约数为m的值
源程序：
#include
void main()
{
int m,n,q,a,b;
printf(Enter two integers:);
scanf(%d%d,&a,&b);
m=a;
n=b;
if(n>m)
{
int z;
z=m;m=n;n=z;//执行算法前保证m的值比n的值大
}
do
{
q=m%n;
m=n;
n=q;
}while(q!=0);
printf(The greatest common divisor of);
printf(%d,%d is %d\n,a,b,m);
}
希望对你有所帮助!问题三：辗转相除法 到底是什么？ 辗转相除法 优点是可以求出两个大数的最大公因数
如果我们要求8251与6105的最大公因数的话
假设8251是这个数x的a倍，再假设6105是x的b倍
那么2146=8251-6105，是x的(a-b)倍，也是x的倍数
而无论这几个数如何加减，甚至相乘，都还是最大公约数的倍数
我们就可以把求8251与6105的最大公约数简化成求2146和6105的最大公约数，再把求2146与6105的最大公约数简化为求3959(=6105-2146)与2146的最大公约数
如此相减往复几次后，会发现两个数变相等了，这个数就是两个原来数的最大公因数
举个例子
9和6
9-6=3，保留6,3
6-3=3，保留3,3
发现两数相等，为3
所以最大公因数为3觉得好就采纳吧，谢谢