Konsolen-Simulation des Algorithmus "Türme von Hanoi" unter Verwendung einer Klasse

[Cpp_Anfaeger]

Hallo,

die Algorithmen zu "Türme von Hanoi" sind nichts Neues. So habe ich mir einfach einen aus dem Netz genommen und versucht, daraus eine Visualisierung auf der Konsole zu erstellen.

Ehrlich gesagt, habe ich mir das auch noch nicht genauer angeschaut, was im rekrusiven Algorithmus passiert (Blackbox). Ich weiß nur, dass der Algorithmus seine Arbeit tut

Jetzt versuche ich, das Ganze objektorientiert zu gestalten, d.h. in eine Klasse zu packen.

Wie mache ich das am saubersten mit Klassen?

Programm zur Visualisierung:

//-----------------------------------------------------------------------
// PROGRAMMNAME     "TÜRME VON HANOI"
//
// BESCHREIBUNG     Rekursiver Funktionsaufrufe
//					Visualisierung auf der Konsole
//
//-----------------------------------------------------------------------
// ERSTELLT         am 02-Dec-2013
//-----------------------------------------------------------------------
// GETESTET         mit QtCreator 2.8.1 + Qt Libraries 5.1.1,
//                  MinGW 4.8 32Bit, WIN XP
//-----------------------------------------------------------------------
// STANDARD         nach C++11 ISO-Standard
//-----------------------------------------------------------------------
// GEÄNDERT         am 04-Dec-2013
//-----------------------------------------------------------------------

#include <cstdlib>      // wegen system("cls")
#include <iostream>
#include <windows.h>	// wegen Windows Handle für Konsolenposition
#include <iomanip>		// wegen setw()
#include <deque>        // Array-Ersatz

using namespace std;

//-----------------------------------------------------------------------
// Gotoxy,  Spalte 0 u. Zeile 0 ist ganz oben am Anfang
//-----------------------------------------------------------------------
void gotoXY(const int line, const int column) {

    COORD p;
    p.Y = line;		// Zeile
    p.X = column;	// Spalte
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), p);
}

//-----------------------------------------------------------------------
// Bestimme die Mitte von einer Scheibe (Länge/2)
//-----------------------------------------------------------------------
const int findSliceCenter(const string &str) {

    int center = ((str.length() + 1) / 2 ); // +1 da die Scheibe ungerade
    return center;
}

//-----------------------------------------------------------------------
// Scheiben von einem Turm runternehmen & auf anderen Turm draufwerfen
//-----------------------------------------------------------------------
void poppushTowers(deque<string> &start_tower,
                   deque<string> &destination_tower) {

    // kopiere die oberste Scheibe aus Startturm
    // und füge sie an Zielturm ein
    destination_tower.push_front(start_tower.at(0));
    start_tower.pop_front();	// lösche sie aus dem Startturm
}

//-----------------------------------------------------------------------
// Alle 3 Türme neuzeichnen
//-----------------------------------------------------------------------
void drawTowers(const deque<string> &tower_1,
                const deque<string> &tower_2,
                const deque<string> &tower_3) {

    system("cls");
    // Turm 1 neu zeichnen
    int start_column; // Start-Spalte
    for (int i=0; i<tower_1.size(); i++) {
        start_column = 14-findSliceCenter(tower_1.at(i));
        gotoXY(i+5, start_column);
        cout << tower_1.at(i);
    }
    // Turm 2 neu zeichnen
    for (int i=0; i<tower_2.size(); i++) {
        start_column = 42-findSliceCenter(tower_2.at(i));
        gotoXY(i+5, start_column);
        cout << tower_2.at(i);
    }
    // Turm 3 neu zeichnen
    for (int i=0; i<tower_3.size(); i++) {
        start_column = 70-findSliceCenter(tower_3.at(i));
        gotoXY(i+5, start_column);
        cout << tower_3.at(i);
    }
}

//-----------------------------------------------------------------------
// Rekursiver Funktionsaufruf zur Berechnung der Möglichkeiten
//-----------------------------------------------------------------------
static int g_schritt = 1;           // Schrittzähler, global wegen rekursiv

