Rekursion Rückgabe - Türme von Hanoi

S

SnowDragon

Mitglied
Hallo,
Ich habe die folgende Aufgabe:
Das Spiel „Türme von Hanoi“ besteht aus drei Stäben „Start“, „Mitte“ und „Ziel“, auf die mehrere gelochte Scheiben gelegt werden, alle verschieden groß. Zu Beginn liegen alle Scheiben auf „Start“, der Größe nach geordnet, mit der größten Scheibe unten und der kleinsten oben. Ziel des Spiels ist es, den kompletten Scheiben-Stapel von „Start“ nach „Ziel“ zu versetzen. Bei jedem Zug darf die oberste Scheibe eines beliebigen Stabes auf einen der bei den anderen Stäbe gelegt werden, vorausgesetzt, dort liegt nicht schon eine kleinere Scheibe. Folglich sind zu jedem Zeitpunkt des Spieles die Scheiben auf jedem Feld der Größe nach geordnet.

Laden Sie sich die Datei Hanoi.java herunter und implementieren Sie die rekursive Methode solve(). Als Parameter wird die Anzahl n der Scheiben, die zu Beginn des Spieles auf Stab A liegen, übergeben, sowie die Bezeichnungen der drei Stäbe „Start“, „Mitte“ und „Ziel“ als Zei- chenkette. Die Rückgabe soll ebenfalls als Zeichenkette erfolgen, die alle durchgeführten Züge beinhaltet. Jeder einzelne Zug soll durch Leerzeichen getrennt im Format ”Start->Ziel” ange- geben werden. Die Lösung für n=3, start=”A”, mid=”B” und final=”C” wäre beispielsweise dieZeichenkette”A->C A->B C->B A->C B->A B->C A->C”.

So, die Sache ist die: Ich habe die verlangte Methode nun fertig programmiert, nur krieg ich es nicht hin, dass das Ergebnis als String returned wird... Hoffe mir kann jemand helfen :)
Java:
public static String solve(int n, String start, String mid, String end) {
// Don't delete!! Tests will fail otherwise
// Pass object r to other function calls of solve (e.g. for recursion). Do not create other instances of object r
// Function solve(...) must be recursive, don't implement other recursive helper functions
//r.check();

// TODO

String erg = null;

if (n == 1){
System.out.println("Lege die oberste Scheibe von " +
"Turm " + start + " auf Turm " + end + ".");

return erg + (start + "->" + end);
}
else {
solve(n-1, start, end, mid);
solve(1, start, mid, end);
solve(n-1, mid, start, end);
}

return null;
}
 
Zuletzt bearbeitet von einem Moderator:
J

Joose

Top Contributor
So, die Sache ist die: Ich habe die verlangte Methode nun fertig programmiert, nur krieg ich es nicht hin, dass das Ergebnis als String returned wird... Hoffe mir kann jemand helfen :)

Code:
String erg = null;
  
        if (n == 1){
            System.out.println("Lege die oberste Scheibe von " +
               "Turm " + start + " auf Turm " + end + ".");
          
            return erg + (start + "->" + end);
        }
        else {
                solve(n-1, start, end, mid);
                solve(1, start, mid, end);
                solve(n-1, mid, start, end);
        }
      
        return null;
    }

Wenn n==1 gibst du doch auch den String erg zurück. Warum nicht am Ende der Methode ebenfalls?
Im else-Zweig rufst du zwar 3x die Methode "solve" auf den Rückgabewert dieser Methode ignorierst du aber und speicherst ihn nicht!
 
S

SnowDragon

Mitglied
Code:
public static String solve(int n, String start, String mid, String end) {
        // Don't delete!! Tests will fail otherwise
        // Pass object r to other function calls of solve (e.g. for recursion). Do not create other instances of object r
        // Function solve(...) must be recursive, don't implement other recursive helper functions
        //r.check();

        // TODO
       
String erg = null;
   
        if (n == 1){
            System.out.println("Lege die oberste Scheibe von " +
               "Turm " + start + " auf Turm " + end + ".");
           
            return erg + (start + "->" + end);
        }
        else {
                solve(n-1, start, end, mid);
                solve(1, start, mid, end);
                solve(n-1, mid, start, end);
        }
       
        return erg + (start + "->" + end);
    }

so funktioniert das leider auch nicht... am ende wird
nullA->C
ausgegeben statt
A->C A->B C->B A->C B->A B->C A->C
 
O

ob18axij

Mitglied
Hi,
bin so wie es aussieht auf derselben Uni und hab das gleiche Problem :/ (Nur mal so, habe gehört dass unser Prof es nicht mag wenn man einfach die Aufgaben o. Ä. per copy&paste ins Inet packt, deswegen auch das PW auf der HP ;D) Naja jedenfalls habe ich, wie schon gesagt, das gleiche Problem.. :(

Habe es schon mit dem "+"-Operator, .concat, und zuletzt per Stringbuilder probiert, und komme leider auch nicht weiter als du. Hier mal mein letzter Versuch per StringBuilder:

Wäre für jede Hilfe sehr dankbar!
 
Zuletzt bearbeitet von einem Moderator:
Robat

Robat

Top Contributor
Also:

einen StringBuilder braucht man in der Situation nicht.
Ihr macht folgendes:

Java:
public class TürmeVonHanoiSolver {

     private static String erg = "";

     public static void main(String[] args) {
           solve(5, "A", "B", "C");
     }

    private static solve(int n, String start, String mid, String end) {
     if(n ==1){
            erg += " " + start + "->" + end;
       }else{
                solve(n-1, start, end, mid);
                solve(1, start, mid, end);
                solve(n-1, mid, start, end);
       }

       return erg;
   }

}

Erklärung:
Bei euren Beispielen ist die Idee richtig aber ihr missachtet ein wichtiges Detail:
Ihr deklariert euren String / StringBuilder beide in der Methode solve(). Das bedeutet, dass euer String/StringBuilder jedes mal neu initialisiert wird und d.h. zurück gesetzt wird. Daher kommt auch nur A->C o.ä raus. Wenn man die Variable jetzt global deklariert, wird sie nicht jedes mal überschrieben.
Den return nach dem if(n==1) braucht man nicht zu setzten. Es reicht wenn man ihn ganz am Ende setzt.
Beachte: erg += " " + .. ist das selbe wie erg = erg + " " + ...
+= ist also noch eine verkürzte Schreibweise.

Output für n = 3:
Code:
A->C A->B C->B A->C B->A B->C A->C
 
O

ob18axij

Mitglied
Das bedeutet, dass euer String/StringBuilder jedes mal neu initialisiert wird und d.h. zurück gesetzt wird. Daher kommt auch nur A->C o.ä raus. Wenn man die Variable jetzt global deklariert, wird sie nicht jedes mal überschrieben.
Danke! :rolleyes:
Hab meinen Code überarbeitet und jetzt läufts mit 3 Scheiben :)
Kannst du mir noch nen kleinen Tipp geben, wie ich es schaffe dass auch für x Scheiben die korrekten Züge berechnet werden ? Momentan loopt bei mir nur der String:
Output für n = 3:
Code:
A->C A->B C->B A->C B->A B->C A->C
 
M

Meniskusschaden

Top Contributor
Wenn man die Variable jetzt global deklariert, wird sie nicht jedes mal überschrieben.
Den return nach dem if(n==1) braucht man nicht zu setzten. Es reicht wenn man ihn ganz am Ende setzt.
Ich denke, das müsste funktionieren (für solve() fehlt aber noch der Rückgabetyp). Ich bin mir aber nicht sicher, ob es ganz im Sinne der Aufgabenstellung ist, eine globale Variable zu verwenden. Das müsste doch zu Problemen führen, wenn man mehrere Berechnungsläufe parallel ausführen würde. Ich würde eigentlich eher erwarten, bei den rekursiven Aufrufen jeweils die Rückgabe von solve() zu verwerten.

Hab meinen Code überarbeitet und jetzt läufts mit 3 Scheiben :)
Kannst du mir noch nen kleinen Tipp geben, wie ich es schaffe dass auch für x Scheiben die korrekten Züge berechnet werden ? Momentan loopt bei mir nur der String:
Im Moment kann ich mir noch nicht richtig vorstellen, wie du es geschafft hast, einen Algorithmus zu erstellen, der bei drei Scheiben funktioniert und bei vier Scheiben nicht. Wenn du deine Lösung hier posten würdest, könnte dir vielleicht jemand helfen.;)
 
O

ob18axij

Mitglied
Im Moment kann ich mir noch nicht richtig vorstellen, wie du es geschafft hast, einen Algorithmus zu erstellen, der bei drei Scheiben funktioniert und bei vier Scheiben nicht. Wenn du deine Lösung hier posten würdest, könnte dir vielleicht jemand helfen.;)
Danke dir, die Antwort ist die folgende:
Ich denke, das müsste funktionieren (für solve() fehlt aber noch der Rückgabetyp). Ich bin mir aber nicht sicher, ob es ganz im Sinne der Aufgabenstellung ist, eine globale Variable zu verwenden. Das müsste doch zu Problemen führen, wenn man mehrere Berechnungsläufe parallel ausführen würde. Ich würde eigentlich eher erwarten, bei den rekursiven Aufrufen jeweils die Rückgabe von solve() zu verwerten.
Die Tests werden nacheinander aufgerufen und so die verschiedenen Lösungen zusammenaddiert. Also habe ich im Grunde genommen das gleiche Problem wie zuvor und das Problem tritt bei jedem korrekten Algorithmus auf.
 
Robat

Robat

Top Contributor
Ich bin mir aber nicht sicher, ob es ganz im Sinne der Aufgabenstellung ist, eine globale Variable zu verwenden. Das müsste doch zu Problemen führen, wenn man mehrere Berechnungsläufe parallel ausführen würde. Ich würde eigentlich eher erwarten, bei den rekursiven Aufrufen jeweils die Rückgabe von solve() zu verwerten.

Ich sag mal so, wenn man den Code versteht, solle es kein Problem sein die var wegzulassen und einfach den zurückgegbenen String auszugeben :D
 
J

Joose

Top Contributor
Also:

einen StringBuilder braucht man in der Situation nicht.
Ihr macht folgendes:
Eine statische String Variable braucht man genauso wenig ;) und ist auch nicht ratsam. Wenn die Methode solve mehrmals aufgerufen werden soll wer setzt diese statische Variable dann wo zurück?

Das Problem der beiden ist wie ich schon weiter oben gesagt habe, dass sie den Rückgabewert ihrer rekursiven Methode ignorieren!
Die Methode solve gibt einen String zurück, in der Methode solve ruft sich die Methode 3x selber auf. Der Rückgabewert keines Aufrufs wird irgendwo gespeichert .... hier wäre es vielleicht praktisch diese an die lokale Variable erg anzuhängen und dann erg zurückzugeben ;)

Java:
private static solve(int n, String start, String mid, String end) {
   String erg = "";
   if(n == 1) {
     erg = start + "->" + end + " ; ";
   } else {
     erg += solve(n-1, start, end, mid);
     erg += solve(1, start, mid, end);
     erg += solve(n-1, mid, start, end);
   }
   return erg;
}

Output für n = 3:
Code:
A -> C ; A -> B ; C -> B ; A -> C ; B -> A ; B -> C ; A -> C ;
Um die Ausgabe nachzuvollziehen der "StackTrace":
Java:
solve(3, "A", "B", "C");
   solve(2, "A", "C", "B");
     solve(1, "A", "B", "C");
       return "A -> C ; ";
     solve(1, "A", "C", "B");
       return "A -> B ; ";
     solve(1, "C", "A", "B");
       return "C -> B ; ";
     return "A -> C ; A -> B ; C -> B ; ";
   solve(1, "A", "B", "C");
     return "A -> C ; ";
   solve(2, "B", "A", "C");
     solve(1, "B", "C", "A");
       return "B -> A ; ";
     solve(1, "B", "A", "C");
       return "B -> C ; ";
     solve(1, "A", "B", "C");
       return "A -> C ; ";
     return "B -> A ; B -> C ; A -> C ; ";
   return "A -> C ; A -> B ; C -> B ; A -> C ; B -> A ; B -> C ; A -> C ; ";
 
JStein52

JStein52

Top Contributor
erg += solve(n-1, start, end, mid);
erg += solve(1, start, mid, end);
erg += solve(n-1, mid, start, end);

Müsste es nicht auch so gehen:
erg += solve(n-1, start, end, mid);
erg += solve(n-1, end, mid, start);

Da ergibt sich bei mir folgender Ablauf:
Bewege Scheibe 1 von der A zur B.
Bewege Scheibe 2 von der A zur C.
Bewege Scheibe 1 von der B zur C.
Bewege Scheibe 3 von der A zur B.
Bewege Scheibe 1 von der C zur A.
Bewege Scheibe 2 von der C zur B.
Bewege Scheibe 1 von der A zur B.

(ein Aufruf von solve weniger)
 
J

Joose

Top Contributor
Nein das würde nicht funktionieren -> A -> C ; B -> A ; C -> B ; A -> C ;
Da hast du dann folgenden Stacktrace:
Java:
solve(3, "A", "B", "C");
   solve(2, "A", "C", "B");
     solve(1, "A", "B", "C");
       return "A -> C ; ";
     solve(1, "B", "C", "A");
       return "B -> A ; ";
     return "A -> C ; B -> A ; ";
   solve(2, "C", "B", "A");
     solve(1, "C", "A", "B");
       return "C -> B ; ";
     solve(1, "A", "B", "C");
       return "A -> C ; ";
     return "C -> B ; A -> C ; ";
   return "A -> C ; B -> A ; C -> B ; A -> C ; ";
 
JStein52

JStein52

Top Contributor
Mhmmm, siehst du bei meiner Lösung einen Unterschied zu seiner, ausser dass ich die beiden rekursiven Aufrufe eben anders mache:

Code:
    static void move(int n, String fromPeg, String toPeg, String usingPeg) {
        if (n > 1) {
            move(n - 1, fromPeg, usingPeg, toPeg);
            System.out.printf("Bewege Scheibe %d von der %s zur %s.\n", n, fromPeg, toPeg);
            move(n - 1, usingPeg, toPeg, fromPeg);
        } else {
            System.out.printf("Bewege Scheibe %d von der %s zur %s.\n", n, fromPeg, toPeg);
        }
    }

    public static void main(String[] args) {
        move(3, "A", "B", "C");
    }

Und ich erhalte den oben geposteten Weg.
 
J

Joose

Top Contributor
Mhmmm, siehst du bei meiner Lösung einen Unterschied zu seiner, ausser dass ich die beiden rekursiven Aufrufe eben anders mache:
Ja jetzt sehe ich das es auch funktioniert ;)
Du hast zwischen den beiden Aufrufen von move noch eine Ausgabe. Diese hast du oben nicht gehabt, deswegen wars es für mich falsch.

