0

我正在尝试编写一个简单的程序，它要求 5 个数字并输出它们的 GCD。我已经发现如何用两个数字用一个简单的方法做到这一点：

private static int gcd(int number1, int number2) //Finds GCD of 2 numbers.
{
    if(number2 == 0)
    {
        return number1;
    }
    return gcd(number2, number1%number2);
}

return 语句中的实际数学让我感到困惑，我不确定如何用 5 个甚至更多的数字写出来。我听说递归地执行此方法，例如使用 "gcd(a,b,c)=gcd(gcd(a,b),c)" 是最好的方法，但我想我在实际操作中遇到了麻烦有问题的数学逻辑。我只需要一个好的起点，真的，如何返回 3 个数字，然后是 4，然后是 5，等等。我想一旦我得到逻辑部分，我就会明白如何更容易地做到这一点。

4

2 回答 2

3

您应该将现有gcd(int, int)方法视为“黑匣子”；您的新gcd(int, int, int, int, int)方法可以在不知道它如何工作的情况下调用它。你会写：

private static int gcd(int a, int b, int c, int d, int e)
{
    return gcd(gcd(a, b), gcd(gcd(c, d), e));
}

或者，对于更通用的解决方案，您可以使用 Java 5 的 var-args 支持编写一个gcd(int, int...)采用任意正数参数的方法：

private static int gcd(int number1, int... otherNumbers)
{
    int result = number1;
    for(int number: otherNumbers)
        result = gcd(result, number);
    return result;
}

（请注意，在这两种情况下，此函数在编程意义上都不是“递归”的。前一种方法确实递归地嵌套了它的调用gcd(int, int)，但这并不是程序员所说的“递归”。gcd(int, int)但是，您的原始函数是递归的，因为它实际上调用了自己。）

于 2013-03-12T00:39:43.477 回答
3

这是关于最大公因数的物质观点。想一想尺寸为 m 和 n 的矩形地板。m 和 n 的 GCD 是可以完美贴合到该地板上的最大方形瓷砖的尺寸。

所以在你使用的算法中，你从两个数字开始，比如 8 和 10。然后你的程序用一个数字（比如 8）和两个数字的模数重复这个过程，即 2。这相当于斩波关闭 8x8 部分，因为我们知道进入剩余位的任何瓷砖也将适合该区域。我们剩下一个 2x8 的部分。重复这个过程，我们将得到 2 作为 GCD。我希望这能阐明您正在使用的算法的实际含义。

因此，将这个概念扩展到三个数的 GCD，我们可以说 m、n 和 p 的 GCD 是最大的立方块，可以放入尺寸为 mxnx p 的矩形棱柱中。为了找到这个 GCD，我们首先找到适合棱镜面之一的方形瓷砖。然后我们可以使用这个维度来切割一个横截面，可以说是棱镜，并取那个横截面的 GCD。当然，这可以扩展到我们无法精确可视化的更高维度！

于 2013-03-12T00:45:00.687 回答