void pushSlices(int start,			// Startturm
                int destination,	// Zielturm
                int slice_counter,
                deque<string> &tower_1,
                deque<string> &tower_2,
                deque<string> &tower_3) {

    int free;	// Freier Turm

    if (slice_counter != 0) {

        free = 6 - start - destination;
        // rekursiver Aufruf zur Berechnung der Möglichkeiten
        pushSlices(start,
                   free,
                   slice_counter-1,
                   tower_1,
                   tower_2,
                   tower_3);
        gotoXY(1, 0);
        cout << g_schritt++ << ".)  " << "von Turm " << start
             << " -> Turm " << destination << endl;
        getwchar();
        // Simulationsteil: Bestimme Startturm u. Zielturm
        switch (start) {
            case 1:
                switch (destination) {
                    case 2:
                        poppushTowers(tower_1, tower_2); break;
                    case 3:
                        poppushTowers(tower_1, tower_3); break;
                }
                break;
            case 2:
                switch (destination) {
                    case 1:
                        poppushTowers(tower_2, tower_1); break;
                    case 3:
                        poppushTowers(tower_2, tower_3); break;
                }
                break;
            case 3:
                switch (destination) {
                    case 2:
                        poppushTowers(tower_3, tower_2); break;
                    case 1:
                        poppushTowers(tower_3, tower_1); break;
                }
        }
        // neu zeichnen
        drawTowers(tower_1, tower_2, tower_3);
        // erneuter rekursiver Aufruf der Funktion
        pushSlices(free,
                   destination,
                   slice_counter-1,
                   tower_1,
                   tower_2,
                   tower_3);
    }
}

//-----------------------------------------------------------------------
// Hauptfunktion
//-----------------------------------------------------------------------
int main() {

    // bei weiteren Scheiben einfach slice auffüllen
    string slice[6];
    slice[0] =          "***";
    slice[1] =        "*******";
    slice[2] =      "***********";
    slice[3] =    "***************";
    slice[4] =  "*******************";
    slice[5] ="***********************";
    // ......

    // 3 Türme deklarieren
    deque<string> tower_1;
    deque<string> tower_2;
    deque<string> tower_3;

    // Den ersten Turm von unten auffüllen
    for (int i=0; i<6; i++) {
        tower_1.push_back(slice[i]);
    }

    system("cls");

    // starte Simulation mit 6 Scheiben
    pushSlices(1, 3, 6, tower_1, tower_2, tower_3);
    getwchar();
    cout << endl;
    return 0;
}

[SeppJ]

Cpp_Anfaeger schrieb:

die Algorithmen zu "Türme von Hanoi" sind nichts Neues. So habe ich mir einfach einen aus dem Netz genommen und versucht, daraus eine Visualisierung auf der Konsole zu erstellen.

Schlechter Ansatz. Wie willst du lernen, wenn du immer nur kopierst und veränderst? Du brauchst Erfahrung, wie du selbstständig etwas erstellst! Dann verstehst du auch, was der Code macht und lernst zudem, fremde Codes zu verstehen (weil du die typischen Strukturen kennst, da du sie selber schon benutzt hast). Gerade die Türme von Hanoi sind doch mit Absicht so einfach, dass sie sich als Übungsaufgabe eignen, bei der niemand gezwungen sein sollte, abzuschreiben.

Wie mache ich das am saubersten mit Klassen?

Indem du erstmal den ganzen gezeigten Code vergisst. Den kannst du eventuell später mal anschauen, falls du noch den einen oder anderen Kniff brauchst.
Dann überlegst du dir, welche "Objekte unserer Vorstellungskraft" wohl an dem Problem beteiligt sind. Das sind dann gute Kandidaten für Objekte im Computermodell. Hier würden mir spontan einfallen: Die Scheiben, die Stäbe, die Gesamtheit der Stäbe (Seitenhieb: Wenn ich Java machen würde, würde ich hier auch so etwas wie "Verschiebung" oder "Lösung" als Objekt identifizieren ).

