Worst-Case-Denken

Die Hofstädter-Folge

Letztmalig dran rumgefummelt: 28.01.08 07:36:27

Ähnlich wie die Fibonacci-Zahlen gibt auch die Hofstädter-Funktion einen rekursiven Lösungsalgorithmus vor - wobei sich die Folge nicht ganz so progressiv verhält, wie dies bei den Fibonacci-Zahlen der Fall ist.

1. Problembeschreibung
2. Hintergründe und Zusammenhänge - Einordnung in Klassen
3. Lösungsalgorithmen
4. Programmvorschläge
5. Zusammenfassung
6. Weiterführende Literatur
7. Linkliste zum Thema

Klassische algorithmisch lösbare Probleme

Logo für die Hofstädter-Funktion

begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-)

Informatik-Profi-Wissen

Quellen:

Lehr- und Übungsbuch Informatik Band 1 - 5 Seite ???

Technische und Theoretische Informatik Seite ???

1. Problembeschreibung

Die Bildungsvorschrift für die Hofstädter-Folge - sie lautet:

hof (1) = 1

hof (2) = 1

hof (n) = hof (n - hof (n - 1)) + hof (n - hof (hof (n - 2))) für n >= 2

h₁ = 1

h₂ = 1

h₃ = h_{3 - 2} + h_{3 - 2}= h₁+ h₂= 1 + 1 = 2

h₄ = h_{4 - 2} + h_{4 - 1}= h₂+ h₃= 1 + 2 = 3

h₅ = h_{5 - 3} + h_{5 - 2}= h₂+ h₃= 1 + 2 = 3

h₆ = h_{6 - 3} + h_{6 - 2}= h₃+ h₃= 3 + 2 = 4

2. Hintergründe, Zusammenhänge - Einordnung in Klassen

Der Lösungsalgorithmus für die Hofstädter-Folge

effiziente Lösung nur als rekursiver Algorithmus
n-polynomialer Aufwand

3. Lösungsalgorithmus

	verbale Problemlösungsstrategie:

4. Programmvorschläge

FUNCTION Hof (x :LONGINT) :LONGINT;

BEGIN
IF x <= 2 THEN Hof := 1
ELSE Hof := Hof (x - Hof (x - 1)) + Hof (x - Hof (x - 2))
END;

Wie unschwer zu erkennen ist, handelt es sich um eine vernestete Form der Rekursion. Sie trägt ähnliche Züge wie die Ackermann-Funktion. Beim Schreibtischtest der Hofstädter-Funktion ergab sich schon bei der Startzahl 5 eine Wulst an Funktionsaufrufen. Die Übersichtlichkeit war kaum noch zu wahren. Die immer neuen Funktionsaufrufe innerhalb der Funktion ließen sich kaum noch zahlenmäßig nachvollziehen.
Beim Versuch, diese Hofstädter-Funktion in eine endrekursive und damit in eine lineare Form zu überführen, bin ich eindeutig gescheitert. Die Umsetzung hätte erfordert, dass beide Funktionsaufrufe (Summanden) zu einem Aufruf zusammengefügt werden müssten. Da aber innerhalb des Summanden wieder die Hofstädter-Funktion aufgerufen wird, ist es nicht möglich gewesen, diese als Parameter zu definieren, die ohne wiederholten Funktionsaufruf übergeben werden könnten. Ähnliches trifft auch für die Ackermann-Funktion zu.

5. Zusammenfassung

der Lösungsalgorithmus der Türme von Hanoi ist nicht komplex, jedoch schon mit geringer Anzahl n mächtig - er ist n-polinomial
es muss also insgesamt hoher Lösungsaufwand betrieben werden - auch ein Computer wird für n=1000 in absehbarer Zeit keine Lösung bringen

6. Weiterführende Literatur

der Lösungsalgorithmus der Türme von Hanoi ist nicht komplex, jedoch schon mit geringer Anzahl n mächtig
es muss also insgesamt hoher Lösungsaufwand betrieben werden - auch ein Computer wird für n=1000 in absehbarer Zeit keine Lösung bringen

7. Links zum Thema

Viele gibt es - die meisten sind JAVA-basierte Spiele, um den erkannten Lösungsalgorithmus nach zu vollziehen. Wie gesagt, wenn Du vor hast, das Spiel noch am laufenden Tag zu beenden, verwnde keine Scheibenzahl größer 20 - das ist dann schon nicht mehr zu schaffen.

http://www.blinde-kuh.de/spiele/hanoi/
http://www.cut-the-knot.org/recurrence/hanoi.shtml

zur Hauptseite

... dieser Text wurde nach den Regeln irgendeiner Rechtschreibreform verfasst - ich hab' irgendwann einmal beschlossen, an diesem Zirkus nicht mehr teilzunehmen ;-)

„Dieses Land braucht eine Steuerreform, dieses Land braucht eine Rentenreform - wir schreiben Schiffahrt mit drei „f“!“

Diddi Hallervorden, dt. Komiker und Kabarettist

Diese Seite wurde ohne Zusatz irgendwelcher Konversationsstoffe erstellt ;-)

	Der Lösungsalgorithmus für die Hofstädter-Folge
	effiziente Lösung nur als rekursiver Algorithmus
	n-polynomialer Aufwand



	FUNCTION Hof (x :LONGINT) :LONGINT; BEGIN IF x <= 2 THEN Hof := 1 ELSE Hof := Hof (x - Hof (x - 1)) + Hof (x - Hof (x - 2)) END;
	Wie unschwer zu erkennen ist, handelt es sich um eine vernestete Form der Rekursion. Sie trägt ähnliche Züge wie die Ackermann-Funktion. Beim Schreibtischtest der Hofstädter-Funktion ergab sich schon bei der Startzahl 5 eine Wulst an Funktionsaufrufen. Die Übersichtlichkeit war kaum noch zu wahren. Die immer neuen Funktionsaufrufe innerhalb der Funktion ließen sich kaum noch zahlenmäßig nachvollziehen. Beim Versuch, diese Hofstädter-Funktion in eine endrekursive und damit in eine lineare Form zu überführen, bin ich eindeutig gescheitert. Die Umsetzung hätte erfordert, dass beide Funktionsaufrufe (Summanden) zu einem Aufruf zusammengefügt werden müssten. Da aber innerhalb des Summanden wieder die Hofstädter-Funktion aufgerufen wird, ist es nicht möglich gewesen, diese als Parameter zu definieren, die ohne wiederholten Funktionsaufruf übergeben werden könnten. Ähnliches trifft auch für die Ackermann-Funktion zu.


	der Lösungsalgorithmus der Türme von Hanoi ist nicht komplex, jedoch schon mit geringer Anzahl n mächtig - er ist n-polinomial
	es muss also insgesamt hoher Lösungsaufwand betrieben werden - auch ein Computer wird für n=1000 in absehbarer Zeit keine Lösung bringen

	Viele gibt es - die meisten sind JAVA-basierte Spiele, um den erkannten Lösungsalgorithmus nach zu vollziehen. Wie gesagt, wenn Du vor hast, das Spiel noch am laufenden Tag zu beenden, verwnde keine Scheibenzahl größer 20 - das ist dann schon nicht mehr zu schaffen.
	http://www.blinde-kuh.de/spiele/hanoi/
	http://www.cut-the-knot.org/recurrence/hanoi.shtml