Türme von Hanoi - Wiederholungsproblem

chiefe

#include <stdio.h>

void hanoi (int hoehe, char von, char nach, char ueber);
int neu, i=0;
int main (void)
{
	do
	{
		int n;
		printf("\n-------------Die Tuerme von Hanoi-------------\n");
		printf("\n----------------------------------------------\n\n");

			do
			{
				printf("Aus wie vielen Elementen soll der Turm bestehen?\nBitte geben Sie eine Zahl ueber 0 ein!\n\n");

				scanf("%d", &n);
				printf("\n");
			}
			while (n<1);

		printf("\n----------------------------------------------\n\n");
		printf ("Bewege:\n\n");
		hanoi (n, '1', '2', '3');
		printf ("-----------------------------------------------\n\n");
		printf ("Somit befinden sich alle Scheiben auf Stab Nr.2\n\n");
		printf ("-----------------------------------------------\n\n");

	printf("Wiederholen(ja=1, nein=2)? ");
	scanf("%d",&neu);
	printf ("---------------------------------------------------------------------------\n\n");
	}
	while (neu==1);

	return 0;
}

void hanoi (int hoehe, char von, char nach, char ueber)
{
	if (hoehe > 1)
	hanoi (hoehe - 1, von, ueber, nach);
	i++;
	printf ("Schritt %d - ", i);
	printf ("Scheibe '%d' nach Stab '%c',\n\n", hoehe, nach);
	if (hoehe > 1)
	hanoi (hoehe - 1, ueber, nach, von);
}

hi,

wir haben mit dem obigen quelltext folgendes problem:
bei der durchnummerierung also schritt... wird beim ersten durchlauf richtig gezählt, beim zweiten allerdings fortlaufen.

woran kann das liegen!
irgendwie müsste der speicher geleert werden, haben aber leider nichts passendes gefunden.

vielen dank für eure hilfe

MFK

Setz doch einfach am Anfang der while-Schleife den Schrittzähler auf 0.

chiefe

wo genau???

Bashar

Bevor du in main hanoi aufrufst.

chiefe

super hat geklappt, danke

#include <stdio.h>

void hanoi (int hoehe, char von, char nach, char ueber);
int i=0, hoehe, neu;
int main (void)
{
	do
	{
		printf("\n-------------Die Tuerme von Hanoi-------------\n");
		printf("\n----------------------------------------------\n\n");
			do
			{
				printf("Aus wie vielen Elementen soll der Turm bestehen?\nBitte geben Sie eine Zahl ueber 0 ein!\n\n");

				scanf("%d", &hoehe);
				printf("\n");
			}
			while (hoehe<1);

		printf("\n----------------------------------------------\n\n");
		printf ("Bewege:\n\n");
		i=0;
		hanoi (hoehe, '1', '2', '3');
		printf ("-----------------------------------------------\n\n");
		printf ("Somit befinden sich alle Scheiben auf Stab Nr.2\n\n");
		printf ("-----------------------------------------------\n\n");

	printf("Wiederholen(ja=1, nein=2)? ");
	scanf("%d",&neu);
	printf ("---------------------------------------------------------------------------\n\n");
	}
	while (neu==1);

	return 0;
}

void hanoi (int hoehe, char von, char nach, char ueber)
{
	if (hoehe > 1)
		hanoi (hoehe - 1, von, ueber, nach);
		i++;
		printf ("Schritt %d - ", i);
		printf ("Scheibe '%d' nach Stab '%c',\n\n", hoehe, nach);
	if (hoehe > 1)
		hanoi (hoehe - 1, ueber, nach, von);
}

chiefe

könnte mir vielleicht mal eben jemand erklären, was dieser teil des quelltextes auf den hacken hat???

hanoi (hoehe - 1, von, ueber, nach);

also das hanoi ist ja ein verweiß auf die funktion hanoi, hoehe-1 heißt, dass 1 subtrahiert werden soll, aber wofür stehen die von, über, nach genau???
es handelt sich bei den drei angaben um die einzelnen stäbe, aber wie wird das mit dem algorithmus gemacht???
sitzen schon 5 stunden daran, haben im netz recherchiert, viel gerechnet usw.
wir kommen aber nicht auf die lösung.
wäre nett, wenn uns das mal einer erklären könnte!

