2

ユーザーに 3 つの数値を入力してから、再帰を使用している間、ユークリッドのアルゴリズムを使用してプログラムに GCD を計算させたいと考えています。

私のコードは現在、2 つの入力数値を実装しています。a と b の GCD を計算し、それを結果 d と呼ぶアプローチを理解しています。次に、3 番目の入力 (c) と d を使用して GCD を見つけ、基本的に Euclid のアルゴリズムをもう一度繰り返します。これをコードに実装する方法がわかりません。

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.

どんな助けや提案も大歓迎です！

4

2 に答える 2

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

と だけでgCdなく、任意の 2 つの引数を指定して関数を呼び出すことができることに注意してください。理解を深め、混乱を避けるために、次のように引数の名前を変更することをお勧めします。ab

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

したがって、最初に and で呼び出して、x = aandy = bの GCD を見つけaますb。結果を新しい変数に格納しますd。その後、 とのGCDx = dである を使用して再度呼び出します。したがって、3 つの数値すべての GCD が得られます。aby = c

于 2014-03-22T22:40:44.533 に答える
1

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
于 2014-03-22T22:55:47.607 に答える