给我讲一下用短除法和辗转相除法求最大公约数

给我讲一下用短除法和辗转相除法求最大公约数
给我讲一下用短除法和辗转相除法求最大公约数

给我讲一下用短除法和辗转相除法求最大公约数
辗转相除法：
要求a、b两个整数的最大公约数,a＞b,那么我们先用a除以b,得到商 q1,余数r1：a÷b＝q1…r1我们当然也可以把上面这个式子改写成乘法式：
a＝b * q1＋r1
如果r1＝0,那么b就是a、b的最大公约数3.要是r1≠0,就继续除,用b除以r1,我们也可以有和上面一样的式子：
b＝r1q2＋r2
如果余数r2＝0,那么r1就是所求的最大公约数3.因为如果b＝r1q2＋r2变成了b＝r1q2,那么b1r1的公约数就一定是a1b的公约数.这是因为一个数能同时除尽b和r1,那么由a＝b * q1＋r1,就一定能整除a,从而也是a1b的公约数.
反过来,如果一个数d,能同时整除a1b,那么由1）式,也一定能整除r1,从而也有d是b1r1的公约数.
这样,a和b的公约数与b和r1的公约数完全一样,那么这两对的最大公约数也一定相同.那b1r1的最大公约数,在r1＝0时,不就是r1吗?所以a和b的最大公约数也是r1了.
如果r2不是0,用r1除以r2,……直到余数为零为止.
短除法
如例子：
2|_18__30__
3|_9__15__
3 5
其实短除法就是放到一起慢慢约分,对于简单的还有效,而大一点的数还是辗转相除法比较有效,而且辗转相除法的逻辑性也为计算机编程提供了条件

//
//??相除法, 又名欧几里德算法（Euclidean algorithm）乃求?个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至3000年前。它首次出?于欧几里德的《几何原本》（第VII卷，命?i和ii）中，而在中国?可以追溯至??出?的《九章算?》。它并不需要把二数作?因子分解。
//?明：
//??数?a、b(b＜a)，求它?最大公?数(a、...

全部展开

//
//??相除法, 又名欧几里德算法（Euclidean algorithm）乃求?个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至3000年前。它首次出?于欧几里德的《几何原本》（第VII卷，命?i和ii）中，而在中国?可以追溯至??出?的《九章算?》。它并不需要把二数作?因子分解。
//?明：
//??数?a、b(b＜a)，求它?最大公?数(a、b)的??如下：用b除a，得a＝bq......r 1(0?r)。若r1=0，?(a，b)＝b；若r1≠0，?再用r1除b，得b＝r1q......r2 (0?r2).若r2＝0，?(a，b)＝r1，若r2≠0，???用r2除r1,……如此下去，直到能整除?止。其最后一个非零余数即?(a，b)。
#include
#include
int gcd(double m,double n);
void main()
{
//printf("float size = %d \n",sizeof(float));
//printf("double size = %d \n",sizeof(double));
int r;
float a,b,max,min;
printf("Please input the two integers needed to get their greatest common divitor!\n");
loop_input_int_a:
{
printf("a=");
scanf("%f",&a);
if(a-(int)a!=0)
{
printf("The number is not a integer!!Please retry...\n");
goto loop_input_int_a;
}//endif
}//loop_input_int_a
loop_input_int_b:
{
printf("b=");
scanf("%f",&b);
if(b-(int)b!=0)
{
printf("The number is not a integer!!Please retry...\n");
goto loop_input_int_b;
}//endif
}//loop_input_int_b
max=(a>b)?a:b;
min=(ar=gcd(max,min);
printf("Success! The greatest common divitor of %d,%d is:%d.",(int)a,(int)b,r);
}
int gcd(double m,double n)
{
int ret;
ret=(int)n;
if(ret!=0)
return gcd(n,(int)m%(int)n);
else
return (int)m;
}

收起