什么是辗转相除法?

  辗转相除法(又名欧几里德算法),它主要用于求两个正整数的最大公约数。是已知的最古老的算法。

  用辗转相除法求132和72的最大公约数的步骤:

    132 / 72 = 1 ... 60

    72  /  60 = 1 ... 12

    60 /  12  = 5

  所以他们的最大公约数就是12。

如何实现辗转相除法?

  我们把要求的两个数定为a和b(a > b)。

  首先算1.a / b = c ... r

  接着2.a = b, b = r,并判断r是否是0。若不为零则重复1,若为0则输出除数,也就是b。

  但是,仔细一想,b = r,r = 0,输出的结果总是0,所以我们要找到原来的b,就是a,所以正确的应该是输出a。

  这是经过重复修改后的伪代码:

  while(b ≠ 0){

    r = a mod b;

    a = b;

    b = r;

    if(r == 0) break and show a;

  }

  完整的程序代码:

#include <stdio.h>
#include <stdlib.h> int fun(int, int); int main(int argc,char *argv[])
{
int a,b,n;
printf("请输入两个数:");
scanf("%d%d",&a,&b);
if( (a <= ) || (b <= ) ){ //数据检查
printf("除数不能为0");
return ;}
n = ( a > b ? fun(a,b) : fun(b,a) ); //调用函数并处理大小顺序
printf("最大公因数:%d",n);
getch();
return ;
} int fun(int a,int b)
{
int r;
while(b){ //因为b的初值不为0,所以循环有效。当b=0时,余数r=0,循环终止。
r = a % b; //取余数
a = b; //除数作被除数
b = r; //商作除数
}
return a; //a就是最后的除数
}
04-18 01:56