Türme von Hanoi - Rekursion

Erecthoma2006 · 06.06.2006, 18:37

Hi,

ich bin gerade beim Thema Rekursion und da wurde als Übung vorgeschlagen mit den Türmen von Hanoi anzufangen. Hier was ich bisher geschafft habe:

PHP-Code:

  <?php

 
function hanoi ($n, $start, $ziel, $hilf) {

    if($n >0) {

        

            hanoi($n-1, $start, $hilf, $ziel);

            echo ("Bewege Scheibe $n vom $start-Platz zum $ziel-Platz.
");

             

    }

}

 
hanoi(3, "Start", "Ziel", "Hilfs");

 
 
?>

Ausgabe:

Bewege Scheibe 1 vom Start-Platz zum Ziel-Platz.
Bewege Scheibe 2 vom Start-Platz zum Hilfs-Platz.
Bewege Scheibe 3 vom Start-Platz zum Ziel-Platz.

Nun verstehe ich nicht wieso in der ersten Zeile Ziel-Platz steht. Müsste dort nicht Hilfsplatz stehen? Ich hoffe jemand kann mir das erklären.

Zergling-new · 06.06.2006, 18:53

In dieser Reihenfolge werden die echo's aufgerufen:
echo von hanoi ($n = 0, "Start", "Hilfs", "Ziel"); // ..wird nie aufgerufen da $n > 0 nicht erfüllt
echo von hanoi (1, "Start", $ziel="Ziel", "Hilfs");
echo von hanoi (2, "Start", $ziel="Hilfs", "Ziel");
echo von hanoi (3, "Start", $ziel="Ziel", "Hilfs");

Du hast Wahrscheinlich auf die Parameter-Reihenfolge des hanoi-Aufrufesgeschaut (also der innerhalb des if-Blocks) und nicht der Funktion selbst.

06.06.2006, 19:20

Und der Algorithmus ist unvollständig.
Vergl. mit http://de.wikipedia.org/wiki/Die_T%C3%BCrme_von_Hanoi

Erecthoma2006 · 06.06.2006, 19:24

Hi

vielen Dank für die sehr schnellen Antworten.

Erecthoma2006 · 07.06.2006, 17:59

Hi,

ich habe mir wirklich die Parameter der Aufrufe angeschaut. Ich habe die Rekursion aber immer noch nicht ganz verstanden.

PHP-Code:

  <?php

 
function test($n,$go, $gogo) {

 
     if ($n>0){

        

    test($n-1,$gogo,$go);

    echo "Ergebnist: $go.
";

 
    }

}

 
echo test(3,"go", "gogo");

 
 
 
?>

Ausgabe:

Ergebnis: go.
Ergebnis: gogo.
Ergebnis: go.

Ich verstehe jetzt nicht wieso in der 3. Rekursionsstufe $go mit go ausgegeben wird. Ich befinde
mich doch jetzt im Aufruf der Funktion test() und dort entspricht doch $go $gogo(=gogo), oder? Ich verstehe nicht wieso in
der ersten Zeile nicht gogo steht.

1. Rekursionsstufe: test (3, $n, $go, $gogo)

gibt test(3-1, $gogo,$go) echo ... zurück

2. Rekursionsstufe: test(3-1, $gogo,$go )

gibt test(2-1,$gogo,$go) echo ... zurück

3. Rekursionsstufe: test (1-1, $gogo, $go)

gibt echo ... zurück

07.06.2006, 18:18

Aufruf: test(3, a, b)
- Aufruf: test(2, b, a);
-- Aufruf: test(1, a, b);
--- Aufruf: test(0, b, a);
--- Ausgabe: a
-- Ausgabe: b
- Ausgabe a

Also ist die erste stattfindene Ausgabe a (oder von mir aus auch go)

Zergling-new · 07.06.2006, 18:21

Du hast es nicht verstanden, weil du schon beim Denken (oder Schreiben) etwas schlamperst:

Zitat:

1. Rekursionsstufe: test (3, $n, $go, $gogo) Arrow gibt test(3-1, $gogo,$go) echo ... zurück

4 Parameter auf einmal?

Zitat:

2. Rekursionsstufe: test(3-1, $gogo,$go ) Arrow gibt test(2-1,$gogo,$go) echo ... zurück

test(3-1, $gogo, $go) und test(2-1, $gogo, $go) kann ja nicht sein, da die Parameter immer wechseln.

Nochmal, ganz einfach:
Du rufst test(3, "go", "gogo") auf.
Damit erzeugst du eben auf jeden Fall ein
echo "3: go";
Demzufolge ein
echo "2: gogo";
Weiter brauchen wir nicht denken, denn ungerade $n's (Anzahl rekursive Aufrufe) bekommen offenbar ein "go" und gerade ein "gogo".
Da das ganze umgedreht ausgegeben wird (denn der Rekursionsaufruf test(..) steht vor echo) bekommst du

PHP-Code:

  1: go

2: gogo

3: go

Erecthoma2006 · 07.06.2006, 18:54

Danke für die Antworten. Jetzt habe ich es verstanden. Ich hatte übersehen, dass die Parameter Ihre Position tauschen. Vielen Dank.

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Thema bewerten
Thema bewerten:

Ähnliche Themen
Thema	Autor	Forum	Antworten	Letzter Beitrag
Rekursion zur Ausgabe von Kategorien und Unterkategorien	goofreezer	PHP Tipps 2008	19	20.06.2008 10:43
Nested Sets oder Rekursion?	litterauspirna	PHP Tipps 2008	8	06.06.2008 16:57
rekursion ist nicht mein freund.... ;-)	Promaetheus	PHP Tipps 2008	6	11.10.2007 18:49
rekursion in php	netdirk	PHP Tipps 2006	10	13.05.2006 12:08
Wie nennt man so etwas? Rekursion bei Klassen?	Andreas	PHP Tipps 2007	3	16.11.2005 12:50
Rekursion als sql	DerDesian	Datenbanken	1	20.04.2005 11:59
Rekursion		PHP Tipps 2004	2	15.06.2004 11:31

