[Java] Türme von Hanoi Iterativ

Dieses Thema im Forum "Programmierung & Entwicklung" wurde erstellt von Straight-Edge, 28. November 2007 .

Schlagworte:
  1. 28. November 2007
    Türme von Hanoi Iterativ

    Hat jemand eine verständliche Version davon? Sei ein guter Pseudocode?

    Habe nur den bei Wikipedia gefunden, welcher aber nicht verständlich ist und einen in C++

    Code:
    #include <iostream>
    using namespace std;
    int main()
    {
    int n, x;
    
    cout << "How many disks?" << endl;
    cin >> n;
    
    for (x=1; x < (1 << n); x++)
    cout << "Move from pole " << (x&x-1)%3 << " to pole " << (((x|x-1)+1)%3) << endl;
    }
    
    C++ CodeC Code
    #include <iostream>
    using namespace std;
    
    int main()
    {
    int st[20][4],top,o=1,m=2,d=3,n, i,j,k;
    top=0;
    cout << "How many disks?" << endl;
    cin >> n;
    st[top][0]=o;
    st[top][1]=d;
    st[top][2]=m;
    st[top][3]=n;
    
    while(top>=0)
    {
    i=st[top][0];
    j=st[top][1];
    k=st[top][2];
    n=st[top][3];
    
    top=top-1;
    
    if(n<=1)
    cout << "Move " << i << " to " << j << endl;
    else if(n>1)
    {
    top=top+1;
    st[top][0]=k;
    st[top][1]=j;
    st[top][2]=i;
    st[top][3]=n-1;
    
    top=top+1;
    st[top][0]=i;
    st[top][1]=j;
    st[top][2]=0;
    st[top][3]=0;
    top=top+1;
    st[top][0]=i;
    st[top][1]=k;
    st[top][2]=j;
    st[top][3]=n-1;
    }
    }
    }

    ich kann aber kein c++

    kann mir da jemand helfen?
     
  2. 28. November 2007
    AW: Türme von Hanoi Iterativ

    Ich kenne mich mit Java zwar nicht aus, aber villeicht helfen dir folgende Links :

    jGuru: Your view of the Java universe
    Tower of Hanoi
    Java Source Code
     
  3. 28. November 2007
    AW: Türme von Hanoi Iterativ

    nee das sind alles rekursive aufrufe

    also die funktion ruft sich immer wieder neu auf. soll diese aber nicht
     
  4. 28. November 2007
    AW: Türme von Hanoi Iterativ

    Unser Info-Lehrer hat immer gesagt, als wir das Thema hatten, dass es keine komplett iterative Lösung für das Problem der Türme von Hanoi gäbe. Er war felsenfest davon überzeugt. Ich hatte dann auch den Code da rausgekramt, aber irgendwo war da ein Haken dran ... ich kann ihn aber gerne mal fragen ... wann brauchst du denn den Code?
     
  5. 28. November 2007
    AW: Türme von Hanoi Iterativ

    du möchtest den code also in java übersetzt haben?
    schick mir eine pm und wir sprechen drüber
     
  6. 28. November 2007
    AW: Türme von Hanoi Iterativ

    Habs mal kurz in Java umgesetzt, deinen C++ Code von oben. Sollte so klappen.

    Code:
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    public class Hanoi {
    
     public static void main(String[] args)throws IOException {
     int st[][] = new int[20][4];
     int top=0;
     int o=1;
     int m=2;
     int d=3;
     int n,i,j,k;
    
     System.out.println("How many disks?");
     String line = new String((new BufferedReader(new InputStreamReader(System.in))).readLine());
     n = Integer.parseInt(line);
    
     for (int x=1; x < (1 << n); x++){
     System.out.println("Move from pole " + (x&x-1)%3 + " to pole " + (((x|x-1)+1)%3));
     }
    
     st[top][0]=o;
     st[top][1]=d;
     st[top][2]=m;
     st[top][3]=n;
    
     while(top>=0)
     {
     i = st[top][0];
     j = st[top][1];
     k = st[top][2];
     n = st[top][3];
    
     top=top-1;
    
     if(n<=1)
     System.out.println("Move "+ i + " to "+ j);
     else if(n>1)
     {
     top=top+1;
     st[top][0]=k;
     st[top][1]=j;
     st[top][2]=i;
     st[top][3]=n-1;
     
     top=top+1;
     st[top][0]=i;
     st[top][1]=j;
     st[top][2]=0;
     st[top][3]=0;
     top=top+1;
     st[top][0]=i;
     st[top][1]=k;
     st[top][2]=j;
     st[top][3]=n-1;
     }
     }
     }
    }
    
    hier hab ich noch ne gut kommentierte iterative Türme von Hanoi Version gefunden:
    http://www-user.tu-chemnitz.de/~hsteff/progs/hanoi/hanoi_it.c
     
  7. 6. Dezember 2007
    AW: Türme von Hanoi Iterativ

    Ich denk mal, der folgende Quellcode dürfte es einigermaßen treffen:

    Code:
    ... und jetzt ganz ohne Rekursion:
    public static void move(int n, int a, int b, int c) {
    int [] stab = {a, c, b};
    int gesamtZahlDerBewegungen = 1; // 2 **n-1 berechnen
    for(int i = 0; i < n; ++i) {
    gesamtZahlDerBewegungen *= 2;
    }
    --gesamtZahlDerBewegungen;
    for(int aktuelleBewegung = 1;
    aktuelleBewegung <= gesamtZahlDerBewegungen;
    ++aktuelleBewegung) {
    int i = aktuelleBewegung;
    /* die zu bewegende Scheibe ist 1 + die höchste
    fruchtbarkeit von 2, die aktuelleBewegung teilt
    */
    int scheibe = 1;
    while (i % 2 == 0) {
    i /= 2;
    ++scheibe;
    }
    int bewegungenDerScheibe = i / 2;
    /* Eine Scheibe macht entweder einen einfachen
    oder einen doppelten Schritt im Zyklus 1231..,
    abhängig von der Parität von (n+scheibe)
    */
    int schritt = 2 - (n + scheibe) % 2;
    int von = (bewegungenDerScheibe * schritt) % 3;
    int nach = (von + schritt) % 3;
    System.out.println("move disk from " + stab[von]
    + " to " + stab[nach]);
    }
    }
     
  8. Video Script

    Videos zum Themenbereich

    * gefundene Videos auf YouTube, anhand der Überschrift.