Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3236073
  • 博文数量: 367
  • 博客积分: 9916
  • 博客等级: 中将
  • 技术积分: 7199
  • 用 户 组: 普通用户
  • 注册时间: 2011-05-29 23:27
个人简介

简单!

文章分类

全部博文(367)

文章存档

2013年(51)

2012年(269)

2011年(47)

分类: C/C++

2013-05-01 20:31:51

辗转相除法又名欧几里德算法(Euclidean algorithm)乃求两个正整数之最大公因子的算法。它是已知最古老的算法,其可追溯至前300年。它首次出现于欧几里德的《几何原本》中,而在中国则可以追溯至东汉出现的《九章算术》。

证明:

设两数为ab(ba),求它们最大公约数(ab)的步骤如下:用ba,得abq......r1(0r)。若r1=0,则(ab)b;若r10,则再用r1b,得br1q......r2(0r2).r20,则(ab)r1,若r20,则继续用r2r1,……如此下去,直到能整除为止。其最后一个非零余数即为(ab)

辗转相除法是利用以下性质来确定两个正整数ab的最大公因子的:

1.ra÷b的余数,gcd(a,b)=gcd(b,r)

2.a和其倍数之最大公因子为a

另一种写法是:

1.a÷b,令r为所得余数(0rb)。若r=0,算法结束;b即为答案。

        2.互换:置abbr,并返回第一步。

方法一:
  1. int gcd(int a,int b)
  2. {
  3.     if(b==0)
  4.         return a;
  5.     else
  6.         return gcd(b,a%b);
  7. }

对方法一的改进:
  1. int gcd(int a,int b)
  2. {
  3.         return b ? gcd(b, a%b) : a;
  4. }

方法二:
  1. int gcd( int a, int b)
  2. {
  3.     int temp;

  4.      while(b)
  5.      {
  6.           temp = b;
  7.           b = a%b;
  8.           a = temp;      
  9.      }

  10.      return a;
  11. }

对方法二的改进:
  1. int gcd(int a, int b)
  2. {
  3.     while(b)
  4.         b = a%b + 0/(a=b);

  5.     return a;
  6. }
阅读(1428) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册