Verständnisproblem Türme von Hanoi

Status
Nicht offen für weitere Antworten.
G

Guest

Gast
Hallo, ich habe einen interessanten Code zu den Türmen von Hanoi gefunden, nur leider verstehe ich ihn noch nicht ganz:

Die Implementierung der Stange:

Code:
import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;

/** Diese Klasse repraesentiert eine Stange, auf
  * der einzelne Scheiben aufgereiht werden koennen.
  **/
public class Stange {
  
  /** Die einzelnen Scheiben werden in einer Liste
    * abgelegt.
    **/
  private List<Scheibe> scheiben = new ArrayList<Scheibe>();
  
  /** Fuegt der Stange genau dann eine einzelne Scheibe  
    * hinzu, wenn nicht schon eine kleinere Scheibe auf 
    * der Stange sitzt.
    * @param scheibe die hinzugefuegte Scheibe
    * @return true, wenn das Einfuegen erfolgreich war
    **/
  public boolean fuegeEin(Scheibe scheibe) {
    // Test: haben wir versucht, null einzufuegen?
    if (scheibe == null)
      return false;
    // Test: ist die Stange leer?
    if (!scheiben.isEmpty()) {
      // Hole die oberste Scheibe aus der Liste
      Scheibe oben = (Scheibe) scheiben.get(0);
      // Vergleiche die Breiten der Scheiben
      if (oben.getBreite() < scheibe.getBreite()) 
        return false;
    }
    // Fuehre die Operation durch
    scheiben.add(0,scheibe);
    return true;
  }
  
  /** Entfernt das oberste Element vom Turm.
    * @return das oberste Element, null, falls
    * die Stange leer ist.
    **/
  public Scheibe entferne() {
    if (scheiben.isEmpty()) {
      return null;
    }
    return (Scheibe)scheiben.remove(0);
  }
  
  /** Gib die Hoehe des Turms aus 
    * @return die Anzahl der Scheiben, die auf der Stange
    * aufgereiht sind.
    **/
  public int getHoehe() {
    return scheiben.size();
  }  
  
  /** Gibt eine String-Repraesentation des Objektes zurueck.
    * @return eine textuelle Darstellung der Stange
    **/
  public String toString() {
    // Wir speichern das Ergebnis in einem StringBuffer zwischen
    StringBuffer res = new StringBuffer("||=");
    // ... und iterieren durch die Liste
    for (Iterator it = scheiben.iterator(); it.hasNext(); ) {
      res.insert(2,it.next());  // impliziter Aufruf von toString()
      res.insert(2,'=');
    }
    // Fertig :-)
    return res.toString();
  }  
}

Implementierung der Scheibe

Code:
import java.text.DecimalFormat;

/** Diese Klasse repraesentiert eine einzelne Scheibe,
  * die waehrend des Tuerme-von-Hanoi-Spieles hin- und
  * hergeschoben wird. 
  **/
public class Scheibe {
  
  /** Formatierungs-Objekt fuer die Breite */
  private final static DecimalFormat FORMAT = new DecimalFormat("00");
  
  /** Wie breit ist die Scheibe ? */
  private int breite;
  
  /** Konstruktor.
    * @param breite die Breite der Scheibe.
    **/
  public Scheibe(int breite) {
    this.breite = breite;
  }
  
  /** Liefert die Breite der Scheibe zurueck 
    * @return die Breite der Scheibe
    **/
  public int getBreite() {
    return breite;
  }  
  /** Gibt eine String-Repraesentation des Objektes zurueck.
    * @return eine textuelle Darstellung der Stange
    **/
  public String toString() {
    return "(" + FORMAT.format(breite) + ")";
  }
}

und Hanoi mit Algorithmus

Code:
/** Dieses Programm loest das Tuerme-von-Hanoi-Problem
  * und gibt die Loesung auf dem Bildschirm aus. 
  **/
  
public class Hanoi {
  
  /** Ein Zaehler fuer die Zuege */
  private int zaehler;
  
  /** Die drei Tuerme */
  private Stange[] stangen = {
    new Stange(),new Stange(),new Stange()
  };
  
  /** Konstruktor 
    * @param anzahl die Anzahl der Scheiben
    **/
  public Hanoi(int anzahl) {
    for (int i = anzahl; i > 0; i--) 
      stangen[0].fuegeEin(new Scheibe(i));
  }
  
  /** Liefert eine String-Darstellung des
    * aktuellen Zustandes.
    * @return die drei Stangen in textueller Darstellung
    **/
  public String toString() {
    StringBuffer res = new StringBuffer();
    res.append("Start:       ");
    res.append(stangen[0].toString());
    res.append('\n');
    res.append("Ziel:        ");
    res.append(stangen[1].toString());
    res.append('\n');
    res.append("Hilfsstange: ");
    res.append(stangen[2].toString());
    return res.toString();
  }
 
