四种算法求最大公约数C/C++tuityftuy的博客-

四种算法求最大公约数（C++)

一．
实验目的

1. 明确算法的概念和特点。

2. 通过对问题的分析，设计合理的算法解决问题；

二．
实验内容

运行最大公约数的常用算法，并进行程序的调式与测试，要求程序设计风格良好，并添加异常处理模块（如输入非法等）。

三． 算法及流程图

1.辗转相除法

辗转相除法（又名欧几里德法）C语言中用于计算两个正整数a,b的最大公约数和最小公倍数，实质它依赖于下面的定理： gcd(a,b)=gcd(b,a mod b),(b!=0)。

2.穷举法

穷举法（也叫枚举法）求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数 。

3.更相减损法

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

4. Stein算法

两个数均为偶数时有公约数2，且公约数一定为偶数。一个奇数一个偶数时，因为其奇偶性的不同，所以其最大公约数一定为奇数。当两个数均为奇数时，其最大公约数一定是奇数。
1.辗转相除法

2.穷举法

3.更相减损法

4.stein算法

四.代码

#include <iostream>  #include <ctime>  #include <math.h>  using namespace std; //辗转相除法求最大公约数   int gcd1(int a, int b) { int temp, t; if (a < b) {                t = a;                 a = b;                  b = t; } while (b != 0) {                 temp = a % b;                a = b;                   b = temp; } return a; //返回最大公约数   } //穷举法求最大公约数   int gycd2(int a, int b) { int temp ;           temp = (a > b) ? b : a; while (temp > 0) { if (a % temp == 0 && b % temp == 0) break;                 temp--; } return temp; //返回最大公约数  } //更相减损法求最大公约数  int gcd3(int a, int b） { int i = 0, temp, t=0; while (a % 2 == 0 && b % 2 == 0) {                      a /= 2;                      b /= 2;                     i += 1; } if (a < b) {                   temp = a;                     a = b;                     b = temp; } while (t!= 0) {                   t = a - b;                    a = (b > t) ? b : t;                     b = (b < t) ? b : t; if (b == (a - b)) break; } if (i == 0) return b; else return (int)pow(2, i) * b; //返回最大公约数  } //stein算法求最大公约数   int gcd4(unsigned int a,unsigned int b) { int factor = 0; //计数器       int temp; //大数赋给a，小数赋给b      if (a < b) {                 temp = a;                 a = b;                   b = temp; } if (b == 0) { return 0; } while (a != b) { if (a & 0x1) { if (b & 0x1) //a和b都为奇数               {                              b = (a - b) >> 1;                                  a -= b; } else //x为奇数，y为偶数              {                               b >> 1; } } else { if (b & 0x1) //x为奇数，y为偶数             {                              a >>= 1; if (a < b) {                                      temp = a;                                        a = b;                                        b = temp; } } else { //x和y都为偶数                              a >>= 1;                                  b >>= 1; ++factor; } } } return (a << factor); //返回最大公约数  } int main() { int a, b;            clock_t start1,start2,start3,start4,finish1,finish2,finish3,finish4;           cout << "请输入数据：" << endl;      cin >> a >> b; //辗转相除法求最大公约数            start1 = clock();                  cout << "辗转相除法所求结果为：" << endl;            cout << "最大公约数为：" << gcd1(a,b)<<endl;                 finish1 = clock();                       cout <<"运行所花时间为：  "<< finish1-start1 << "/" << CLOCKS_PER_SEC << "秒" << endl;             cout << endl; //穷举法求最大公约数            start2 = clock();            cout << "穷举法法所求结果为：" << endl;            cout << "最大公约数为：" << gcd1(a, b) << endl;            finish2 = clock();            cout << "运行所花时间为：  " << finish2 - start2 << "/" <<           CLOCKS_PER_SEC << "秒" << endl;           cout << endl; //更相减损法求最大公约数            start3 = clock();            cout << "更相减损法所求结果为：" << endl;            cout << "最大公约数为：" << gcd1(a, b) << endl;            finish3 = clock();            cout << "运行所花时间为：  " << finish3 - start3 << "/" << CLOCKS_PER_SEC << "秒" << endl;            cout << endl; //stein算法求最大公约数            start4 = clock();            cout << "stein算法所求结果为：" << endl;            cout << "最大公约数为：" << gcd1(a, b) << endl;            finish4 = clock();            cout << "运行所花时间为：  " << finish4 - start4 << "/" << CLOCKS_PER_SEC << "秒" << endl;           cout << endl; return 0; } 

五.程序测试（调试就不放了）