华师一附中OI组

标题: 辗转相除法求最大公约数 [打印本页]
作者: admin    时间: 2018-6-28 19:46
标题: 辗转相除法求最大公约数
很经典的算法。小学老师讲的最大公约数一般用短除法，要经过很多次的试除，在c++里面实现并不容易，我们在这里使用辗转相除法。
设求a b两数的最大公约数，a=80,b=48，实际上等价于求b(=48)和 a%b(=32) 的最大公约数，直到a%b=0,这个是最大公约数就是b
  1. #include <iostream>
  2. using namespace std;
  3. int a,b,c;
  4. int main()
  5. {
  6.     cin>>a>>b;
  7.     c=a%b;
  8.     while (c!=0)
  9.     {
  10.         a=b;b=c;c=a%b;
  11.     }
  12.     cout<<b;
  13. }
复制代码



作者: 高歌岭    时间: 2018-7-15 15:46
  1. #include<iostream>
  2. using namespace std;
  3. int a,b,c;
  4. int main()
  5. {
  6.     cin>>a>>b;
  7.     while(b>0)
  8.     {
  9.         c=a;
  10.         a=b;
  11.         b=c%b;
  12.     }
  13.     cout<<a;
  14.     return 0;
  15. }
复制代码
作者: admin    时间: 2018-7-15 21:13
楼上的做法感觉有问题！
作者: JASONZHU    时间: 2018-7-16 23:00
  1. #include<iostream>
  2. using namespace std;
  3. int a,b,s;
  4. int main()
  5. {
  6.     cin>>a>>b;
  7.     s=a%b;
  8.     while(s!=0)
  9.     {
  10.         a=b;
  11.         b=s;
  12.         s=a%b;
  13.     }
  14.     cout<<b;
  15.     return 0;
  16. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2