Türme von Hanoi Frage

Question

Ich lese ein paar der Diskussionen über die Türme von Hanoi Problem durch. Ich verstehe die rekursive Lösung mit dem folgenden Code:

void Hanoi3(int nDisks, char source, char intermed, char dest) 
{ 
    if(nDisks == 1){ 
     cout << "Move the plate from " << source << " to " << dest << endl; 
    } 
    else{ 
     Hanoi3(nDisks - 1, source, dest, intermed); 
     cout << "Move the plate from " << source << " to " << dest << endl; 
     Hanoi3(nDisks - 1, dest, intermed, source); 
    } 
} 

Was ich brauche eigentlich zu tun, um ausgegeben irgendeine Art von „Abbildung“ des Turms bei jedem Schritt. Ich habe große Schwierigkeiten damit. Unser Kursleiter schlug vor, Stacks zu verwenden, um zu verfolgen, welche Disk in welchem ​​Tower ist, aber ich habe Probleme beim Ausgeben, da das Finden und Ausgeben der Werte in den Stapeln erfordert, dass die oberen Einträge entfernt und gelöscht werden. Sie verlieren sich, wenn ich es richtig verstehe.

So oder so, es führte mich zu einem gewissen Lösung, die wie folgt beginnt:

void Hanoi(int nDisks, stack<int> source, stack<int> intermed, stack<int> dest){ 
    if(nDisks == 1){ 
     dest.push(source.top()); 
     source.pop(); 
    } 
    else{ 
     Hanoi(nDisks - 1, source, dest, intermed); 
     dest.push(source.top()); 
     source.pop(); 
     Hanoi(nDisks - 1, dest, intermed, source); 
    } 
} 

int main() 
{ 

    int nDisks; 
    cout << "Enter the number of disks: "; 
    cin >> nDisks; 

    stack<int> source, intermed, dest; 

    for(int i = nDisks; i >= 1; i--){ 
     source.push(i); 
    } 

    Hanoi(nDisks, source, intermed, dest); 

    return 0; 
} 

mir bewusst bin, dass dies falsch ist. Ich bin nicht sicher, wo ein guter Platz wäre, Quelle mit den Diskettenzahlen zu füllen. Und ich gebe jedes Mal den gleichen Quellstapel weiter. Wenn mir jemand eine Richtung geben könnte, wäre das wirklich cool. Vielen Dank.

Answer 1

Geben Sie einen Verweis auf die Stapel:

stack<int>& 

Sehen Sie sich auch einen Vektor, anstatt ein Stapel mit, so dass Sie es laufen können den aktuellen Inhalt des Turms zu sehen.

Die Antwort von PigBen identifiziert auch einen Fehler in Ihrem Code, bei dem Sie die Festplatten nicht vom Zwischenturm zum Zielturm bewegen.

Answer 2

Übergeben Sie die Stapel als Referenz und ändern Sie die Reihenfolge, in der Sie sie im letzten Schritt übergeben, sodass Sie von intermed nach dest wechseln, wobei Sie Quelle als Zwischenprodukt verwenden.

Um den Stapel anzuzeigen, kopieren Sie es einfach und Pop von der Kopie.

Answer 3

Betrachten Sie Ihre Original-Code:

void Hanoi3(int nDisks, char source, char intermed, char dest) 
{ 
    if(nDisks == 1){ 
     cout << "Move the plate from " << source << " to " << dest << endl; 
    } 
    else{ 
     Hanoi3(nDisks - 1, source, dest, intermed); 
     cout << "Move the plate from " << source << " to " << dest << endl; 
     Hanoi3(nDisks - 1, dest, intermed, source); 
    } 
} 

es nicht richtig ist, so dass möglicherweise Grund schlägt Ihr Lehrer die Türme zu präsentieren. Wie Sie bemerken, ist ein std::stack ein guter Container, um die aktuellen Festplatten eines Turms zu repräsentieren, aber wie Sie auch bemerken, ist es nicht ganz einfach, an die Elemente eines std::stack zu gelangen, ohne sie zu knacken. Sie können sie platzen lassen und sie auf einen anderen Stapel schieben und zurückbewegen, aber das ist kompliziert und albern, ganz zu schweigen von dem, was für den allgemeinen Fall ineffizient ist. Deshalb hat std::stack ein protected Mitglied c, den zugrunde liegenden Container, auf den Sie zugreifen können, indem Sie von der Klasse ableiten.

Es gibt keine virtuellen Mitglieder in std::stack, so dass der einzige Zweck, ein protected Mitglied zu haben, ist, es ein wenig schwierig zu machen, um zu bekommen. Ich denke, es ist eine schlechte Designentscheidung. Aber es ist, was Sie haben, so,

#include <iostream> 
#include <string> 
#include <stack> 
#include <stddef.h> 
using namespace std; 

typedef ptrdiff_t Size; 
typedef Size  Index; 

class IntStack 
    : public stack<int> 
{ 
public: 
    Size count() const { return size(); } 
    int at(Index i) const { return c[i]; } 
}; 

class Hanoi 
{ 
private: 
    IntStack towers_[3]; 
    int   nDisks_; 

public: 
    Hanoi(int nDisks) 
     : nDisks_(nDisks) 
    { 
     for(int disk = nDisks; disk >= 1; --disk) 
     { 
      towers_[0].push(disk); 
     } 
    } 

    IntStack const& towers(Index i) const { return towers_[i]; } 
}; 

int main() 
{ 
    int const nDisksTotal = 2; 

    Hanoi puzzle(nDisksTotal); 

    for(Index i = 0; i < 3; ++i) 
    { 
     IntStack const& tower = puzzle.towers(i); 
     Size const  nDisks = tower.count(); 

     cout << "Tower " << i << ": ";   
     for(Index diskPos = 0; diskPos < nDisks; ++diskPos) 
     { 
      if(diskPos > 0) { cout << ", "; } 
      cout << tower.at(diskPos); 
     } 
     cout << endl; 
    } 
} 

Beachten Sie, dass dieser Code nur zeigt, wie Sie die Elemente dieser Stapel zugreifen können.

Die Anzeige kann viel ausgefallener gemacht werden, z.B. grafisch.

Ich schlage vor, Sie machen Ihre Solver-Funktion ein Mitglied der Klasse Hanoi. Und fügen Sie eine Mitgliedsfunktion hinzu, um den Puzzlezustand anzuzeigen. Später könnten Sie dies in einen Rückruf umwandeln, um eine grafische Benutzeroberfläche zu unterstützen.

EDIT: hm, ich sehe eine andere Antwort hat "die Lösung" für den Fehler gezeigt. Das entfernt die Lernerfahrung des OP und den ganzen Grund für die Anzeige der Türme. Diese Antwort bestätigte absichtlich nur, dass der Fehler real ist, und zeigte stattdessen, was das OP forderte, nämlich wie Stacks effizient angezeigt werden.

Beifall & hth.,