  /** main-Methode: Erhaelt die Anzahl der Scheiben als
    * Kommandozeilenparameter und startet den Algorithmus.
    **/
  public static void main(String[] args) {
    if (args.length != 1) {
      System.out.println("Korrekter Aufruf: Hanoi <Anzahl Scheiben>");
      return;
    }
    int anzahl = Integer.parseInt(args[0]);
    new Hanoi(anzahl).spiele();
  }  

  /** Der eigentliche (rekursive) Verschiebe-Algorithmus.
    * @param kleinste die kleinste zu verschiebende Scheibe
    * @param groesste die groesste zu verschiebende Scheibe
    * @param start index der Stange, von der wir starten
    * @param ziel index der Stange, auf die wir schieben
    */    
  private void rekursion(int kleinste,int groesste,int start,int ziel){
    // Falls kleinste == groesste ist, sind wir am Ende der
    // Rekursion (und koennen direkt verschieben)
    if ( kleinste == groesste ) {
      // Die eigentliche Verschiebung
      boolean ok = stangen[ziel].fuegeEin(stangen[start].entferne());
      assert ok;
      // Gib den Zustand der Tuerme aus
      System.out.println("Zug : " + (++zaehler));
      System.out.println(this);
      System.out.println();
    }
    // Andernfalls muessen wir etwas mehr tun    
    else { 
      // Schiebe die kleineren Scheiben auf einen anderen Turm
      rekursion(kleinste, groesste - 1, start, 3 - start - ziel);
      // Dann verschiebe die groesste Scheibe
      rekursion(groesste,groesste,start,ziel);
      // Danach schiebe die ganzen kleineren ebenfalls aufs Ziel
      rekursion(kleinste, groesste - 1, 3 - start - ziel, ziel);
    } 
  }

  /** Fuehre den "Tuerme von Hanoi"-Algorithmus durch */
  public void spiele() {
    if (zaehler > 0)
      return;
    System.out.println("Ausgangszustand:");
    System.out.println(this);
    System.out.println();
    rekursion(1,stangen[0].getHoehe(),0,1);
  }
  
}

Also dort läuft ja ein rekursiver Algorithmus ab, dass nur verschoben wird, wenn größter und kleinster identisch sind:
Mein generelles problem ist:
kleinster ist doch immer 1, oder?
Wie kann es dann sein , dass dann die scheiben 2 und 3 verschoben werden und nicht nur die kleinste und die größte:

weil generell wird doch nur verschoben, wenn kleinster und größter identisch sind
 
S

SlaterB

Gast
kleinster ist nicht immer 1, siehe Aufruf
// // Dann verschiebe die groesste Scheibe
// rekursion(groesste,groesste,start,ziel);
Zeile 74-75

da wird also etwas getrickst, die Benennung könnte man evtl. logischer bauen, aber hat auch ihren gewissen Sinn

das Programm fängt jedenfalls mit "verschiebe 1-3 von a nach b" an,
das wid dann nicht direkt verschoben weil 1 != 3 sondern stattdessen wird erst 1-2 an einen freien Platz (c) abgelagert,
dann 3 direkt verschoben und danach 1-2 zurück
 
G

Guest

Gast
ok danke schon einmal ,

zeile 73 macht mir immer noch etwas probleme:

also laut beschreibung sollen dort ja die kleineren zwischen verschoben werden:

dabei wird groeßte ja dauernd um 1 verkleinert, bis kleinste = größte ist und dann verschoben wird. also 1 = 1

wieso wird dann weiter gemacht?

wann wird kleinste mal auf 2 gesetzt, für mich sieht es aus dass kleinste dauernd den wert 1 bzw. beim rekursionaufruf vom größten zu verschiebenen, den größten wert, aber dazwischen kann ich nix erkennen.
 
musiKk

musiKk

Top Contributor
Turm von Hanoi ist ein ziemlich interessantes Problem fuer einen rekursiven Algorithmus. Man geht von einem Turm der Hoehe n aus, den es zu verschieben gilt. Aber man kann diesen Turm nicht verschieben, wenn n>1, darum vereinfacht man das auf einen Turm der Hoehe n-1 und verschiebt diesen auf die gleiche Weise. Hat man irgendwann einen Turm der Hoehe 1, kann dieser verschoben werden.
 
S

SlaterB

Gast
kleinste kann nur in Zeile 75 einen Wert != 1, also > 1 erhalten,

