Turm von Hanoi (Zweifarbig)

Neue Frage »

Andreamimi Auf diesen Beitrag antworten »
Turm von Hanoi (Zweifarbig)
Meine Frage:
Hallo, ich brauche Hilfe beim finden einer Formel für diese Aufgabe:

Und zwar geht es um einen zweifarbigen Turm von Hanoi, d.h. jede Scheibe ist zweimal vorhanden, einmal in schwarz und einmal in weiß. Die Farben liegen im Wechsel der Größe nach sortiert aufeinander.
Das Ziel besteht darin, einen schwarzen und einen weißen Turm zu erhalten, wobei die größte schwarze und die größte weiße Scheibe ihre Positionen tauschen sollen. In jedem Zug kann nur eine Scheibe bewegt werden. Man darf auch hier nur kleinere auf größere Scheiben legen.

Finden Sie die minimale Anzahl an Zügen für n=1, n=2, n=3.
Bei n=2, gibt es also auf einer Stange eine große schwarze Scheibe und da drauf eine kleinere weiße, auf einer der anderen Stangen liegt eine große weiße Scheibe und eine kleinere schwarze oben drauf.

Finden Sie auch eine rekursive
oder explizite Formel zur Berechnung der Anzahl?

Meine Ideen:
Ich habe für n=1 A(n)=3, für n=2 A(n)=10 und für n=3 A(n)=30.
Die Ergebnisse habe ich allerdings nur durch ausprobieren bekommen. Ich kann kein Muster erkennen. Natürlich sind es vielfache von 3, das wäre allerdings zu einfach.
Die rekursive Formel für den klassichen Turm v. H. ist ja A(n+1)= 2*A(n)+1. Ich weiß nicht, ob ihr was damit anfangen könnt.
10001000Nick1 Auf diesen Beitrag antworten »
RE: Turm von Hanoi (Zweifarbig)
Zitat:
Original von Andreamimi
Man darf auch hier nur kleinere auf größere Scheiben legen.

Steht das wirklich so in der Aufgabe? In deinem Bildausschnitt kann man zwar nicht den ganzen Aufgabentext lesen, aber da steht etwas von "... Scheibe legen, die mindestens den...".
Steht da vielleicht, dass eine Scheibe höchstens den Durchmesser der Scheibe haben darf, auf die man sie drauf legt? (Gleich große Scheiben übereinander sind also auch erlaubt.)

Bei der Regel "nur kleinere auf größere" gibt es meiner Meinung nach schon für n=2 keine Lösung mehr.

Falls das stimmen sollte, habe ich für n=2 eine Lösung mit 9 Zügen gefunden. Meintest du wahrscheinlich auch, weil du ja geschrieben hast, A(n) ist ein Vielfaches von 3.
Andreamimi Auf diesen Beitrag antworten »
RE: Turm von Hanoi (Zweifarbig)
Ja stimmt, mindestens den gleichen Durchmesser, also man darf auch gleichgroße aufeinander legen.
Kannst du dir eine Formel erschließen?
10001000Nick1 Auf diesen Beitrag antworten »

An einer allgemeinen Formel für (rekursiv oder explizit) rätsele ich auch noch. Das, was mir gerade einfällt, sieht ziemlich "unschön" aus und ich bin auch noch nicht davon überzeugt, dass es richtig ist.
Ich werde nochmal überlegen; vielleicht fällt ja auch jemand anderem etwas ein. smile
Andreamimi Auf diesen Beitrag antworten »
RE: Turm von Hanoi (Zweifarbig)
Okay, ich werde auch noch weitergrübeln. Sollte dir noch etwas einfallen, lass es uns hier bitte wissen.
Einen schönen Abend noch.
HAL 9000 Auf diesen Beitrag antworten »
Déjà-vu ?
Anscheinend soll das hier eine Fortsetzung dieses Threads werden. verwirrt
 
 
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »