türme von hanoi mit stack lösen

sigint

hallo,

könnte mir jemand weiterhelfen bei der folgenden aufgabe?

Das bekannte Problem der Türme von Hanoi soll mit Hilfe eines Stapels der Container-Klasse stack der Standard Template Library gelöst werden. Der Stapel soll dazu einen Vektor (aus der Container-Klasse vector der Standard Library) aufnehmen der in

- der 1. Komponente die Anzahl der Scheiben aus dem sich der Turm zusammensetzt enthalten. Die Anzahl der Scheiben wird dem Programm über Konsoleneingabe (argv[]) mitgeteilt.
- der 2. Komponente beim Start die Podest-Nr. 1 enthält.
- der 3. Komponente beim Start die Podest-Nr. 2 enthält.
- der 4. Komponente beim Start die Podest-Nr. 3 enthält.

Das weitere Vorgehen zur Lösung des Problems besteht in dem angepassten Vertauschen der Zahlenwerte in den Komponenten des in dem Stapel abzulegenden Vektors.

Gib das zugehörige C++-Programm (nur ein Hauptprogrammabschnitt ist nötig), das die Lösung des Problems Türme von Hanoi realisiert.

danke im voraus

gruß sigint

THX 1138

Wo klemmts denn?

sigint

ich weiß nicht nach welchem muster ich die elemente ordnen soll, denn rekursiv ist das ohne funktion die sich aufrufen kann ein bisschen komisch. nach welcher reihenfolge soll ich die elemente denn runterpoppen bzw. wieder hochpushen?

Du mußt Element 1, Element 2, Element 3 ... pushen
und
... Element 3, Element 2, Element 1 poppen

oder was meinst du?

sigint

es kommt mir auf die reihenfolge des pushens und poppens an, da liegt mein problem.
hat niemand ein codebeispiel bei der hand?

wäre echt super

könntest du es rekursiv? beim dfunktionsaufruf werden auch nur die parameter auf den stack gepushed und am ende wieder runter

Werner Salomon

Endlich mal wieder eine kleine interessante Programmieraufgabe .. die Fragestellung ist interessant. Ich kannte das bisher noch nicht.

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>    // swap

const std::size_t VON = 1;
const std::size_t UEBER = 2;
const std::size_t NACH = 3;
const std::size_t ANZ = 0;

int main()
{
    using namespace std;

    vector< int > zug(4);
    zug[VON] = 1; zug[UEBER] = 2; zug[NACH] = 3; // Podest#'n initialisieren
    cout << "Turm von Hanoi: Bringe den Turm von Podest 1 nach 3" << endl;;
    cout << "Anzahl der Scheiben des Turms: ";
    cin >> zug[ANZ];

    // -- lösen
    stack< vector< int > > st;
    if( zug[ANZ] > 0 ) st.push( zug );
    while( !st.empty() )
    {
        zug = st.top();  st.pop(); // Zug vom Stack nehmen
        if( zug[ANZ] == 1 )
            cout << "Scheibe von " << zug[VON] << " nach " << zug[NACH] << endl;
        else
        {
            // -- Falls der Turm mehr als eine Scheibe hat, Problem in drei Schritte zerlegen
            // 3.) Turm-1 von 'UEBER' nach 'NACH'
            --zug[ANZ];
            vector< int > tmp = zug;
            swap( tmp[VON], tmp[UEBER] ); 
            st.push( tmp );
            // 2.) 1 Scheibe von 'VON' nach 'NACH'
            tmp = zug;
            tmp[ANZ] = 1; 
            st.push( tmp );
            // 1.) Turm-1 von 'VON' nach 'UEBER'
            tmp = zug;
            swap( tmp[UEBER], tmp[NACH] ); 
            st.push( tmp );
        }
    }
    return 0;
}

Gruß
Werner