Mit Rekursion und Umsetzung von Euklid ' s Algorithmus zum finden GGT von drei zahlen vom Benutzer

Ich bin zu wollen, bitten Sie den Benutzer zur Eingabe drei zahlen und dann das Programm berechnet den GGT mittels Euklid ' s Algorithmus alle während der Verwendung der Rekursion.

Mein code richtig implementiert jetzt zwei zahlen einzugeben. Ich verstehe den Ansatz, die Berechnung der GCD von a und b, und nennen es Ergebnis d.... Dann mit dem Dritten Eingang (c) und d zu finden, der GCD und im wesentlichen wiederholen Euklid ' s Algorithmus wieder; ich bin nicht sicher, wie Sie diese umsetzen im code.

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

Den Teil, der wirklich werfen mich aus ist mit Rekursion zu lösen mein problem.

So weit ich weiß, brauche ich, um zu implementieren:

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

d = //Not sure here

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

Jede Hilfe oder Anregungen würde sehr geschätzt werden!

Die folgende Gleichheit, die Euch helfen können: gcd(a,b,c) = gcd(gcd(a,b),c)

InformationsquelleAutor TroutmasterJ | 2014-03-22

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

    Beachten Sie, dass Sie rufen Sie Ihren gCd - Funktion, mit der zwei beliebige Argumente, nicht nur a und b. Für ein besseres Verständnis und weniger Verwirrung, möchten Sie vielleicht umbenennen, um seine Argumente, wie die folgenden:

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

    Also, zuerst rufen Sie es mit x = a und y = b zu finden GCD von a und b. Speichern Sie das Ergebnis in einer neuen variable d. Danach rufen Sie es wieder mit x = d was wiederum GCD von a und b, und y = c. So erhalten Sie den GGT aller drei zahlen.

    Danke, das war das, was ich Malte in meinem Kopf, konnte aber nicht Recht bekommen es nach unten. Umbenennen mein argument-Variablen war ein guter Tipp.

    InformationsquelleAutor Gassa

  2. 1

    Den gcd-Methode Durchlaufen werden können, erhalten den gcd von einer größeren Menge von zahlen.
    Zum Beispiel:

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

    und

    gCd(a, b, c, d) = gCd( gCd(a, b, c), d) so dann

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

    Einfach, spezielle Lösung:

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

    Allerdings, wenn Sie feststellen, es ist die Rekursion geht. Ich habe eine Methode, die eine array von Ganzzahlen als input. Es wird für die Arbeit ein array der Größe drei, oder jeder Größe. Hier sind die Methoden:

    /* 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, in Beziehung zu deinem 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

    InformationsquelleAutor Michael Yaworski

Schreibe einen Kommentar