Informatik, kann einer für Idioten erklären, warum die fibonaci Folge das Treppenproblem löst?

Hi, ich habe ein Programm entwickelt, welches das hier beschriebene: https://www.gutefrage.net/frage/treppenproblem-mit-java#comment-317872275

Treppenproblem löst.

Methodenname(anzahltreppen-1,k+"-1");

Methodenname(anzahltreppen-2,k+"-2");

Dieser Rekursionsschritt in der Methode Methodenname löst das Problem, aber warum? Wie kann man das nachvollziehen?

Also meine Frage ist nur, warum löst die fibonaci-Folge dieses Problem? Das macht doch keinen Sinn, wie kann man das verstehen? Könnte jemand die Logik idiotensicher erklären?

Answer 1

[procoder42]

Jain, die Anzahl der Kombinationen ergibt sich aus der Fibonacci Folge.

Der Rekursionsboden ist der Fall, wenn du auf der letzten bzw vorletzten Stufe stehst. Das ist ein einfacheres Problem, da es nur eine resp. 2 Möglichkeiten zur Besteigung der Treppe gibt.

Die Rekursion ergibt sich aus folgender Erkenntniss: Wenn du auf der vor-vorletzten Stufe stehst, kannst du entweder auf die vor letzte oder letzte Stufe steigen. D.h. du hast insgesamt count(letzte) + count(vorlezte) Möglichkeiten auf die Treppe zu kommen. Und das kannst du jetzt so weiterspinnen, bis du "vor der Treppe" angekommen bist.

Und das entspricht der rekursiven Definition der Fibonacci Folge: neue Zahl = letzte Zahl + vorletzte Zahl

Comments

[procoder42]

Nachtrag: Dein Code framed das Problem ein wenig anders (weil du ja alle Wege enumerierst), da du quasi einen Baum aller Kombinationen aufbaust, bis du beim Rekursionsende n=0 angekommen bist.

Wenn es nur um die Anzahl der Möglichkeiten ginge, würde ich deine Lösung als äußerst ineffizient betrachten. Hier käme die Fibonacci Reihe ins Spiel, weil wir analog mittels Dynamischer Programmierunt in linearer Zeit + konstantem Speicher eine Lösung finden können.

Die eigentlichen Kombinationen bekommst du über die Fibonacci Reihe aber nicht raus, daher das "Jain" in der Antwort