Złamane drogi (problem z logiką)

Problem ten został opublikowany na stronie internetowej Newton School, „Pytanie dnia 9/styczeń/2023”.

Sformułowanie problemu:

Newton chce dotrzeć na szczyt schodów, na których są zepsute stopnie (nie może ich odwiedzić). Potrafi wspiąć się po 1 lub 2 stopniach na raz.

Przykład klatki schodowej składającej się z 15 stopni z przerwanymi stopniami 3 i 9. Prawidłowe kroki do odwiedzenia to: 1,2, 4,5,6,7,8, 10,11,12,13,14,15.

Jednym ze sposobów dotarcia na szczyt tej klatki schodowej jest wejście po stopniach: 2,4,5,7,8,10,12,14,15 (czasami Newton wspiął się na 1 stopień, a innym razem na 2 stopnie).

Celem zadania jest znalezienie liczby różnych sposobów, którymi Newton może dotrzeć na szczyt schodów.

Tutaj pokazuję jedno rozwiązanie:

Ten problem zapamiętuje „ciąg Fibonacciego”. Ale dlaczego? Ponieważ możesz osiągnąć krok tylko od kroku 1 lub kroku 2, liczba sposobów na osiągnięcie kroku jest sumą „sposobów na dojście do kroku 1” + „sposobów na dotarcie do kroku 2” ”.

Tak więc, aby dotrzeć do stopnia 1, masz tylko 1 sposób (wspinaczka z ziemi do stopnia 1); aby osiągnąć stopień 2 masz 2 sposoby (wspinaczka z ziemi bezpośrednio do stopnia 2 lub wspinaczka od stopnia 1), aby dotrzeć do stopnia 3 masz 3 sposoby (1 sposób z poziomu 1 + 2 sposoby z poziomu 2), aby dotrzeć do stopnia 4 ty masz 5 dróg (2 drogi z kroku 2 + 3 drogi z kroku 3), aby dojść do kroku 5 masz 8 dróg (3 drogi z kroku 3 + 5 dróg z kroku 4) i tak dalej, aż do ostatniego kroku.

Ale to jest właśnie Ciąg Fibonacciego! Tak, ale ten problem ma niespodziankę, dodano „zepsute stopnie” . Dobra, nie ma problemu, ponieważ Newton nie może odwiedzać zepsutych stopni, po prostu ustaw 0 sposobów dotarcia do nich.

Wracając do naszego przykładu, z przerwanymi krokami 3 i 9, mamy „przerwaną sekwencję Fibonacciego” : 1, 2, 0, 2, 2, 4, 6, 10, 0, 10, 10, 20, 30, 50, 80.

Więc na tych schodach Newton ma 80 różnych sposobów, aby się po nich wspiąć.

Teraz możesz zaimplementować algorytm łamanych ciągów Fibonacciego w swoim ulubionym języku programowania i przesłać go na stronę Newton School , która zawiera wiele fajnych problemów do rozwiązania w sesji Pytanie dnia.

Baw się dobrze!