C++最大公约数

Question

我对C++非常陌生，正在尝试创建一个函数来实现欧几里得算法，该算法返回两个整数输入的最大公约数。

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

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;
}

感谢您的来信，

David

- David Loughnane

Answer 1

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

这个是错误的。正确应该是

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

顺便提一下，欧几里得算法可以通过递归方式简洁地实现：

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

- Armen Tsirunyan

---

这篇文章介绍了一些使用C++模板元编程实现的最大公约数算法，其中包括递归实现。 - Alexander Oh

Answer 2

你的术语( a || b ) != 0无法按照你的期望进行解决。
你需要这样写：(a != 0) && (b != 0)
或者像Cheers and hth. - Alf建议的那样，只需写a && b。

- FireRain

---

为什么不直接使用 a && b？ - Cheers and hth. - Alf

@Cheersandhth.-Alf 这可能对于新的C++学习者来说不太易读/易懂。 - frogatto

@abforce，你说得对，我不理解 a && b，能否解释一下？ - David Loughnane

当a和b都有非零值时，@DavidLoughnane a && b被评估为true。 - frogatto

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++

- Enpi

---

你也可以写成 while (b) 而不是 while (b != 0)，做出同样的程序。但无论哪种方式...欧几里得算法的使用非常棒！ - moldovean

Answer 4

让我们仔细看看你的代码，也许你想知道 while ( ( a || b ) != 0 ) 是做什么的？

现在我们需要评估 ( a || b ) != 0。在 C/C++ 中，评估从右到左开始，但是 () 的优先级更高，因此在运行时我们会有：

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 决定是否循环执行。

- frogatto