Algorithmen und Datenstrukturen · Middle · Frage 42 von 75
Treppensteigen: man kann 1 oder 2 Stufen auf einmal nehmen. Wie viele Wege gibt es, n Stufen zu steigen?
- 1
ways(n) = 2 ** n, weil jeder Schritt zwei Möglichkeiten hat - 2
ways(n) = n * 2, ein oder zwei Schritte pro Stufe - 3
ways(n) = ways(n - 1) + ways(n - 2), die Fibonacci-Rekurrenz
Antwort zeigen
Richtige Antwort: ways(n) = ways(n - 1) + ways(n - 2), die Fibonacci-Rekurrenz
Erklärung
Der letzte Zug ist entweder ein einzelner Schritt von Stufe n - 1 oder ein doppelter von n - 2, die Anzahlen addieren sich also. Mit zwei Variablen ist es O(n) Zeit und O(1) Speicher.