Tower of Hanoi

chille07

Hallo!

ich habe das HIERHER gepostet (ANSI C), weil wir das Programm, welches wir für unseren Programmierunterricht schreiben sollten, in C geschrieben werden soll.

Naja: Wer kennt die "Türme von Hanoi"?
es sind "n" immer schmäler werdende blöcke übereinander gestapelt.
es gibt 3 "flächen" wo "teile" des turmes positioniert werden können.
Ziel ist es, den Turm, der auf FLÄCHE1 steht, auf FLÄCHE 2 zu bewegen.
Dabei darf jedoch immer nur ein Block verschoben werden.
Es darf immer nur der oberste Block bewegt werden.
Weiters darf nie ein größerer Block über einem kleineren stehen.

Das Programm soll sämtliche Züge, die gemacht werden am Bildschirm ausgeben.
Es soll in einer Rekursiven Funktion berechnet werden.

zB.:
Flächen: a,b,c
turmhöhe: 3 stufen

*
  ***
 ***** _____ _____

a->b

a->c
b->c
a->b
c->a
c->b
a->b ...nun steht der turm auf position b

*
        ***
 _____ ***** _____

Kennt jemand einen Algorithmus dafür, oder kann sich jemand einen Algorithmus vorstellen(rekursiv)?

mfG (c)h

Also komm.
Dafür gibt es nun wirklich genug fertiges Material.
http://de.search.yahoo.com/search?p=türme+von+hanoi+c&ei=UTF-8&fr=fp-tab-web-t-1&fl=0&vc=&x=wrt&meta=vl%3D

Ist ja sozusagen die Standardaufgabe für die Rekursion.(Neben Potenzen.)

chille07

#include<stdio.h>
#include<conio.h>

void bewege(char a,char b,char c,int hoehe)
{
	if (hoehe == 1)
	{
		printf("\n %c -> %c",a,c);
	} 
	else
	{
		bewege(a,c,b,hoehe-1);
		bewege(a,b,c,1);
		bewege(b,a,c,hoehe-1);
	}
}

void main ()
{
	int hoehe;
	printf("\n Bitte geben Sie die Hoehe des Turmes ein...");
	scanf("%d",&hoehe);
	fflush(stdin);

	bewege('a','b','c',hoehe);
	getchar();
}

das funktioniert, aber........
kann mir jemand beim verständnis der funktion "bewege" behilflich sein?!

mfG (c)h

Die Idee ist, das man das Problem schrittweise vereinfacht.
(Jeweils mit einer Scheibe weniger.)

Als wir das in Informatik besprochen haben, lagen mehrere Geldmünzen auf dem Tisch und wir mussten uns alle in einer Reihe aufstellen und einer hat dann zu dem nächsten immer gesagt:
Ich möchte, das du dieses Türmchen dahin bewegst.
Man selber musste nur eine Scheibe vor der Weiterdelegation und eine danach
umlegen.

Vielleicht hilft dir ja diese Vorstellung.