Java 基础：寻找最大公因数

Basic Java: Finding the Greatest Common Factor

提问by user2799775

I need to create a program that finds the greatest common factor of two user entered numbers using this formula:

我需要创建一个程序，使用以下公式找到两个用户输入数字的最大公因数：

gcd(x, y) = gcd(x – y, y) if x >= y and gcd(x, y) = gcd(x,y-x) if x < y.

gcd(x, y) = gcd(x – y, y) 如果 x >= y 并且 gcd(x, y) = gcd(x,yx) 如果 x < y。

For example: gcd(72, 54) = gcd(72 – 54, 54) = gcd(18, 54)Since 72 > 54, we replace 72 with 72 – 54 = 18 and continue the loop with the new values

例如： gcd(72, 54) = gcd(72 – 54, 54) = gcd(18, 54)由于 72 > 54，我们将 72 替换为 72 – 54 = 18 并使用新值继续循环

Iteration 2: gcd(18, 54) = gcd(18, 54 – 18) = gcd(18, 36) Since 18 < 54, we replace 54 with 54 – 18 = 36 and continue the loop with the new values

迭代 2： gcd(18, 54) = gcd(18, 54 – 18) = gcd(18, 36) 由于 18 < 54，我们用 54 – 18 = 36 替换 54 并用新值继续循环

Iteration 3: gcd(18, 36) = gcd(18, 36 – 18) = gcd(18, 18) Since 18 < 36, we replace 36 with 36 – 18 = 18 and continue the loop with the new values

迭代 3： gcd(18, 36) = gcd(18, 36 – 18) = gcd(18, 18) 由于 18 < 36，我们用 36 – 18 = 18 替换 36 并用新值继续循环

Iteration 4: gcd(18, 18) = gcd(18 – 18, 18) = gcd(0, 18) = 18 Since 18 >= 18, we replace the first 18 with 18 – 18 = 0 Since one of the values is 0 we do not continue the loop The nonzero value, 18, is the gcd.

迭代 4：gcd(18, 18) = gcd(18 – 18, 18) = gcd(0, 18) = 18 由于 18 >= 18，我们用 18 – 18 = 0 替换前 18，因为其中一个值是0 我们不继续循环 非零值 18 是 gcd。

Here's of the code I have so far:

这是我到目前为止的代码：

I'm getting the error "Illegal start of expression."

我收到错误“非法的表达开始”。

采纳答案by Hello_Everyone

First of all in your logic here:

首先在你的逻辑中：

do {
   int gcd1 = (num1-num2);
   System.out.println(gcd1 + "," + num2);

   }
   while (num1 != 0 && num2 != 0);
   return
}

You are just printing out gcd1 and num2 without updating num1 and num2.

您只是在不更新 num1 和 num2 的情况下打印出 gcd1 和 num2。

Also think how you can use recursion to tackle this problem.

还要考虑如何使用递归来解决这个问题。

If you insist on using a loop, here's the while loop logic:

如果你坚持使用循环，这里是 while 循环逻辑：

public static int greatestCommon(int a, int b)
        {
            while (a != 0 && b != 0)
            {
                if (a >= b)
                {
                    a = a - b;
                }
                else
                    b = b - a;
            }
            if (a == 0) return b;
            else return a;
        }

note that you do not need to use a do-while loop since there are situations when you do not need the substraction (if one or both of them are 0).

请注意，您不需要使用 do-while 循环，因为在某些情况下您不需要减法（如果其中一个或两个都为 0）。

回答by VladL

Use

用

Math.Max(num1, num2) - Math.Min(num1,num2)

instead of num1-num2

代替 num1-num2

回答by splungebob

You've already stated the answer (the algorithm) in your first sentence:

您已经在第一句话中说明了答案（算法）：

gcd(x, y) = gcd(x – y, y) if x >= y and gcd(x, y) = gcd(x,y-x) if x < y.

gcd(x, y) = gcd(x – y, y) if x >= y and gcd(x, y) = gcd(x,y-x) if x < y.

So how to translate that into code? The left-hand side of the equation is your method prototype, and the right-hand side is your method body:

那么如何将其翻译成代码呢？等式的左边是你的方法原型，右边是你的方法体：

public static int gcd(x, y)  // doesn't HAVE to be public or static
{
  gcd(x – y, y) if x >= y and gcd(x, y) = gcd(x,y-x) if x < y
}

but that code in the body doesn't compile, so you need to rewrite the body. Note that "and gcd(x, y) = ..."is a repetition of the method prototype and thus removed:

但是正文中的代码无法编译，因此您需要重写正文。请注意，这"and gcd(x, y) = ..."是方法原型的重复，因此被删除：

public static int gcd(x, y)
{
  if (x >= y)
  {
    return ... // you fill this in
  }
  else if (x < y)
  {
    return ... // you fill this in
  }
}

Note that the final "else-if" check really isn't necessary, but you teacher likely wants to see it there.

请注意，最后的“else-if”检查确实没有必要，但您的老师可能希望在那里看到它。

EDIT:

编辑：

Since this likely a classroom exercise in recursion, consider this working example taken from javax.swing.table.DefaultTableModel:

由于这可能是递归课堂练习，请考虑以下工作示例javax.swing.table.DefaultTableModel：

private static int gcd(int i, int j)
{
  return (j == 0) ? i : gcd(j, i%j);
}

SIDENOTE: Don't turn this in, as it obviously is not derived from the algorithm given to you, and your teacher will likely mark it wrong.

旁注：不要把它交出来，因为它显然不是从给你的算法中得出的，你的老师可能会记错。

Since you may not have learned the ternary operator syntax, I'll rewrite it as:

由于您可能没有学习过三元运算符的语法，我将其重写为：

private static int gcd(int i, int j)
{
  if (j == 0)
    return i;
  else
    return gcd(j, i%j);
}

This is an example of recursion, where under certain circumstances we can return a known value, but otherwise the method has to call itself again with a different set of parameters.

这是递归的一个例子，在某些情况下我们可以返回一个已知值，但否则该方法必须使用一组不同的参数再次调用自己。

EDIT 2:

编辑2：

Since an interative approach is needed in lieu of a recursive one, remember that all recursive methods can be rewritten using iteration (i.e., via loops).

由于需要一种交互方法来代替递归方法，请记住所有递归方法都可以使用迭代（即通过循环）重写。

Further reading:

进一步阅读：

Refactoring: Replace Recursion With Iteration

重构：用迭代代替递归