Ja natürlich kann man den Aufruf von solve(1, start, mid, end); wegoptimieren indem man direkt die Ausgabe hinschreibt. Dann kommt man auch auf den richtigen Weg. Aber man hätte eben die Ausgabe doppelt stehen ;)
Ich würde lieber die Methode 3x rekursive aufrufen und nur 1x die Ausgabe stehen haben.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
A Rekursion in Baum und ArrayList als Rückgabe Java Basics - Anfänger-Themen 2
H Rekursion und Rückgabe Java Basics - Anfänger-Themen 11
Kirby_Sike Rekursion Java Basics - Anfänger-Themen 7
N for Schleife durch Rekursion ersetzen Java Basics - Anfänger-Themen 6
X Rekursion Java Basics - Anfänger-Themen 3
H Rekursion Java Basics - Anfänger-Themen 2
D Erste Schritte Rekursion Java Basics - Anfänger-Themen 13
M Rekursion Tage Ansteckung gesamte Bevölkerung Java Basics - Anfänger-Themen 15
M Java Rekursion Java Basics - Anfänger-Themen 9
G Java Rekursion Java Basics - Anfänger-Themen 5
J Rekursion Klausur Aufgabe Java Basics - Anfänger-Themen 2
N Rekursion Java Basics - Anfänger-Themen 18
M Verständnisproblem der Rekursion bei Arrays Java Basics - Anfänger-Themen 8
X Rekursion Rätsel Java Basics - Anfänger-Themen 4
N Klassen Rekursion mit Feldern von Objekten Java Basics - Anfänger-Themen 14
W Rekursion Java Basics - Anfänger-Themen 0
D Konsolenausgabe Zahlenfolge Rekursion Java Basics - Anfänger-Themen 3
J Ping Pong Methode mit Rekursion Java Basics - Anfänger-Themen 1
N Rekursion Java Basics - Anfänger-Themen 1
B Rekursion Basic Java Basics - Anfänger-Themen 15
O Rekursion Mergesort Java Basics - Anfänger-Themen 18
G Rekursion Java Basics - Anfänger-Themen 20
M Rekursion Java Basics - Anfänger-Themen 7
F Hilfe bei Rekursion... Java Basics - Anfänger-Themen 4
A Mit Rekursion Zufallszahlen erstellen und größte finden Java Basics - Anfänger-Themen 5
B Rekursion Wurzel Java Basics - Anfänger-Themen 39
O Rekursion ordentlich aufschreiben Java Basics - Anfänger-Themen 2
B Rekursion verstehen Java Basics - Anfänger-Themen 4
O Rekursion Java Basics - Anfänger-Themen 2
E Rekursion verstehen. Java Basics - Anfänger-Themen 4
E Rekursion Kisten befüllen Java Basics - Anfänger-Themen 10
E Rekursion verstehen Java Basics - Anfänger-Themen 2
O Rekursion, String Java Basics - Anfänger-Themen 8
N Invertierte Rekursion??? Java Basics - Anfänger-Themen 5
M Bitte um Hilfe bei Quellcode (Rekursion) Java Basics - Anfänger-Themen 6
T Rekursion Warum bricht meine Funktion nicht ab Java Basics - Anfänger-Themen 4
A Hilfe bei Rekursion,Ich verstehe nicht,wie funktioniert die Rekursion in der Methode "walk" Java Basics - Anfänger-Themen 13
L Rekursion im Baum Java Basics - Anfänger-Themen 9
E Pfade eines Baums angeben ohne Rekursion Java Basics - Anfänger-Themen 20
L Rekursion Baumknoten Java Basics - Anfänger-Themen 8
L Rekursion größtes Zeichen Java Basics - Anfänger-Themen 8
L Rekursion Modulo Java Basics - Anfänger-Themen 7
I Rekursion Java Basics - Anfänger-Themen 11
H Rekursion Java Basics - Anfänger-Themen 7
N Methoden zur Rekursion (catalansche Zahlen) Java Basics - Anfänger-Themen 4
S Frage zu Rekursion... Java Basics - Anfänger-Themen 15
N Java catalansche Zahlen (Rekursion) Java Basics - Anfänger-Themen 5
S Noch eine Frage zur Rekursion... Java Basics - Anfänger-Themen 11
S Frage zu einer Rekursion Java Basics - Anfänger-Themen 15
F Methoden Abbruchbedingung bei Rekursion Java Basics - Anfänger-Themen 2
Z Rekursion Primzahlen Java Basics - Anfänger-Themen 1
K Rekursion Verständnisfrage Java Basics - Anfänger-Themen 19
L Methoden Rekursion gibt alten Wert wieder Java Basics - Anfänger-Themen 37
M Rekursion Minimums Suche Java Basics - Anfänger-Themen 12
J Rekursion Java Basics - Anfänger-Themen 5
F Aufgabe Rekursion Binärer Baum Java Basics - Anfänger-Themen 15
N Rekursion Java Basics - Anfänger-Themen 2
B Rekursion - Übung Java Basics - Anfänger-Themen 2
B Problem beim grundsätzlichen Verständnis bei Rekursion mit 2-dimensionalen Array Java Basics - Anfänger-Themen 6
P Rekursion Java Basics - Anfänger-Themen 19
G Rekursion Beispiel Java Basics - Anfänger-Themen 3
M Rekursion schreiben Java Basics - Anfänger-Themen 16
A Rekursion Funktion in eine Iterativ Funktion umwandeln Java Basics - Anfänger-Themen 8
T Array Rekursion Java Basics - Anfänger-Themen 1
B lineare und schlichte Rekursion Java Basics - Anfänger-Themen 1
A Rekursion Java Basics - Anfänger-Themen 2
B Rekursion Java Basics - Anfänger-Themen 3
A Rekursion stoppt an der falschen Stelle Java Basics - Anfänger-Themen 4
A Lineare Rekursion Java Basics - Anfänger-Themen 6
P Hilfe zur Rekursion? Java Basics - Anfänger-Themen 2
B Rekursion Schneeflocke - Kurze Frage zur Methode Java Basics - Anfänger-Themen 11
L Rekursion Java Basics - Anfänger-Themen 4
kilopack15 Rekursion und Schleifen Java Basics - Anfänger-Themen 27
E Rekursion Java Basics - Anfänger-Themen 10
JavaXava rekursion nicht verstanden Java Basics - Anfänger-Themen 5
K Rekursion-Verständnisfrage Java Basics - Anfänger-Themen 4
E Methoden String wird in Rekursion nicht überschrieben Java Basics - Anfänger-Themen 2
T 2fach Rekursion. Java Basics - Anfänger-Themen 4
N Rekursion mit if-Anweisung Java Basics - Anfänger-Themen 10
K Methoden Zahlensysteme umwandeln mittels Rekursion Java Basics - Anfänger-Themen 5
H Rekursion Binäre Suche Java Basics - Anfänger-Themen 2
P Methoden Primzahltest mit Rekursion Java Basics - Anfänger-Themen 3
C Rekursion überführen in eine normale methode Java Basics - Anfänger-Themen 1
M Methoden Rekursion nachvollziehen Java Basics - Anfänger-Themen 4
C Rekursion Java Basics - Anfänger-Themen 6
B Rekursion - Variable initialisieren Java Basics - Anfänger-Themen 2
B Rekursion von Hand durchführen Java Basics - Anfänger-Themen 2
Z Rekursion Java Basics - Anfänger-Themen 4
C Rekursion auf einem Array(negative werte addieren) Java Basics - Anfänger-Themen 4
O Methoden rekursion Java Basics - Anfänger-Themen 7
P Rekursion mit 2 Aufrufen Java Basics - Anfänger-Themen 4
J Hilfe! Rekursion Java Basics - Anfänger-Themen 28
A Rekursion, Anzahl von Stellen ausgeben Java Basics - Anfänger-Themen 7
A Rekursion (anhand von Mergesort) nachvollziehen Java Basics - Anfänger-Themen 4
E Erste Schritte Verschiedene Anfängerfragen (Rekursion, Terminierung, Schleife, etc.) Java Basics - Anfänger-Themen 5
A Frage zur Rekursion Java Basics - Anfänger-Themen 8
D Klausur Vorbereitung: Listen, Rekursion, Bäume & Vererbung Java Basics - Anfänger-Themen 3
V Rekursion Java Basics - Anfänger-Themen 4
V Rekursion Java Basics - Anfänger-Themen 2
K Erste Schritte "return" Problem bei Rekursion Java Basics - Anfänger-Themen 8

Ähnliche Java Themen

Anzeige

Neue Themen


Oben