danke

MFK

Das Problem, einen ganzen Turm "von" - "über" - "nach" zu bewegen, wird auf drei einfachere reduziert. Man bewegt (1) alle Schreiben bis auf die größte "von" -> "über", dann (2) die größte "von" -> "nach", und schließlich (3) alle übrigen Scheiben "über" -> "nach". Bei (1) wird zwischenzeitig der ursprüngliche "nach" als "über" benutzt, bei (3) der ursprüngliche "von".

(1) ist der erste rekursive Aufruf, (2) ist der "Schritt" und (3) der zweite rekursive Aufruf. Und weil man bei (1) und (3) alle bis auf die größte bewegt, steht da hoehe - 1.

Man sollte noch anmerken, dass die Einrückung in der hanoi-Funktion irreführend ist. Das i++ und die beiden printfs hängen nicht von dem ersten if ab.

chiefe

erst mal danke.
das verstehen der vorgehensweise ist uns schon klar.
das problem ist halt nur, wie kommt eine zahl, nehmen wir mal an eine 3 durch die funktion hanoi?
in der sache bleiben wir dann immer bei hanoi(scheibe-1,von, ueber, nach); stehen.
woher weiß das programm, dass die scheibe auf zb. ueber kommt??
das ist unser problem.

könntest du vielleicht mal eine zahl durch die untere funktion durchlaufen lassen??
also nehmen wir mal an eine 3.

das wäre super nett.

wir brauchen das im rahmen des cae unterrichts an der fh!

danke

MFK

chiefe schrieb:

in der sache bleiben wir dann immer bei hanoi(scheibe-1,von, ueber, nach); stehen.
woher weiß das programm, dass die scheibe auf zb. ueber kommt??

Das Programm "weiß" nichts, es ist einfach so geschrieben. Die Funktion hanoi erwartet die Stäbe in der Reihenfolge "von"-"nach"-"über". Wenn man beim rekursiven Aufruf also "von"-"über"-"nach" benutzt, dann sind im verschachtelten Aufruf "über" und "nach" vertauscht.

Für Höhe 3 sieht das so aus (ich benutze a, b und c für die Stäbe, damit man das besser von den Scheiben unterscheiden kann):

hanoi(3,a,b,c)
{
  hanoi(2,a,c,b)
  {
    hanoi(1,a,b,c)
    {
      Scheibe 1 von a nach b
    }
    Scheibe 2 von a nach c
    hanoi(1,b,c,a)
    {
      Scheibe 1 von b nach c
    }
  }
  Scheibe 3 von a nach b
  hanoi(2,c,b,a)
  {
    hanoi(1,c,a,b)
    {
      Scheibe 1 von c nach a
    }
    Scheibe 2 von c nach b
    hanoi(1,a,b,c)
    {
      Scheibe 1 von a nach b
    }
  }
}

chiefe

ja jetzt wird es schon viel klarer.
aber eine frage habe ich noch.
wie kommt man auf die scheibe 2 nach der ersten ausgabe von scheibe 1?
also ganz am anfang.
ist der weitergabebetrag der variablen scheibe da nicht 1???

MFK

chiefe schrieb:

wie kommt man auf die scheibe 2 nach der ersten ausgabe von scheibe 1?

Jeder Aufruf von hanoi besteht aus

hanoi
Schritt
hanoi

wobei 1 und 3 nur stattfinden, wenn die Höhe größer als 1 ist. Wenn also der Aufruf von hanoi(2,...) mit seinem Punkt 1 (dem Aufruf von hanoi(1,...)) fertig ist, macht er ganz normal mit seinem Punkt 2 weiter.

also ganz am anfang.
ist der weitergabebetrag der variablen scheibe da nicht 1???

Jeder Aufruf von hanoi hat seinen eigenen Satz an lokalen Variablen (hoehe, von, nach, ueber), und mit dem arbeitet er. Für die untergeordneten Aufrufe werden neue Variablensätze mit anderen Werten erstellt, die nach dem Aufruf auch nicht mehr da sind. Es gibt keine "Weitergabe" aus einem untergeordneten Aufruf zurück in den aufrufenden.

Es gibt nicht nur eine Variable "hoehe", sondern im Verlauf des Beispiels insgesamt acht, allerdings nie mehr als vier gleichzeitig.