Dann überlegst du dir die Eigenschaften dieser Objekte, das was diese Objekte ausmacht. Spontan würde ich sagen, die Scheibe hat eine Größe. Ein Stab hat/ist eine (geordnete) Sammlung an Scheiben. Die Gesamtheit aller Stäbe ist eben dies, eine Sammlung von drei Stäben.

Dann überlegst du dir, ob das wirklich alles essentiell ist für die Problemstellung. Oft erkennt man dabei, dass man viel zu viele Klassen hat, die gar nicht so wichtig sind. Hier könnte man sich zum Beispiel praktisch alles sparen und einfach mit drei vector<int> oder stack<int> arbeiten, die die Problemstellung genau so gut einfangen, da es eben nicht so wichtig ist, ob die Scheibe wirklich eine Scheibe ist, da reicht auch jede andere Art von "Ding", die irgendwie den Begriff "größer" kennt. Genau das scheint im Originalcode der Fall zu sein. Aber da du hier ja ausdrücklich ins Details modellieren möchtest, ignoriere ich das mal und bleibe bei Scheiben und Stäben.^*

Dann überlegt man sich, was diese Objekte tun können müssen. Die Scheiben liegen eigentlich nur dumm rum. Eventuell können sie ihre Größe vergleichen (muss man mal sehen, ob man das braucht) oder ihre Größe preisgeben. Außerdem muss man natürlich eine Scheibe mit einer bestimmten Größe erstellen können. Auf einen Stab, kann man Scheiben drauftun oder runternehmen. Wenn man mehrere Stäbe hat (also das Gesamtsystem), so kann man im Rahmen dieses Gesamtsystems Scheiben von einem Stab auf einen anderen verschieben. Da du das alles grafisch darstellen willst, müssen die Objekte noch irgendwie ausgegeben werden. Da wir hier mal kein professionelles Spieledesign betreiben, bei dem Ausgabe und Logik getrennt werden, schlage ich mal einfach vor, dass die Stabsammlung alle ihre Stäbe sauber ausgibt, der Stab gibt alle seine Scheiben sauber aus, die Scheibe gibt sich selbst aus.

Dann gibt es abschließend noch die Gesamtlösung, diese ist irgendwie eine Funktion von Verschiebeaktionen und wegen der grafischen Ausgabe auch noch von Ausgabeaktionen nach jeder Verschiebung.

Damit ist das ein schickes, schönes Programm.

^*: Man könnte auch erkennen, dass das gesamte Problem auch zur Compilezeit gelöst werden kann und man eigentlich gar kein richtiges Programm braucht (sondern höchstens ein Metaprogramm). Aber ich schweife ab .

[Cpp_Anfaeger]

SeppJ schrieb:

Schlechter Ansatz. Wie willst du lernen, wenn du immer nur kopierst und veränderst? Du brauchst Erfahrung, wie du selbstständig etwas erstellst!

Danke für die ausführliche Erklärung zum Vorgehen bei dem Thema Klassen. Ich versuche morgen mal etwas aufzubauen.

Mir ging es bei dem Beispiel noch nicht um Algorithmen bzw. Rekursion. Das kommt später noch auf meinem Lernplan.... deswegen mal eben schnell "Türme von Hanoi " als Mittel zum Zweck kopiert, um damit Ablaufsteuerung, Funktion & Referenz zu üben

[SeppJ]

Cpp_Anfaeger schrieb:

deswegen mal eben schnell "Türme von Hanoi " als Mittel zum Zweck kopiert, um damit Ablaufsteuerung, Funktion & Referenz zu üben

Dann programmier doch selber Sachen mit Ablaufsteuerung, Funktionen und Referenzen!

[Cpp_Anfaeger]

SeppJ schrieb:

Cpp_Anfaeger schrieb:

deswegen mal eben schnell "Türme von Hanoi " als Mittel zum Zweck kopiert, um damit Ablaufsteuerung, Funktion & Referenz zu üben

Dann programmier doch selber Sachen mit Ablaufsteuerung, Funktionen und Referenzen!

Habe ich doch ... die gesamte Visualisierung habe ich doch mit Ablaufsteuerung, Funktionen & Referenzen ... programmiert.

Nur den Algorithmus:

void Ziehe(int von, int nach, int ScheibenZahl)
{
    int frei;
    if (ScheibenZahl==0) return;
    frei = 6 - von - nach;    // bestimme den freien Platz
    Ziehe(von, frei, ScheibenZahl-1);
    cout << von << " - " << nach << endl;
    Ziehe(frei, nach, ScheibenZahl-1);
}

habe ich von hier kopiert :

http://www.willemer.de/informatik/cpp/rekursion.htm

[Columbo]

Hier könnte man sich zum Beispiel praktisch alles sparen und einfach mit drei vector<int> oder stack<int> arbeiten, die die Problemstellung genau so gut einfangen, da es eben nicht so wichtig ist, ob die Scheibe wirklich eine Scheibe ist, da reicht auch jede andere Art von "Ding", die irgendwie den Begriff "größer" kennt.

#include <iostream>
#include <vector>
#include <iterator>
#include <functional>
using namespace std;

// Rekursiver Algorithmus von Wikipedia (http://de.wikipedia.org/wiki/T%C3%BCrme_von_Hanoi#Rekursiver_Algorithmus)
void solve( unsigned i,
            vector<unsigned>& a,
            vector<unsigned>& b,
            vector<unsigned>& c,
            function<void()> const& dump_all )
{
	if( i )
	{
		solve(i-1, a, c, b, dump_all);
		dump_all();
		c.push_back(a.back());
		a.pop_back();
		solve(i-1, b, a, c, dump_all);
	}
}

void dump( vector<unsigned>& a )
{
	cout << ": ";
	for(auto i : a)
		cout << i << ' ';
	cout << '\n';
}

int main()
{
	vector<unsigned> a{5,4,3,2,1}, b, c;

	auto dump_all = [&]
	{
		dump(a); dump(b); dump(c);
		cout << "--------------------";
		cin.get();
	};

	solve(5, a, b, c, dump_all);
	dump_all();
}

Aber ich schweife ab

Na vielen Dank, jetzt muss ich das also machen, ja!?

[Cpp_Anfaeger]

Danke für den Code. C++11 ist ja kurz, wie praktisch.

Aber was bedeutet das:

= [&]

[Columbo]

Das ist eine Zuweisung, [&]{ /*... */ } ist ein Lambda-Ausdruck, mit dem die Variable dump_all initialisiert wird.

[tipp]

Funktionen mit function<void()> zu übergeben macht niemand freiwillig, weil das enorm langsam ist. Ich bin mir sicher, Arcoth hat das nur gemacht, damit der Code verständlicher ist, aber sobald du Templates kennst, würde ich diese verwenden.

[Cpp_Anfaeger]

Danke, der Thread hier schnappt mir das Wort aus dem Mund:

http://www.computerbase.de/forum/showthread.php?t=590896

[Columbo]

Ich bin mir sicher, Arcoth hat das nur gemacht, damit der Code verständlicher ist

Natürlich wäre der normale Fall so:

template<typename Func>
void solve( ...,
            Func const& dump_all ) // Const-Referenz, um Kopie des closure-Objektes zu vermeiden

[Cpp_Anfaeger]

Ich habe gerade angefangen, die Visualisierung objektorientiert zu programmieren. Mir fehlt leider noch die Vorstelllungskraft, wie ich den Verlauf richtig gestalten soll.

Ich habe mir überlegt, dass ich folgende Klassen erstelle:

* Slice
	- kann ihre Länge selbst bestimmen u. zurückgeben
	- kann ihre Mitte selbst bestimmen u. zurückgeben
	- kann sich selbst zurückgeben

* Tower
	- kann ihre Größe selbst bestimmen u. zurückgeben
	- kann sich selbst zurückgeben
	- kann eine Scheibe aufnehmen
	- kann eine Scheibe von sich nehmen u. an einen anderen Turm geben
	- kann auf ein Mal komplett eine Ladung Scheiben auf sich nehmen (beim Start)

* Simulation
	- kann rekursiv die Bewegungen der Scheiben errechnen

