Broken Ways (Logikproblem)

Dieses Problem wurde auf der Website der Newton School unter „Frage des Tages 9. Januar 2023“ veröffentlicht.

Problemstellung:

Newton möchte die Spitze einer Treppe erreichen, die einige kaputte Stufen hat (er kann diese Stufen nicht besuchen). Er kann 1 oder 2 Stufen gleichzeitig erklimmen.

Beispiel einer Treppe mit 15 Stufen, wobei die Stufen 3 und 9 unterbrochen sind. Die gültigen Schritte für den Besuch sind: 1,2, 4,5,6,7,8, 10,11,12,13,14,15.

Eine Möglichkeit, die Spitze dieser Treppe zu erreichen, besteht darin, die Stufen 2,4,5,7,8,10,12,14,15 zu besuchen (manchmal stieg Newton eine Stufe hinauf und andere stieg er zwei Stufen hinauf).

Ziel des Problems ist es, herauszufinden, auf wie vielen verschiedenen Wegen Newton das obere Ende der Treppe erreichen kann.

Hier zeige ich eine Lösung:

Dieses Problem erinnert an die „Fibonacci-Folge“. Aber warum? Denn da Sie eine Stufe nur von Stufe 1 oder Stufe 2 aus erreichen können, ist die Anzahl der Möglichkeiten, wie Sie eine Stufe erreichen können, die Summe aus „Möglichkeiten, wie Sie Stufe 1 erreichen können“ + „Möglichkeiten, wie Sie Stufe 2 erreichen können“. “.

Um Stufe 1 zu erreichen, haben Sie also nur einen Weg (Klettern vom Boden zu Stufe 1); Um Stufe 2 zu erreichen, haben Sie zwei Möglichkeiten (vom Boden direkt auf Stufe 2 klettern oder von Stufe 1 aufsteigen), um Stufe 3 zu erreichen, haben Sie 3 Möglichkeiten (1 Weg von Stufe 1 + 2 Wege von Stufe 2), um Stufe 4 zu erreichen Sie haben 5 Wege (2 Wege aus Schritt 2 + 3 Wege aus Schritt 3), um Schritt 5 zu erreichen, haben Sie 8 Wege (3 Wege aus Schritt 3 + 5 Wege aus Schritt 4) und so weiter bis zum letzten Schritt.

Aber das ist genau die Fibonacci-Folge! Ja, aber dieses Problem hat eine Wendung, es wurden „kaputte Schritte“ hinzugefügt. Okay, kein Problem, da Newton die kaputten Stufen nicht besuchen kann, legen Sie einfach 0 Wege fest, um sie zu erreichen.

Zurück zu unserem Beispiel: Wenn die Schritte 3 und 9 unterbrochen sind, haben wir diese „Fibonacci Broken Sequence“ : 1, 2, 0, 2, 2, 4, 6, 10, 0, 10, 10, 20, 30, 50, 80.

Bei dieser Treppe hat Newton also 80 verschiedene Möglichkeiten, sie hinaufzusteigen.

Jetzt können Sie den Fibonacci-Broken-Sequence-Algorithmus in Ihrer bevorzugten Programmiersprache implementieren und auf die Website der Newton School hochladen , wo es in der Sitzung „Frage des Tages“ viele coole Probleme zu lösen gibt.

Sich amüsieren!