Konsolen-Simulation des Algorithmus "Türme von Hanoi" unter Verwendung einer Klasse
-
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
-
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!
-
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
:
-
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!?
-
Danke für den Code. C++11 ist ja kurz, wie praktisch.
Aber was bedeutet das:
= [&]
-
Das ist eine Zuweisung,
[&]{ /*... */ }ist ein Lambda-Ausdruck, mit dem die Variabledump_allinitialisiert wird.
-
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.
-
Danke,
der Thread hier schnappt mir das Wort aus dem Mund:
-
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
-
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 einzeichenIch 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)?
-
tower.add(slice)?
-
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?
-
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.
-
oder wenn du es exceptionsafe machen willst:
Das braucht man nicht. (bzw. es ist bereits exception-safe).
Destruktoren sollten nie etwas werfen. Daher solltepop()auch nie etwas werfen.
Edit: Eine assertion, welches die Groesse vonrhsprueft, waere auch nicht verkehrt.
-
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 solltepop()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.
-
asdfsa schrieb:
void Transfer(Tower& Lhs, Tower& Rhs) { Lhs.Add(Rhs.Top()); Rhs.Pop(); }Hmmm... wo hätte ich dann das Objekt Slice?
-
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.
-
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 ...
-
aber man kann ja nie wissen, womit und wie etwas implementiert werden wird.
Der Fall ist so unwahrscheinlich (und andererseits so verheerend*), dass man ihn vernachlaessigen kann. Es macht die Funktion nur komplizierter und langsamer.
Und falls eine Exception fliegt, dann kommt diese wahrscheinlich sowieso bis zur
main()durch und wird den Programmfluss mindestens unterbrechen, sodass der Status eines der Stacks keinen Unterschied mehr macht.
Prinzipiell hast du aber Recht.* ~Ueberleg dir mal, wie lange das Programm noch weiterlaeuft, sobald der Speicher ausgegangen ist.~
-
Mir war langweilig
. Das Programm erzählt die Geschichte der Türme von Hanoi. Ich habe natürlich peinlich genau darauf geachtet, dass die Scheiben wirklich verschoben werden, keine Tricksereien mit Kopien von Scheiben. Kopien von realen Gegenständen gibt es in einem wohl geformten Universum nicht. Über allem wacht der mächtige Gott Brahma, dass alle Regeln eingehalten werden:#include <iostream> #include <vector> #include <stdexcept> #include <utility> class EndOfTheWorldAsWeKnowIt { }; class Disk { unsigned diameter; void brahma_check() const { if (diameter == 0) throw std::logic_error("Brahma ist zornig! " "Du hast die heiligen Regeln verletzt, " "als du eine nicht existierende Scheibe nahmst." ); } public: Disk(unsigned diameter = 0) : diameter(diameter) { } Disk(Disk &&other): diameter(other.diameter) { other.brahma_check(); other.diameter = 0; } Disk(const Disk&) = delete; void operator=(const Disk&) = delete; unsigned get_diameter() const { brahma_check(); return diameter; } friend std::ostream& operator<<(std::ostream &out, Disk const& disk) { return out << "|\t" << disk.diameter << "\t|"; } }; class Tower { std::vector<Disk> disks; public: void add_disk(Disk &&disk) { if (!disks.empty() && disks.back().get_diameter() < disk.get_diameter() ) throw std::logic_error("Brahma ist zornig! " "Du hast die heiligen Regeln verletzt, " "als du eine große Scheibe auf eine kleine legtest." ); disks.push_back(std::move(disk)); } Disk remove_top() { if (disks.empty()) throw std::logic_error("Brahma ist zornig! " "Du hast die heiligen Regeln verletzt, " "als du eine Scheibe von einem leeren Turm nahmst." ); Disk disk = std::move(disks.back()); disks.pop_back(); return std::move(disk); } bool empty() const { return disks.empty(); } Tower() = default; Tower(const Tower&) = delete; void operator=(const Tower&) = delete; friend std::ostream& operator<<(std::ostream &out, Tower const& tower) { for(auto const& disk: tower.disks) out << disk; return out; } }; template <unsigned num_disks> class Temple { Tower towers[3]; public: Temple() { for(unsigned i = num_disks; i != 0; --i) towers[0].add_disk(Disk(i)); } void move(unsigned from, unsigned to) { towers[to].add_disk(towers[from].remove_top()); } void show_to_brahma() const { if (towers[0].empty() && (towers[1].empty() || towers[2].empty())) throw EndOfTheWorldAsWeKnowIt(); else throw std::logic_error("Brahma ist zornig! " "Du hast die heiligen Regeln verletzt, " "als du ihm eine unvollstandige Lösung zeigtest." ); } friend std::ostream& operator<<(std::ostream &out, Temple<num_disks> const& temple) { return out << "----------------------------------------------------------\n" << temple.towers[0] << '\n' << temple.towers[1] << '\n' << temple.towers[2] << '\n' << "----------------------------------------------------------\n"; } }; class Monk { unsigned rank; static unsigned other_tower(unsigned t1, unsigned t2) { if (t1 == 0 && t2 == 1) return 2; if (t1 == 1 && t2 == 0) return 2; if (t1 == 2 && t2 == 1) return 0; if (t1 == 1 && t2 == 2) return 0; if (t1 == 2 && t2 == 0) return 1; if (t1 == 0 && t2 == 2) return 1; throw std::logic_error("Brahma ist zornig! " "Du hast die heiligen Regeln verletzt, " "als du totalen Unsinn programmiert hast." ); } public: Monk(unsigned rank): rank(rank) { } template <typename Temple> void solve_puzzle(Temple &temple, unsigned from, unsigned to) { if (rank > 1) { // Ask subordinate to move all the top disks: Monk minor_monk(rank - 1); unsigned other = other_tower(from, to); minor_monk.solve_puzzle(temple, from, other); // Move the last piece temple.move(from, to); // Proudly draw the result: std::cout << temple; // Ask subordinate to move all the rest: minor_monk.solve_puzzle(temple, other, to); } else { // This task is simple, even for the lowliest monk: temple.move(from, to); // Proudly draw the result: std::cout << temple; } } }; int main() { const unsigned num_disks = 5; Temple<num_disks> temple; try { std::cout << temple; Monk abbot(num_disks); abbot.solve_puzzle(temple, 0, 1); temple.show_to_brahma(); } catch (EndOfTheWorldAsWeKnowIt) { std::cout << "Brahma ist zufrieden. Das Universum hat seinen Zweck " "erfüllt und kann nun neu erschaffen werden. Einen schönen Tag noch!\n"; } }P.S.: Da manche Leute immer noch kein C++11 haben:
https://ideone.com/bgcPZl
