Java 使用递归和实现欧几里德算法从用户中找到三个数字的 GCD
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/22583517/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Using recursion and implementing Euclid's algorithm to find GCD of three numbers from user
提问by TroutmasterJ
I am wanting to ask the user to input three numbers and then have program calculate the GCD using Euclid's algorithm all the while using recursion.
我想要求用户输入三个数字，然后让程序一直使用 Euclid 算法计算 GCD，同时使用递归。
My code right now implements two input numbers. I understand the approach of calculating the GCD of a and b, and calling it result d. Then using the third input (c) and d to find the GCD and essentially repeating Euclid's algorithm again; I am not sure how to implement this in code.
我的代码现在实现了两个输入数字。我理解计算 a 和 b 的 GCD 并将其称为结果 d 的方法。然后使用第三个输入 (c) 和 d 来找到 GCD 并基本上再次重复欧几里德算法；我不确定如何在代码中实现这一点。
import java.util.Scanner;
public class RecursionDemo {
public static void main (String[] args) {
Scanner userInput = new Scanner(System.in);
System.out.println("Enter first number: ");
int a = userInput.nextInt();
System.out.println("Enter second number: ");
int b = userInput.nextInt();
System.out.println("GCD is: " + gCd(a, b));
}
public static int gCd(int a, int b) {
if(b == 0){
return a;
}
return gCd(b, a%b);
}
}
The part that is really throwing me off is using recursion to solve my problem.
真正让我失望的部分是使用递归来解决我的问题。
So far I know I need to implement:
到目前为止，我知道我需要实施：
System.out.println("Enter third number: ");
int c = userInput.nextInt();
d = //Not sure here
//And then modify my recursion method to find GCD.
Any help or suggestions would greatly be appreciated!
任何帮助或建议将不胜感激！
采纳答案by Gassa
d = gCd (a, b);
System.out.println("GCD is: " + gCd(d, c));
Note that you may call your gCdfunction with any two arguments, not just aand b. For better understanding and less confusion, you may want to rename its arguments, like the following:
请注意，您可以gCd使用任意两个参数调用您的函数，而不仅仅是a和b。为了更好地理解和减少混淆，您可能需要重命名其参数，如下所示：
public static int gCd(int x, int y) {
if(y == 0) {
return x;
}
return gCd(y, x%y);
}
So, first you call it with x = aand y = bto find GCD of aand b. Store the result into new variable d. After that, you call it again with x = dwhich is in turn GCD of aand b, and y = c. Thus you get the GCD of all the three numbers.
所以，首先你用x = aand调用它y = b以找到aand 的GCD b。将结果存储到新变量中d。之后，您再次调用它x = d，依次是aandb和 的GCD y = c。这样你就得到了所有三个数字的 GCD。
回答by Michael Yaworski
The gcd method can be iterated to obtain the gcd of a larger set of numbers. For example:
可以迭代 gcd 方法以获得更大的一组数字的 gcd。例如：
gCd(a, b, c) = gCd( gCd(a, b), c)
gCd(a, b, c) = gCd( gCd(a, b), c)
and
和
gCd(a, b, c, d) = gCd( gCd(a, b, c), d)so thengCd(a, b, c, d) = gCd( gCd( gCd(a, b), c), d)
gCd(a, b, c, d) = gCd( gCd(a, b, c), d)那么gCd(a, b, c, d) = gCd( gCd( gCd(a, b), c), d)
Easy, specific solution:
简单、具体的解决方案：
System.out.println("GCD is: " + gCd( gCd(a, b), c) );
However, if you'll notice, there is recursion going on. I've created a method that takes an arrayof integers as an input. It will work for an array of size three, or any size. Here are the methods:
但是，如果您会注意到，就会发生递归。我创建了一个将整数数组作为输入的方法。它适用于大小为 3 或任何大小的数组。以下是方法：
/* returns gcd of two numbers: a and b */
public static int gCd(int a, int b) {
if (b == 0) {
return a;
}
return gCd(b, a%b);
}
/* returns gcf of an array of numbers */
public static int gCd(int[] numbers)
{
int result = numbers[0]; // first number
for(int i = 1; i < numbers.length; i++) {
result = gCd(result, numbers[i]); // gcf of itself and next #
}
return result;
}
So, to relate it to your code:
因此，将其与您的代码相关联：
Scanner userInput = new Scanner(System.in);
System.out.println("Enter first number: ");
int a = userInput.nextInt();
System.out.println("Enter second number: ");
int b = userInput.nextInt();
System.out.println("Enter third number: ");
int c = userInput.nextInt();
// you can do this
System.out.println("GCD is: " + gCd( gCd(a, b), c) );
// or you can do this
int[] numbers = {a, b, c};
int d = gCd(numbers);
System.out.println("GCD is: " + d);
Sample input/output:
示例输入/输出：
Enter first number:
12
Enter second number:
18
Enter third number:
30
GCD is: 6
GCD is: 6
