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

[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 ...

[Columbo]

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.~

[SeppJ]

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

[Werner Salomon]

SeppJ schrieb:

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:

...

nicht schlecht SeppJ .. nur bei der Ausgabe der Türme sehe ich noch Verbesserungspotential.

Dazu habe ich mir auch was einfallen lassen. Vom Algorithmus her ist das so eine Art einfacher-2D-Raytracer. Der Kern besteht aus dem Interface Shape und der Klasse Display . Display hat Zugriff auf alle Shape -Objekte, die gezeichnet werden sollen. Wird ein Display -Objekt ausgegeben, so berechnet Display für jeden Punkt (Zeichen) in der Ausgabe die jeweilige Position und fordert alle Shapes auf, ggf ihren 'Stempel' dort zu hinterlassen.

Jedes Objekt, was 'gezeichnet' werden soll, muss von Shape abgeleitet sein, und die Methode void draw( const Pos& drawPos, char& out ) const überladen. Dort muss dann eine Implementierung dafür sorgen, dass das Zeichen out genau dann überschrieben wird, wenn die Position drawPos auf eine Punkt des Objekts zeigt. Natürlich sollte das Objekt dazu wissen, wo es sich befindet.
Die Klasse Pos enthält schlicht x- und y-Wert einer Position. Man bräuchte Pos in dieser Programm-Skizze nicht zwingend, ich finde das aber durchgängiger und verständlicher. Für Erweiterungen, die Addition- und/oder Subtraktion von Positionen nötig machen ist Pos sicher von Vorteil.

Die Methode ermöglicht es auch, Objekte übereinander zu zeichnen. Es gewinnt das Objekt, welches 'oben' liegt.

Anbei die Demo:

#include <iostream>
#include <string>
#include <vector>

class Pos
{
public:
    Pos() : x_(0), y_(0) {}
    Pos( int x, int y ) : x_(x), y_(y) {}

    friend int X( const Pos& pos ) { return pos.x_; }
    friend int Y( const Pos& pos ) { return pos.y_; }
private:
    int x_, y_;
};

class Shape
{
public:
    virtual ~Shape() =0;
    virtual void draw( const Pos& drawPos, char& out ) const =0;
};
Shape::~Shape() {}

// --   die Scheibe ist ein schlichter int
//      es folgen 5 überflüssige Zeilen; sie dienen nur als 'syntaktischer Zucker' (s. Tower::draw)
typedef int Slice;
int get_diameter( const Slice& slice )
{
    return slice;
}

// --   der Turm aus 'die Türme von Hanoi'
class Tower : public Shape
{
public:
    Tower( const Pos& turm_pos )
        : slices_()
        , pos_(turm_pos)
    {}

    void push( const Slice& slice )
    {
        slices_.push_back( slice );
    }

    // --   die Methode 'draw' schaut nach, ob der Punkt 'out' in der
    //      Position 'drawPos' auf einer der Scheiben des Turms
    //      liegt. 
    //      Falls ja, wird 'out' mit der 'FARBE' der Scheibe belegt
    virtual void draw( const Pos& drawPos, char& out ) const
    {
        const char FARBE = 'X';
        const int idx = Y(drawPos) - Y(pos_);
        if( idx >= 0 && idx < int(slices_.size()) )
        {
            const int xBegin = X(pos_) - get_diameter( slices_[idx] )/2;
            if( xBegin <= X(drawPos) && X(drawPos) < xBegin + get_diameter( slices_[idx] ) )
                out = FARBE; // Punkt 'drawPos' liegt in einer Scheibe 'slices_[idx]' -> 'anmalen'
        }
    }
private:
    std::vector< Slice > slices_; // die Scheiben
    Pos pos_; // Position des Turms (Mitte unten)
};

class Display
{
public:
    Display()
        : shapes_()
        , lower_left_()
        , upper_right_( 60, 12 )
    {}
    void add( const Shape& shape )
    {
        shapes_.push_back( &shape );
    }

    // --   Bildausschnitt setzen
    Display& operator()( const Pos& lower_left, const Pos& upper_right )
    {
        lower_left_ = lower_left;
        upper_right_ = upper_right;
        return *this;
    }

    // --   'zeichnen' des Display-Inhalts
    friend std::ostream& operator<<( std::ostream& out, const Display& d )
    {
        for( int y = Y(d.upper_right_); y >= Y(d.lower_left_); --y )
        {
            out.width(3);
            out << y << ": ";
            for( int x = X(d.lower_left_); x <= X(d.upper_right_); ++x )
            {
                char c = out.fill(); // background
                const Pos pos(x, y);
                for( auto s = begin(d.shapes_); s != end(d.shapes_); ++s )
                    (*s)->draw( pos, c );
                out << c;
            }
            out << '\n'; // EOL
        }
        return out << "--x->" << std::string("|-10 |-5  |    |5   |10  |    |20  |    |30  |    |40  |    |50  |    |60  |    |80")
            .substr(X(d.lower_left_) + 10, X(d.upper_right_) - X(d.lower_left_) + 1) << "\n";
    }
private:
    std::vector< const Shape* > shapes_;
    Pos lower_left_, upper_right_;
};

// --   Demo-main-Programm für obige Konstruktion
int main()
{
    using namespace std;
    Tower t1( Pos(10,0) );
    for( int slice = 9; slice > 0; slice -= 2 )
        t1.push( slice );

    Tower t2( Pos(25,2) ); // der zweite Turm liegt um 2 höher
    t2.push( 7 );
    t2.push( 3 );
    t2.push( 1 );

    Display display;
    display.add( t1 );
    display.add( t2 );

    cout << "zwei Tuerme:\n" << display( Pos(0,0), Pos(60,8) ) << endl; // die Koordinaten bestimmen den Bildausschnitt

    // -- noch ein wenig Demo-Schischi
    t2.push( 0 );
    for( int i=1; i<36; i+=4 )
        t2.push( i > 13? 26 - i: i );
    cout << "zweiter Bildausschnitt:\n" << display( Pos(9,2), Pos(35,12) ) << endl;
    return 0;
}

Noch ein Hinweis: die Ausgabe der Skaliereung für x und y ist für die Demo hier. Wer das nicht haben will, lässt die Zeilen 94 und 95 weg und ersetzt die Zeilen 106 und 107 durch ein schlichtes return out; .

Es ist übrigens ein Leichtes, SeppJs Programm und dieses zu verbinden. Man nehme die Klassen Display und Shape und die Methode Tower::draw , füge Letztere zu SeppJs Tower hinzu und ersetze die Ausgabe des Temple durch die Ausgabe von Display .

SeppJ schrieb:

Da manche Leute immer noch kein C++11 haben:
https://ideone.com/bgcPZl

.. manchmal schlägt eben der normative Zwang des Faktischen erbarmungslos zu

Gruß
Werner