求最大公约数的4种算法（C++）

一、实验目的
1.计算两个正整数的最大公约数和最小公倍数，并进行程序的调式与测试。
2.理解四种不同的求最大公约数的方法，学习其思维模式。
3.了解算法的概念。对问题的分析时，进行合适的算法设计。
二、算法设计
1.题目分析
（1）首先输入一对正整数，对两个数进行判断，若不是正整数，则给出提示并重新输入，直至两个数均为正整数为止。
（2）将两个数传入计算最大公约数的函数和计算最小公倍数的函数中，求解输出。
（3）验证各种算法的效率，在求解函数之前设置一个计时器开始运行，在函数执行完毕后，结束计时，计算出两个时间节点的差，即可得出每个函数执行一定次数的时间。规定统一的次数，将每种算法所用时间进行对比即可。
2.算法设计
1.辗转相除法，又称欧几里得算法。用于计算两个正整数a，b的最大公约数和最小公倍数，其依赖于gcd(a,b) = a (b=0)和gcd(b,a mod b) (b!=0).
2．穷举法，也叫枚举法，求最大公约数时从两者中较小的数开始，由大到小列举，直到找到第一个公约数为止。
3.更相减损法，若两个正整数都为偶数，则用2约简，直到不能约简为止。然后用大数减小数，将差与较小的数比较，再以大数减小数，直到减数和差相等为止。
4. Stein算法，两个数均为偶数时有公约数2，且公约数一定为偶数。一个奇数一个偶数时，因为其奇偶性的不同，所以其最大公约数一定为奇数。当两个数均为奇数时，其最大公约数一定是奇数。
三、业务流程图设计
欧几里得算法：

穷举法：

更相减损法：

Stein算法：

在这里插入图片描述
四、主要代码（2.0.0版）

