Euer erstes mal " türme von hanoi"

[kantaki]

Cybertec schrieb:

Hmm, ich hab in der Aufgabe nur eine if Abfrage drin.

ja klar die endbedingung n>0
soweit bin ich auch

[SeppJ]

kantaki schrieb:

Hattet ihr damals auch probleme diese aufgabe rekursiv zu lösen ?

Hmm, eigentlich nicht. Mir ist der rekursive Algorithmus sogar deutlich intuitiver. Bei der allerersten Implementierung hat's freilich nicht auf Anhieb funktioniert, aber das lag da dran, dass ich nicht gut programmieren konnte, nicht, weil ich nicht gewusst hätte, was zu tun ist. War aber auch nicht das erste Mal, dass ich überhaupt etwas rekursives gemacht habe.

[Bashar]

Ich hab das beim ersten Versuch nicht hingekriegt und aufgegeben, hab auch die gegebene Lösung nicht kapiert. Hilft dir das weiter? Ich glaube nicht :p

Wenn es bei der Rekursion irgendwann mal geklickt hat ist das aber ganz einfach. Überlege dir (wie bei jeder Rekursion) die zwei Fälle:

1. Den Basisfall: Wie bekomme ich eine Scheibe von A nach B?
2. Den rekursiven Fall: Angenommen ich möchte n>1 Scheiben von A nach B schaffen und eine gute Fee kann mir die Aufgabe abnehmen, n-1 Scheiben von A nach B zu schaffen. Wo muss ich dann meine Scheibe hinlegen und wo sag ich der Fee, dass sie die anderen n-1 Scheiben hintransportieren soll?
   (Die Fee bist du selbst, das ist die Magie bei der Rekursion.)

(Man kann auch n=0 als Basisfall nehmen. Geschmackssache. Ich empfehle, beide Versionen mal zu implementieren.)

[Michael E.]

Ich hab nie die Türme von Hanoi programmiert :p

[ipsec]

Mir wurde gleich die Implementierung gezeigt. An sich finde ich sie aber auch sehr intuitiv, jedoch kommt man nur schwer drauf, wenn man mit rekursiven Algorithmen noch nicht vertraut ist. Dann möchte man das rekursive Problem lösen und erkennt nicht, dass man es schon gelöst hat.
Deine 10-Minuten-Lösung würde mich aber auch mal interessieren. Es gibt einen iterativen Algorithmus, aber auf den kommt man eigentlich auch nicht ohne weiteres.

[*Rewind*]

Her mit der Aufgabenstellung.

[berniebutt]

Gespielt mit Hölzern schon, programmiert nicht. Führt zu einem kniffligen aber intereressanten Algorithmus. Zeig deinen Ansatz her oder was du da schon gefunden hast! Irgendwie Geld verdienen kann man damit wohl nicht?

[kantaki]

naja ich bin noch nicht sehr weit

void hanoi(int hoehe, char  ausgang, char zwichen, char ziel )
{
 if (hoehe > 0)
 {
      hanoi(hoehe-1,ausgang,ziel,zwichen);
      cout << ausgang<<" nach "<<ziel<<endl;

also ich denke das ich meinen ersten schritt schonmal richtig gemacht habe.
da bei ungeraden zahlen immer von a nach c und bei geraden zahlen a nach b ausgeführt wird.

beispiel
n=1 a nach c
n=2 a nach b
n=3 a nach c

das ist der erste sich ständig wiederholende algorithmus den ich entdeck habe, doch wie ich weiter komme. keine ahnung.

bitte nur tips geben ( keine lösungen )

edit ups

a = anfang
b = puffer
c = ziel

[SeppJ]

Wenn eine Scheibe bewegt wurde, müssen die Scheiben vom Zwischenstapel wieder drauf gelegt werden.

[kantaki]

void hanoi(int hoehe, char  ausgang, char zwichen, char ziel )
{
 if (hoehe > 0)
 {
      hanoi(hoehe-1,ausgang,ziel,zwichen);
      cout << ausgang<<" nach "<<ziel<<endl;
      hanoi(hoehe-1,zwichen,ausgang,ziel);

 }

}

okay ich habe es hinbekommen, aber rekursion finde ich trotzdem noch sehr merkwürdig, ich habe eigentlich nur zwei sachen erkannt und das programm wird korrekt ausgeführt. ich muss nochmal jeden schritt durchgehen.

edit: es sind ja auch eigentlich nur 2 sich wiederholende aktionen.

[SeppJ]

Die Geschichte, wie der älteste Mönch im Kloster das Problem löst, kennst du aber, oder?

[kantaki]

SeppJ schrieb:

Die Geschichte, wie der älteste Mönch im Kloster das Problem löst, kennst du aber, oder?

ne kenne ich nicht, direkt mal nachlesen

[SeppJ]

kantaki schrieb:

SeppJ schrieb:

Die Geschichte, wie der älteste Mönch im Kloster das Problem löst, kennst du aber, oder?

ne kenne ich nicht, direkt mal nachlesen

Wikipedia. Wieso hast du das nicht sofort gelesen? schrieb:

Vermutlich wurde das Spiel 1883 vom französischen Mathematiker Édouard Lucas erfunden. Er dachte sich dazu die Geschichte aus, dass indische Mönche im großen Tempel zu Benares, im Mittelpunkt der Welt, einen Turm aus 64 goldenen Scheiben versetzen müssten, und wenn ihnen das gelungen sei, wäre das Ende der Welt gekommen.

In der Geschichte lösen die Mönche das Problem folgendermaßen: Der älteste Mönch erhält die Aufgabe, den Turm aus 64 Scheiben zu versetzen. Da er die komplexe Aufgabe nicht bewältigen kann, gibt er dem zweitältesten Mönch die Aufgabe, die oberen 63 Scheiben auf einen Hilfsplatz zu versetzen. Er selbst (der Älteste) würde dann die große letzte Scheibe zum Ziel bringen. Dann könnte der Zweitälteste wieder die 63 Scheiben vom Hilfsplatz zum Ziel bringen.

Der zweitälteste Mönch fühlt sich der Aufgabe ebenfalls nicht gewachsen. So gibt er dem drittältesten Mönch den Auftrag, die oberen 62 Scheiben zu transportieren, und zwar auf den endgültigen Platz. Er selbst (der Zweitälteste) würde dann die zweitletzte Scheibe an den Hilfsplatz bringen. Schließlich würde er wieder den Drittältesten beauftragen, die 62 Scheiben vom Zielfeld zum Hilfsplatz zu schaffen. Dies setzt sich bis zum 64. Mönch (dem Jüngsten) fort, der die obenauf liegende kleinste Scheibe alleine verschieben kann.

Da es 64 Mönche im Kloster gibt und alle viel Zeit haben, können sie die Aufgabe in endlicher, wenn auch sehr langer Zeit erledigen.

Ist dir nun klar, was da passiert?

[kantaki]

ja schon klar im prinzip ist eine funktion ein mönch. sie lösen das problem auch rekursiv.

gibt es vielleicht noch andere rekursive aufgaben ? fakultät habe ich eben schon geschrieben, das war relativ einfach.

[knivil]

kantaki schrieb:

gibt es vielleicht noch andere rekursive aufgaben ?

LU-Zerlegung.