代码之家 › 专栏 › 技术社区 › TroutmasterJ

使用递归并实现欧几里德算法从用户处找到三个数字的GCD

greatest-common-divisor recursion algorithm java

2

TroutmasterJ · 技术社区 · 11 年前

我想让用户输入三个数字,然后让程序使用欧几里德算法计算GCD,同时使用递归。

我的代码现在实现了两个输入数字。我理解计算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);         
   }
}

真正让我头疼的是使用递归来解决我的问题。

到目前为止,我知道我需要实施:

System.out.println("Enter third number: ");
     int c = userInput.nextInt();

d = //Not sure here

//And then modify my recursion method to find GCD.

如有任何帮助或建议,将不胜感激!

2 回复 | 直到 11 年前

1

2

Gassa 11 年前

d = gCd (a, b);
System.out.println("GCD is: " + gCd(d, c));

请注意,您可以致电 gCd 函数,而不仅仅是 a 和 b 。为了更好地理解和减少混淆,您可能需要重命名其参数,如下所示:

 public static int gCd(int x, int y) {
     if(y == 0) {
         return x;
     }
     return gCd(y, x%y);
 }

所以,首先你用 x = a 和 y = b 查找的GCD 一 和 b 。将结果存储到新变量中 d 。之后,你用 x = d 这又是 一 和 b 和 y = c 这样你就得到了这三个数字的GCD。

2

1

Michael Yaworski 11 年前

可以迭代gcd方法以获得更大的一组数字的gcd。例如:

gCd(a, b, c) = gCd( gCd(a, b), c)

和

gCd(a, b, c, d) = gCd( gCd(a, b, c), d) 那么
gCd(a, b, c, d) = gCd( gCd( gCd(a, b), c), d)

简单、具体的解决方案:

System.out.println("GCD is: " + gCd( gCd(a, b), c) );

然而,如果您注意到,这里正在进行递归大堆整数作为输入。它适用于大小为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;
}

因此,要将其与代码联系起来:

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);

样本输入/输出:

Enter first number: 
12
Enter second number: 
18
Enter third number: 
30
GCD is: 6
GCD is: 6