欧几里得算法

Question

在欧几里得算法计算gcd(x, y)的示例中，x始终大于y。这个条件重要吗？如果x小于y会发生什么？为什么即使输入的x值比y小，这个程序仍然返回正确的结果？

import acm.program.*;
/*
GCD Algorithm - greatest common divisor. "Euclid Algorithm approach"

 */
public class EuclidsAlgorithm extends ConsoleProgram {
    public void run(){
        println("This program is calculating the gratest common divisor (GCD) of two numbers.");
        int x = readInt("Enter 1st number: ");
        int y = readInt("Enter 2nd number: ");
        println("GCD(" + x + ", " + y + ") = " + gcd(x, y) );
    }

    private int gcd(int m, int k){
        int r = m % k;
        while (r != 0){
            m = k;
            k = r;
            r = m % k;
        }
        return k;
    }
}

- user6179055

---

不妨尝试使用x>y和x<y的输入进行调试。 - Andy Turner

旁注：在声明中添加 static ：private static int gcd（...）。 - Dmitry Bychenko

@DmitryBychenko 或许他还应该在方法中添加泛型，以防他想要处理长整型？为什么要在不必要的地方添加东西呢？ - Coderino Javarino

每次循环中都有一个变量移位：m <-- k <-- r=m'，交换变量的角色（取除法余数）。 - Joop Eggen

@Coderino Javarino：我个人认为这取决于情况。如果你不打算使用long等类型，可能不想从原始类型迁移到泛型（想象一下，你必须将gcd应用于一个包含百万个int对的数组）。 - Dmitry Bychenko

Answer 1

输入的顺序对结果没有影响。

如果m < k，那么r的初始值就是m；然后m接收k的值，而k接收r的值，即m。

因此，在循环的第一次迭代中，输入实际上被交换，以使得m > k。

显然，这样做第一次迭代来交换输入比不交换需要更长的时间：如果您能够以这样的方式调用该方法，使得输入已经按照m > k的顺序排列，则可以节省一些工作。

- Andy Turner

---

输出结果并不重要，但对于“软性”原因却很重要。例如，总是将较大的放在前面，因为没有人想展示第一步只是交换输入。如果必要的话，真正的实现通常会先进行交换，因为它们必须检查负数等内容，这比让循环来做更快，并且如果m>=k在循环中保持不变，则代码更容易理解。 - Matt Timmermans

谢谢@Matt。我已经在回答中添加了更多内容，但我不会直接复制您的评论 :) - Andy Turner

Answer 2

两个输入的顺序并不重要，因为对于：r = m%k。

if(m < k)
r = m
if(m == k)
r = 0
if(m > k)
r =  an integer number between 0 and k

而 r 是一个不断缩小的数字，直到找到一个可以同时被这两个数字整除的数字或者达到 0。

- nick zoum

Answer 3

它返回正确的结果，因为当你用一个较小的数除以一个较大的数时，模数是较小的数。

所以，例如，10%14将给你10。 因此，在你的逻辑中，如果我们以x为10和y为14的例子，仍然会得到2作为答案，这是正确的。 虽然在这段代码中，while循环将比如果我们将x作为14和y作为10传递运行多一次。

- Pushpinder Singh Grewal

Answer 4

其实这并不重要，原因如下：

GCD(x,y)
  if (y == 0 ) return x
return GCD(y,x%y)

假设 x = 3，y = 5

GCD(3,5) = GCD(5,3%5) = GCD(5,3) = GCD(3,2) .....

- hard coder