C++ 最大公约数

Question

我是 C++ 的新手，正在尝试创建一个函数来实现欧几里得算法，returns 是两个整数输入的最大公约数。

我目前采用的方法总是崩溃 - 你能帮我理解为什么吗？

int main() {    
    int a = 0;
    int b = 0;

    cin >>  a;
    cin >> b;

    do {
        if ( a > b ) a = a % b;
        else if ( a < b ) b = b % a;
        else if ( a == b ) break;
    } while ( ( a || b ) != 0 ); 

    return 0;
}

谢谢，

大卫

Answer 1

您的条款 ( a || b ) != 0 不会如您所愿地解决。
你要做的是(a != 0) && (b != 0)
或者如 Cheers and hth. - Alf 所建议的那样 a && b.

Answer 2

while ( ( a || b ) != 0 );

这是错误的。应该是

while ( a != 0 && b != 0 );

附带说明一下，欧几里得算法可以简洁地递归实现：

int gcd(int a, int b)
{
   return b == 0 ? a : gcd(b, a%b);
}

Answer 3

你的 while 条件是错误的。你不能这样简化它。

while ( ( a || b ) != 0 );

它应该是这样的。

while ( ( a != 0 ) && ( b != 0 ) );

顺便说一句，您可以采用更简单的方法。像这样

int main() {

int a, b, r;

cin >> a;
cin >> b;

while ( b != 0) {
    r = a % b;
    a = b;
    b = r;
}

cout << "The GCD is " << a << endl;

}

还有另一种方法，它不需要对算法进行编码。只需使用 libstdc++ 算法库即可。 Libstdc++

Answer 4

让我们仔细看看你的代码，也许你很好奇 while ( ( a || b ) != 0 ) 做了什么？

我们现在应该评估 ( a || b ) != 0。在 C/C++ 中，评估从右到左开始，但 () 具有更高的优先级，因此在运行-time 我们将有：

bool r1 = a || b;  // intermediate result
bool r2 = r1 != 0;
while(r2);

步骤：

a

b

a || b 被评估为 true。
r1 将转换为整数
- true 变为 1
- false 变为 0
r1 != 0 被评估并得到一个布尔值（true 或 false）
while决定是否循环。

C++ 最大公约数

c++ Greatest Common Divisor

c++

algorithm

do-while

modulus