* Display
	- kann den Konsolenbildschirm leeren
	- kann eine Position auf der Konsole ansteuern
	- kann auf einen Tastendruck warten
	- kann String-Werte auf der Konsole ausgeben
	- kann die Scheiben und ihre Türme auf die Konsole einzeichen

Ich kann im Moment nicht absehen, wie ich "die Scheibe an den Turm geben" klassen-technisch lösen soll.

In der strukturierten Programmierung hatte ich bisher einen Container deque<string> als Übergabeparameter.

Nun mit dem Klassendesign hätte ich also den Container deque<Slice>, der an die Klasse Tower zu übergeben wäre, oder? Wie geht das? Übergebe ich das ganze Objekt (Slice)?

[SeppJ]

tower.add(slice) ?

[Cpp_Anfaeger]

SeppJ schrieb:

tower.add(slice) ?

ist slice dann die Klasse selbst? Kann ich sie so einfach übergeben, oder muss ich da was bauen für?

[asdfsa]

Cpp_Anfaeger schrieb:

SeppJ schrieb:

tower.add(slice) ?

ist slice dann die Klasse selbst? Kann ich sie so einfach übergeben, oder muss ich da was bauen für?

du kannst natürlich schon nicht einen typen als funktionsparameter (ich hab extra funktion davorgehängt, nicht dass mir nun die leute erklären kommen was templates sind...) übergeben. das würde dann vielleicht so aussehen:

void Transfer(Tower& Lhs, Tower& Rhs)
{
    Lhs.Add(Rhs.Top());
    Rhs.Pop();
}

oder wenn du es exceptionsafe machen willst:

void Transfer(Tower& Lhs, Tower& Rhs)
{
    Tower LhsCopy(Lhs);
    LhsCopy.Add(Rhs.Top());
    Rhs.Pop();
    Lhs.Swap(LhsCopy);
}

wobei die ensprechenden funktionen (add, top etc) alle mit instanzen vom typen slice arbeiten.

[Columbo]

oder wenn du es exceptionsafe machen willst:

Das braucht man nicht. (bzw. es ist bereits exception-safe).
Destruktoren sollten nie etwas werfen. Daher sollte pop() auch nie etwas werfen.
Edit: Eine assertion, welches die Groesse von rhs prueft, waere auch nicht verkehrt.

[asdfsa]

Arcoth schrieb:

oder wenn du es exceptionsafe machen willst:

Das braucht man nicht. (bzw. es ist bereits exception-safe).
Destruktoren sollten nie etwas werfen. Daher sollte pop() auch nie etwas werfen.

da hast du recht. stell dir aber den (unwahrscheinlichen) fall vor, dass bei jedem pop ein neuer speicherbereich alloziiert wird und alle elemente umkopiert werden (bzw. gemoved). dann kann ein pop schonmal werfen. (mir ist schon bewusst dass das bei std::stack<T, std::vector<T> > nicht passiert aber man kann ja nie wissen, womit und wie etwas implementiert werden wird.

[Cpp_Anfaeger]

asdfsa schrieb:

void Transfer(Tower& Lhs, Tower& Rhs)
{
    Lhs.Add(Rhs.Top());
    Rhs.Pop();
}

Hmmm... wo hätte ich dann das Objekt Slice?

[asdfsa]

Cpp_Anfaeger schrieb:

asdfsa schrieb:

void Transfer(Tower& Lhs, Tower& Rhs)
{
    Lhs.Add(Rhs.Top());
    Rhs.Pop();
}

Hmmm... wo hätte ich dann das Objekt Slice?

asdfsa schrieb:

wobei die ensprechenden funktionen (add, top etc) alle mit instanzen vom typen slice arbeiten.

[Cpp_Anfaeger]

asdfsa schrieb:

Cpp_Anfaeger schrieb:

asdfsa schrieb:

void Transfer(Tower& Lhs, Tower& Rhs)
{
    Lhs.Add(Rhs.Top());
    Rhs.Pop();
}

Hmmm... wo hätte ich dann das Objekt Slice?

asdfsa schrieb:

wobei die ensprechenden funktionen (add, top etc) alle mit instanzen vom typen slice arbeiten.

achso, das muss ich noch sacken lassen ...