C++程序计算最大公约数

Question

我已经开始编写一个计算最大公约数的程序。这是我目前的代码：

#include <iostream>
#include <math.h>
using namespace std;
int getGCD(int a, int b)
{
    a = a % b;
    if (a == 0)
    {
        return b;
        b = b % a;
    }
    if (b == 0)
    {
        return a;
    }
}
int main()

{
    int x, y;
    cout << "Please enter two integers x and y, for GCD calculation" << endl;
    cin >> x >> y;
    cout << "The GCD of " << x << "and " << y << " is" << getGCD(x, y) << endl;
    return 0;
}

我经常在GCD中得到0分。我做错了什么？

- user964141

---

b = b % a; 永远不会执行 - Mikhail

检查代码中的“return b;”语句，问自己：如果之前已经告诉程序从该函数返回，那么程序如何执行“b = b % a;”这一行呢？ - dowhilefor

如果这是作业，你应该添加适当的标签 :) - Muad'Dib

为了好玩，查看在编译时评估的GCD算法（使用模板）：http://blog.emptycrate.com/node/279 - sehe

你的函数总是声称在一次调用后返回正确的结果，这个事实应该暴露出了某些问题。 - Kerrek SB

int g(int a, int b){ return b?g(b,a%b):a;} - Lefteris E

Answer 1

你应该通过循环来查找它，如果你能用一些方程式来描述算法，那可能会有所帮助。

但我看到你有两个问题，除非你在另一个循环内调用它。

在两种情况下都使用了返回语句，因此你只会执行一次。

此外，这部分内容没有意义，为什么在执行完“return”后修改“b”值呢？

          return b;

          b = b%a;

你应该使用递归来完成这个任务。顺便提一下，下面的链接介绍了使用递归欧几里得算法计算最大公约数：http://rosettacode.org/wiki/Greatest_common_divisor#Recursive_Euclid_algorithm

- James Black

---

递归不应该用于此。迭代查找最大公约数对于欧几里得（《几何原本》约公元前300年，第七卷，命题1和2）已经足够好了，而且对于你来说也足够好。 - Eric Postpischil

@EricPostpischil - 递归可以使解决方案更简单，但最终取决于OP想要做什么，我只是提出了我的观点，并附上了源链接以帮助。 - James Black

Answer 2

int getGCD(int a, int b) {

//这里我们需要检查如果b==0，则返回a

    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

欧几里得算法实现

- noelyahan

---

控制可能到达非void函数的末尾。 - Babken Vardanyan

应该将代码行“b = a % b”改为“a = a % b”，反之亦然。 - muhammedabuali