java - 使用递归并实现欧几里得算法来查找用户的三个数字的 GCD

Question

我想要求用户输入三个数字，然后让程序在使用递归的同时使用欧几里得算法计算 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.

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

Answer 1

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求 a 的 GCD和b 。将结果存储到新变量d中。之后，您再次使用 x = d 调用它。其 GCD 又为 a和b ，和y = c 。这样你就得到了所有三个数字的 GCD。