最大公约数

Question

我试图找到两个整数的最大公约数.但我不明白我的代码有什么问题:

public class Main {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);

        int a = s.nextInt();
        int b = s.nextInt();

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

        if (a == 0) {
            System.out.println(b);
        } else {
            System.out.println(a);
        }
    }
}

Answer 1

只是改变

a != 0 | b != 0

至

a != 0 && b != 0

因为你的版本将工作,即使a或b等于0.但是你需要退出循环,当其中一个等于0. && - 更好而且因为在你的情况下你不需要检查右手操作符,如果左边等于0

Answer 2

如果我们理解核心逻辑,则更容易计算GCD.尝试了解我们需要做什么,以及在实施程序之前我们将如何做.

我们试图找到的是将a和b分开的最大数字.

所以问题出现了我们将如何去做.我们像你一样做一个循环,但对于这种情况,我们最初假设a大于b.

第一步是启动循环,而计算没有完成.在我们的情况下,我们必须在两个数字中的任何一个变为零时停止.

while (a != 0 && b != 0)
{
    // Do the calculation here.
}

现在我们必须编写计算.我们假设a大于b或两者相等.

我们保持对分配的剩余一个除以b到一个.

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

这使解决方案只有一半正确,我们将不得不处理另一种情况,即当b大于a时.之所以出现这种情况是有的组迭代后,会变得小于b,这将导致一个被设置为0.

因此,当a小于b时,让我们对另一种情况做同样的解决方案.

while (a != 0 && b != 0)
{
    if (a > b)
        a = a % b;
    else
        b = b % a;
}

这就是你想要实现的目标.非零值将是解决方案.

让我们不要停在这里,看看为什么你当前的版本不起作用.你有这个条件.

你的条件是:

a != 0 | b != 0

在这里,您在两个布尔值之间使用逐位运算符OR,如下所示.假设a和b中的任何一个为零.

情况1:

a != 0 => true
b != 0 => false

true | false => true

案例2:

a != 0 => false
b != 0 => true

false | true => true

因此,正如您在上述情况中所看到的那样,它继续循环直到两者都变为零,因此您将始终报告为G​​CD为零.

希望这可以帮助.