06.06.2006, 18:37
Erecthoma2006 Neuer Benutzer Registriert seit: 31.05.2006 Beiträge: 28	Türme von Hanoi - Rekursion Hi, ich bin gerade beim Thema Rekursion und da wurde als Übung vorgeschlagen mit den Türmen von Hanoi anzufangen. Hier was ich bisher geschafft habe: PHP-Code: `<?php function hanoi ($n, $start, $ziel, $hilf) { if($n >0) { hanoi($n-1, $start, $hilf, $ziel); echo ("Bewege Scheibe $n vom $start-Platz zum $ziel-Platz. "); } } hanoi(3, "Start", "Ziel", "Hilfs"); ?>` Ausgabe: Bewege Scheibe 1 vom Start-Platz zum Ziel-Platz. Bewege Scheibe 2 vom Start-Platz zum Hilfs-Platz. Bewege Scheibe 3 vom Start-Platz zum Ziel-Platz. Nun verstehe ich nicht wieso in der ersten Zeile Ziel-Platz steht. Müsste dort nicht Hilfsplatz stehen? Ich hoffe jemand kann mir das erklären.


Mister Ad PHP Code Flüsterer Registriert seit: 21.08.2005 Beiträge: 4682 PHP-Kenntnisse: Fortgeschritten

06.06.2006, 18:53
Zergling-new Erfahrener Benutzer Registriert seit: 21.05.2008 Beiträge: 9.937	In dieser Reihenfolge werden die echo's aufgerufen: echo von hanoi ($n = 0, "Start", "Hilfs", "Ziel"); // ..wird nie aufgerufen da $n > 0 nicht erfüllt echo von hanoi (1, "Start", $ziel="Ziel", "Hilfs"); echo von hanoi (2, "Start", $ziel="Hilfs", "Ziel"); echo von hanoi (3, "Start", $ziel="Ziel", "Hilfs"); Du hast Wahrscheinlich auf die Parameter-Reihenfolge des hanoi-Aufrufesgeschaut (also der innerhalb des if-Blocks) und nicht der Funktion selbst.

06.06.2006, 19:20
Gast Beiträge: n/a	Und der Algorithmus ist unvollständig. Vergl. mit http://de.wikipedia.org/wiki/Die_T%C3%BCrme_von_Hanoi

06.06.2006, 19:24
Erecthoma2006 Neuer Benutzer Registriert seit: 31.05.2006 Beiträge: 28	Hi vielen Dank für die sehr schnellen Antworten.

07.06.2006, 17:59
Erecthoma2006 Neuer Benutzer Registriert seit: 31.05.2006 Beiträge: 28	Hi, ich habe mir wirklich die Parameter der Aufrufe angeschaut. Ich habe die Rekursion aber immer noch nicht ganz verstanden. PHP-Code: `<?php function test($n,$go, $gogo) { if ($n>0){ test($n-1,$gogo,$go); echo "Ergebnist: $go. "; } } echo test(3,"go", "gogo"); ?>` Ausgabe: Ergebnis: go. Ergebnis: gogo. Ergebnis: go. Ich verstehe jetzt nicht wieso in der 3. Rekursionsstufe $go mit go ausgegeben wird. Ich befinde mich doch jetzt im Aufruf der Funktion test() und dort entspricht doch $go $gogo(=gogo), oder? Ich verstehe nicht wieso in der ersten Zeile nicht gogo steht. 1. Rekursionsstufe: test (3, $n, $go, $gogo) gibt test(3-1, $gogo,$go) echo ... zurück 2. Rekursionsstufe: test(3-1, $gogo,$go ) gibt test(2-1,$gogo,$go) echo ... zurück 3. Rekursionsstufe: test (1-1, $gogo, $go) gibt echo ... zurück

07.06.2006, 18:18
Gast Beiträge: n/a	Aufruf: test(3, a, b) - Aufruf: test(2, b, a); -- Aufruf: test(1, a, b); --- Aufruf: test(0, b, a); --- Ausgabe: a -- Ausgabe: b - Ausgabe a Also ist die erste stattfindene Ausgabe a (oder von mir aus auch go)

07.06.2006, 18:54
Erecthoma2006 Neuer Benutzer Registriert seit: 31.05.2006 Beiträge: 28	Danke für die Antworten. Jetzt habe ich es verstanden. Ich hatte übersehen, dass die Parameter Ihre Position tauschen. Vielen Dank.