/* *FileName: Test1.cpp *Author: Qixiang.Su *e-mail: @.com *Version: 2.0.0 *Date: 2019.3.10 *Description: 求两个正整数的最大公约数和最小公倍数 * 理解各种算法求解过程 *History: 1.Date: 2019.3.10 Author: Elf.苏洛曦 Modification: Create project 2.Date: 2019.3.12 Author: Elf.苏洛曦 Modification: 1.0.0版 3.Date: 2019.3.14 Author: Elf.苏洛曦 Modification: 2.0.0版 / #include 
     #include 
     using namespace std; int t1, t2, s, w; //辗转相除法求最大公约数函数 int divisor(int a, int b) { 
    int temp; //比较两个数的大小，值大的数为a，值小的数为b if (a < b) { 
    temp = a; a = b; b = temp; } //求余 while (b != 0) { 
    temp = a % b; a = b; b = temp; } return a; } //求最小公倍数 int multiple(int a, int b) { 
    int divisor(int a, int b); int temp; temp = divisor(a, b); return(a * b / temp); } //函数递归调用求最大公约数 int gcd(int a, int b) { 
    if (a % b == 0) { 
    return b; } else { 
    return gcd(b, a % b); } } //穷举法求最大公约数 int divisor1(int a, int b) { 
    int temp; temp = (a > b) ? b : a; //求较小值 while (temp > 0) { 
    if (a % temp == 0 && b % temp == 0) { 
    break; } else { 
    temp--; } } return (temp); } //穷举法求最小公倍数 int multiple1(int a, int b) { 
    int p, q, temp; p = (a > b) ? a : b; //求两数中的最大值 q = (a > b) ? b : a; //求两数中的最小值 temp = p; while (1) { 
    if (p % q == 0) { 
    break; } else { 
    p += temp; } } return (p); } //更相减损法求最大公约数 int gcd1(int a, int b) { 
    int i = 0, temp, x = 0; while (a % 2 == 0 && b % 2 == 0) { 
    //m,n有公约数2时 a /= 2; b /= 2; i += 1; } //a,b的值互换 if (a < b) { 
    temp = a; a = b; b = temp; } while (x) { 
    x = a - b; a = (b > x) ? b : x; b = (b < x) ? b : x; if (b == (a - b)) { 
    //差和减数相等 break; } } if (i == 0) { 
    return b; } else { 
    return (int)pow(2, i)*b; } } //输入正整数 int setNumber() { 
    int a; cout << "请输入正整数：" << endl; cin >> a; if (a <= 0) { 
    cout << "您输入的数值不符合规范（要求：正整数)" << endl; setNumber(); } else { 
    return a; } } //Stein算法函数非递归调用求最大公约数 int Stein(unsigned int x, unsigned int y) { 
    int factor = 0; //计数器 int temp; //大数赋给x，小数赋给y if (x < y) { 
    temp = x; x = y; y = temp; } if (0 == y) { 
    return 0; } while (x != y) { 
    if (x & 0x1) { 
    if (y & 0x1) { 
    //x,y都为奇数 y = (x - y) >> 1; x -= y; } else { 
    // x为奇数，y为偶数 y >>= 1; } } else { 
    if (y & 0x1) { 
    // x为偶数，y为奇数 x >>= 1; if (x < y) { 
    temp = x; x = y; y = temp; } } else { 
    //x,y均为偶数 x >>= 1; y >>= 1; ++factor; } } } return (x << factor); } //Stein算法函数递归调用求最大公约数 int gcd2(int u, int v) { 
    if (u == 0) { 
    return v; } if (v == 0) { 
    return u; } if (~u & 1) { 
    if (v & 1) { 
    return gcd2(u >> 1, v); } else { 
    return gcd2(u >> 1, v >> 1) << 1; } } if (~v & 1) { 
    return gcd2(u, v >> 1); } if (u > v) { 
    return gcd2((u - v) >> 1, v); } return gcd2((v - u) >> 1, u); } //获得两个正整数的最大公约数和最小公倍数 void getResult() { 
    s = setNumber(); w = setNumber(); int count; cout << "请输入你想循环的次数：" << endl; cin >> count; clock_t strat = clock(); for (int i = 0; i < count; i++) { 
    t1 = divisor(s, w); t2 = multiple(s, w); } clock_t end = clock(); cout << "辗转相除法函数嵌套调用所求结果:" << endl; cout << s << "和" << w << "的最大公约数为：" << t1 << endl; cout << s << "和" << w << "的最小公倍数为：" << t2 << endl; cout << "运行" << count << "次所花时间为：" << end - strat << "毫秒"<<endl; cout << endl; clock_t strat1 = clock(); for (int i = 0; i < count; i++) { 
    t1 = gcd(s, w); t2 = multiple(s, w); } clock_t end1 = clock(); cout << "辗转相除法函数递归调用所求结果:" << endl; cout << s << "和" << w << "的最大公约数为：" << t1 << endl; cout << s << "和" << w << "的最小公倍数为：" << t2 << endl; cout << "运行" << count << "次所花时间为：" << end1 - strat1 << "毫秒" << endl; cout << endl; clock_t strat2 = clock(); for (int i = 0; i < count; i++) { 
    t1 = divisor1(s, w); t2 = multiple1(s, w); } clock_t end2 = clock(); cout << "穷举法所求结果:" << endl; cout << s << "和" << w << "的最大公约数为：" << t1 << endl; cout << s << "和" << w << "的最小公倍数为：" << t2 << endl; cout << "运行" << count << "次所花时间为：" << end2 - strat2 << "毫秒" << endl; cout << endl; clock_t strat3 = clock(); for (int i = 0; i < count; i++) { 
    t1 = gcd(s, w); t2 = multiple(s, w); } clock_t end3 = clock(); cout << "更相减损法所求结果:" << endl; cout << s << "和" << w << "的最大公约数为：" << t1 << endl; cout << s << "和" << w << "的最小公倍数为：" << t2 << endl; cout << "运行" << count << "次所花时间为：" << end3 - strat3 << "毫秒" << endl; cout << endl; clock_t strat4 = clock(); for (int i = 0; i < count; i++) { 
    t1 = Stein(s, w); t2 = multiple(s, w); } clock_t end4 = clock(); cout << "Stein算法非递归调用所求结果:" << endl; cout << s << "和" << w << "的最大公约数为：" << t1 << endl; cout << s << "和" << w << "的最小公倍数为：" << t2 << endl; cout << "运行" << count << "次所花时间为：" << end4 - strat4 << "毫秒" << endl; cout << endl; clock_t strat5 = clock(); for (int i = 0; i < count; i++) { 
    t1 = gcd2(s, w); t2 = multiple(s, w); } clock_t end5 = clock(); cout << "Stein算法递归调用所求结果:" << endl; cout << s << "和" << w << "的最大公约数为：" << t1 << endl; cout << s << "和" << w << "的最小公倍数为：" << t2 << endl; cout << "运行" << count << "次所花时间为：" << end5 - strat5 << "毫秒" << endl; cout << endl; } int main() { 
    getResult(); system("pause"); }

五、调试和测试
1.在1.0.0版本中
一次进行测试，出现了错误，如下图：

在编译时没有错误，在运行过程也无错误，在结果中，穷举法的结果与其他的不同。对穷举法进行单独测试，结果如下：

与实际不符，结果也是错误的，通过逐语句调试
在这里插入图片描述
发现求最大公约数中temp的值存在异常，通过仔细检查，将while(temp > 0)写成了while(temp = 0)，嵌套出现了层次错误。改正后，运行结果如下：

最大公约数正确，最小公倍数错误，对求最小公倍数的函数进行逐语句后
在这里插入图片描述
p和q的值相同，存在错误，仔细检查后发现将(a>b)写成了(a

2. 2.0.0版本
在2.0.0版本中取消了1.0.0版本中的输入要求数的对数，增加了对一组数据想要循环次数的输入，这样免去了测试时手动输入多组数据的程序。

通过监视，查看各个变量的变化情况,如下图：
在这里插入图片描述