在 Java 中计算 gcd

Question

我自学 Java 所以我在加州大学伯克利分校做实验 CS 61B。我正在尝试编写一个 gcd 方法来使我的 toString 方法工作。

toString 方法以非简化形式打印分数。检查 toString 方法中的代码。它正在调用另一个方法 gcd 计算两个正整数的最大公约数 (GCD)。如果此方法正常工作，toString 将打印 Fractions in reduced 形式。我必须重写 gcd 的主体，以便它是正确计算 GCD 的递归函数。

这是我的 toString 方法：

public String toString() {
    int thisGcd = gcd(numerator, denominator);

    return (numerator / thisGcd + "/" + denominator / thisGcd);
  }

我的目标是编写正确的 gcd 函数，使 toString returns 成为不可约形式的 fracyion。这是我写的：

private static int gcd(int x, int y) {
    int div;
    if(x<0 || y<0){
        return -1;
    }
    else {

        if(x>y){
            div = y ;
        }
        else{
            div = x;
        }
        while( div !=0){
            if( (x % div==0 )&&(y % div == 0) ) {
                return div;

            }
            div --;

        }
    }

}

说明是关于使用以下伪代码编写递归 gcd 函数，但我不确定如何准确地实现它：

function gcd(a, b)
if b = 0
  return a
else
  return gcd(b, a mod b)

我的 gcd 函数有什么问题？我如何使我的工作？我将如何编写递归函数？

Answer 1

为什么不按照说明进行操作？

private static int gcd(int x, int y) {
  if (y == 0) {
    return x;
  }
  return gcd(y, x % y);
}

这个函数之所以叫尾递归，是因为最后一行是递归调用。尾递归函数很容易转换成while循环：

private static int gcd(int x, int y) {
  while (y != 0) {
    int tempX = x;
    x = y;
    y = tempX % y;
  }
  return x;
}

如您所见，转换使 while 循环谓词等于调用递归函数的谓词，而 while 循环的内容只是将 x 和 y 设置为与递归函数的输入相同。这通常是正确的（参见 wiki article）。

Answer 2

递归函数：

public int gcd(int a, int b)
{
 if(b == 0) return a;
 else return gcd(b, a % b);
}

Answer 3

这里有两个版本，一个简短：

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

另一个更接近您的说明：

    public static int gcd(int a, int b) {
      if (b == 0) 
        return a;
      else 
        return gcd(b, a % b);
    }

您的代码来自哪里？它看起来与说明完全不同。

这两个版本在语义上完全相同（我怀疑了一秒钟，因为带有自动装箱的三元运算符的奇怪行为......但是这里没有自动装箱的地方）：

  public static int gcd(int, int);
    Code:
       0: iload_1
       1: ifne          8
       4: iload_0
       5: goto          15
       8: iload_1
       9: iload_0
      10: iload_1
      11: irem
      12: invokestatic  #10                 // Method gcd:(II)I
      15: ireturn

  public static int gcd_verbose(int, int);
    Code:
       0: iload_1
       1: ifne          6
       4: iload_0
       5: ireturn
       6: iload_1
       7: iload_0
       8: iload_1
       9: irem
      10: invokestatic  #13                 // Method gcd_verbose:(II)I
      13: ireturn

Answer 4

您的 gcd 效率极低。除此之外，它缺少最后的 return 语句。假设，您的输入是 x = 0 和 y = 1。它将通过输入 < 0 的第一次检查，'div' 是 0 并且永远不会执行 whileloop。现在您在方法的末尾没有任何 return 语句。对于递归：

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

Answer 5

您问了一个由三部分组成的问题：

What is wrong with my gcd function ? How do I make mine work ? And how would I write the recursive function ?

最后一部分其他人回答的很好，所以我不回答那部分，但是关于你的另外两个问题：

What is wrong with my gcd function ?

第一件事是你的代码在每个状态下都没有 return，虽然逻辑上是这样，但是 java 会给你编译错误 error: missing return statement 所以你需要添加一个 return 值到你的函数的结尾，如果你只是想让它工作。但这不会解决您的问题，您的解决方案没有 return gcd(0,a) = a 的正确值来解决此问题，您只需要进行一些更改！

How do I make mine work ?

这部分是关于进行更改的，以下功能最接近您的答案，可以正常工作：

private static int gcd(int x, int y) {
    int div;
    if(x<0 || y<0){
        return -1;
    }
    else {

        if(x>y){
            div = x-y ;    //to fix the problem for zero input
        }
        else{
            div = y-x;     //to fix the problem for zero input
        }
        while( div !=0){
            if( (x % div==0 )&&(y % div == 0) ) {
                return div;

            }
            div --;
        }
        return div;    //the return statement so you dont get compile error and fix problem of zero input.
    }
}

但为什么要停在那里呢？你的函数根本没有时间效率，所以让我们做一些改变：

private static int gcd(int x, int y) {
    int div;
    int a;
    if(x<0 || y<0){
        return -1;
    }
    else {
        if(x>y){
            div = y;
            a = x-y ;
        }
        else{
            div = x;
            a = y-x;
        }
        while( div !=0){
            if( (x % div==0 )&&(y % div == 0) ) {
                return div;
            }
            a = a - div;
            if(a<div){
                int temp = div;
                div = a;
                a = temp;
            }
        }
        return a;
    }
}

虽然这不是我想要的，但它是可以从您的代码中提取出来的最高效的代码。

在 Java 中计算 gcd

Computing gcd in Java

java

algorithm

recursion

greatest-common-divisor