mit 73 wird die Rekursion soweit heruntergespielt bis nur noch kleinste 1 + größte 2 zu verschieben sind,
dann führt Zeile 73 zur Verschiebung von kleinste 1 + größte 1, was der kleinsten Scheibe entspricht und im Rekursionsaufruf zu Zeile 61 == true führt,
als nächstes wird dann in Zeile 75 größte, größte = 2 verschoben, was auch zu einer direkten Verscheiben (Zeile 61 == true) führt
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
X Verständnisproblem Call-By-Reference Java Basics - Anfänger-Themen 5
P JavaFX: Verständnisproblem bei ComboBox/ChoiceBox etc. Java Basics - Anfänger-Themen 9
T Verständnisproblem mit Assoziationen Java Basics - Anfänger-Themen 7
M Verständnisproblem der Rekursion bei Arrays Java Basics - Anfänger-Themen 8
A Erste Schritte Verständnisproblem Java Basics - Anfänger-Themen 5
S Verständnisproblem Aufgabe Java Basics - Anfänger-Themen 9
S Model View Controller: Verständnisproblem Java Basics - Anfänger-Themen 13
temi Verständnisproblem Class.forName() Java Basics - Anfänger-Themen 3
2 Verständnisproblem bei Anwendung von Lower Bounded Wildcards Java Basics - Anfänger-Themen 5
V Verständnisproblem Java Basics - Anfänger-Themen 22
L [Verständnisproblem] Array wird trotz void rückgabe verändert. Java Basics - Anfänger-Themen 5
A Verständnisproblem Ausgabe Do-While-Schleife Java Basics - Anfänger-Themen 3
J Verständnisproblem einer Methode Java Basics - Anfänger-Themen 20
M Konstruktur - Verständnisproblem Java Basics - Anfänger-Themen 4
C Postinkrement und println - Verständnisproblem Java Basics - Anfänger-Themen 8
T Verständnisproblem beim Vigenere-Verfahren Java Basics - Anfänger-Themen 2
Q MVC Verständnisproblem: Controller vs model.modelChanged() Java Basics - Anfänger-Themen 0
N Verständnisproblem InsertionSort. Java Basics - Anfänger-Themen 2
D Verständnisproblem Java Basics - Anfänger-Themen 2
B VerständnisProblem mit Beispielaufgabe aus Buch Java Basics - Anfänger-Themen 1
H Polymorphie Verständnisproblem Vererbung/Polymorphie Java Basics - Anfänger-Themen 4
FrankR2 Grundsätzliches Verständnisproblem: Java 32/64-bit; Windows 7/8, 32/64-bit-System Java Basics - Anfänger-Themen 5
S Verständnisproblem bei Interfaces Java Basics - Anfänger-Themen 6
V Verständnisproblem Java Basics - Anfänger-Themen 5
V Arrays-verständnisproblem Java Basics - Anfänger-Themen 4
M Collections HashSet verständnisproblem Java Basics - Anfänger-Themen 9
S Verständnisproblem einer Übungsaufgabe Java Basics - Anfänger-Themen 6
H Abstrakte Basisklasse Verständnisproblem! Java Basics - Anfänger-Themen 8
G Verständnisproblem mit swing Java Basics - Anfänger-Themen 6
F Methoden Cannot refer to a non-final variable.. verständnisproblem. Java Basics - Anfänger-Themen 7
P Verständnisproblem main Methode Java Basics - Anfänger-Themen 9
S Klassen Verständnisproblem Konstruktor Java Basics - Anfänger-Themen 7
I e.getMessage(); - Verständnisproblem Java Basics - Anfänger-Themen 6
lesni Vererbung Vererbung - Verständnisproblem Java Basics - Anfänger-Themen 2
M OOP Polymorphie/Vererbung Verständnisproblem Java Basics - Anfänger-Themen 2
J Verständnisproblem Methoden-Kettung Java Basics - Anfänger-Themen 3
A Vererbung Verständnisproblem bei Übung Java Basics - Anfänger-Themen 5
E Verständnisproblem Typkonvertierung Java Basics - Anfänger-Themen 4
S OOP Verständnisproblem Umsteiger Java Basics - Anfänger-Themen 22
C Array Verständnisproblem Java Basics - Anfänger-Themen 3
P White-Box-Test Verständnisproblem Java Basics - Anfänger-Themen 11
D : ? Operator -Verständnisproblem Java Basics - Anfänger-Themen 24
G Verständnisproblem: Exceptions Java Basics - Anfänger-Themen 17
L Eclipse verlangt "{" nach ";"... Verständnisproblem Java Basics - Anfänger-Themen 5
D charAt(i) verständnisproblem Java Basics - Anfänger-Themen 4
D Verständnisproblem Marken und Schleifen Java Basics - Anfänger-Themen 19
M Verständnisproblem bei Ternären Operanten bzw. Bedingungsoperator Java Basics - Anfänger-Themen 8
T Datentypen Verständnisproblem mit main Methode Java Basics - Anfänger-Themen 3
M Verständnisproblem Threads Java Basics - Anfänger-Themen 7
X Threads und synchronized - Verständnisproblem Java Basics - Anfänger-Themen 3
W ArrayLists: Verständnisproblem bei remove() Java Basics - Anfänger-Themen 2
B Verständnisproblem zu Swing und Methoden Java Basics - Anfänger-Themen 8
A Postinkrement-Verständnisproblem Java Basics - Anfänger-Themen 12
R Iterator Liste, Verständnisproblem Java Basics - Anfänger-Themen 4
1 Verständnisproblem mit Foreach Java Basics - Anfänger-Themen 4
B Verständnisproblem bei Vererbung Java Basics - Anfänger-Themen 3
W generisches Programmieren - Verständnisproblem Java Basics - Anfänger-Themen 4
A Verständnisproblem Nr 2 Java Basics - Anfänger-Themen 14
A Verständnisproblem Java Basics - Anfänger-Themen 6
A Array Verständnisproblem Java Basics - Anfänger-Themen 8
G Verständnisproblem --> JTree Java Basics - Anfänger-Themen 6
M Verständnisproblem mit der Klasse Thread Java Basics - Anfänger-Themen 10
N BufferedReader Verständnisproblem Java Basics - Anfänger-Themen 12
G Verständnisproblem: Code kompelieren und interpretieren Java Basics - Anfänger-Themen 3
S Polymorphie Verständnisproblem Java Basics - Anfänger-Themen 4
G Verständnisproblem Serverinput einlesen. Java Basics - Anfänger-Themen 4
J Array und Schleifen Verständnisproblem Java Basics - Anfänger-Themen 25
G Verständnisproblem Java Basics - Anfänger-Themen 4
N Verständnisproblem: Mehrere Objekte einer Klasse erstellen Java Basics - Anfänger-Themen 2
S SelectionListener + repaint().Verständnisproblem ;) Java Basics - Anfänger-Themen 7
V Verständnisproblem mit Abstrakten zu Konkreten Klassen Java Basics - Anfänger-Themen 7
A Problem mit der Stringgrösse, bzw Verständnisproblem? Java Basics - Anfänger-Themen 14
A Verständnisproblem mit ScrollPanel Java Basics - Anfänger-Themen 3
R Verständnisproblem mit Hibernate Java Basics - Anfänger-Themen 2
T Verständnisproblem mit equals() Java Basics - Anfänger-Themen 4
N datei byte für byte auslesen (verständnisproblem) Java Basics - Anfänger-Themen 2
T Verständnisproblem packages/import Java Basics - Anfänger-Themen 9
Chucky Lineare Listen Programm Verständnisproblem Java Basics - Anfänger-Themen 38
D Verständnisproblem Java Basics - Anfänger-Themen 6
S for Schleifen: Verständnisproblem Java Basics - Anfänger-Themen 15
T Vererbung von Attributen und Methoden, Verständnisproblem Java Basics - Anfänger-Themen 4
bernd while-Schleife: Verständnisproblem Java Basics - Anfänger-Themen 7
S verständnisproblem drucken Java Basics - Anfänger-Themen 11
G GridBagLayout: Verständnisproblem Java Basics - Anfänger-Themen 5
S Türme von Hanoi Java Basics - Anfänger-Themen 36
B Türme von Hanoi mit einer beliebigen aber gültigen Eingabe lösen Java Basics - Anfänger-Themen 5
S Rekursion Rückgabe - Türme von Hanoi Java Basics - Anfänger-Themen 16
K Türme von Hanoi - Rekursiv. Java Basics - Anfänger-Themen 1
C Türme von Hanoi - Anzhal der Züge Java Basics - Anfänger-Themen 1
D Türme von Hanoi in "Java ist auch eine Insel" Java Basics - Anfänger-Themen 4
D Türme von hanoi Java Basics - Anfänger-Themen 7
B Türme von Hanoi ausgabe Java Basics - Anfänger-Themen 2
shiroX OOP Türme von Hanoi - einfache grafische Ausgabe Java Basics - Anfänger-Themen 2
T Türme von Hanoi Java Basics - Anfänger-Themen 9
D > 3 Türme von Hanoi Java Basics - Anfänger-Themen 11
J Erste Schritte türme von hanoi verständnisprobleme Java Basics - Anfänger-Themen 6
B Türme von Hanoi - Iterator Java Basics - Anfänger-Themen 50
R Türme von Hanoi mit beliebiger Startposition Java Basics - Anfänger-Themen 5
X Türme von Hanoi - Iterativ Java Basics - Anfänger-Themen 8
X Turm von Haoi - 4 Scheiben 4 Türme Java Basics - Anfänger-Themen 11

Ähnliche Java Themen

Anzeige

Neue Themen


Oben