Poszukuje pomysłu na wzór - kombinatoryczny, algorytmiczny. Zadanko z wyborem

pytanie zadane 11 listopada 2020 w Matematyka, fizyka, logika przez Wiciorny Ekspert (280,610 p.)

Hej, ostatnio ktoś w pracy rzucił hasłem, siedzę troszkę już nad tym... ale nie mogę wymyśleć w którą kombinatoryczną stronę iść. Cel jest znalezienie wzoru :
Na ile sposobów możemy zejść z n-tego szczebla drabiny, jeśli na każdym szczeblu możemy zejść na 3 sposoby, o 1, o 2 lub o 3 szczeble :)... i problem tutaj wiadomo stanowi fakt, tego że schodząc o 3 szczeble czy 2, pojawia się problem że nie będzie to 3 do n-tej.

Analizując sobie po kolei wartości ciąg się układa od n =1 : 1, 2, 4, 6 , 12 ... ale tu jest coś bardziej skomplikowanego.
Dzięki może a nóż ktoś podpowie :)

Pokaż 8 poprzednich komentarzy

1	komentarz 11 listopada 2020 przez Whistleroosh Maniak (57,400 p.) No tak. To jest typowe zadanie na programowanie dynamiczne. Tylko przeważnie pytają o tę wersję gdzie można schodzić albo o jeden, albo o dwa schodki

komentarz 11 listopada 2020 przez Wiciorny Ekspert (280,610 p.)

właśnie dla 2 możliwości np bez 3 schodków, to wiedziałbym że jest coś z fibbonaci... ale tutaj jest coś z tym jak pisałem, też to znalazłeem ( n-1)(n-2)(n-3), ale tu jest ukryty w zadaniu na pewno fibonnaci rekurencja tylko z jakimis dodatkowymi - elementami

komentarz 11 listopada 2020 przez Whistleroosh Maniak (57,400 p.)

Chcesz odpowiedź czy może podpowiedź?

komentarz 11 listopada 2020 przez Wiciorny Ekspert (280,610 p.)

(fib(n-m-3+1))

komentarz 11 listopada 2020 przez Whistleroosh Maniak (57,400 p.)

Nie rozumiem

1 odpowiedź

odpowiedź 19 kwietnia 2021 przez J0ker Pasjonat (15,420 p.)

Ja bym ułożył równanie rekurencyjne

Notabene gdyby można było schodzić o 1 lub 2 stopnie (bez 3) to rozwiązaniem zadania byłaby n-ta liczba ciągu Fibonacciego (bo mielibysmy Tn = Tn-1 + Tn-2).

Dane początkowe:

- z drabiyny wysokości 1 na 1 sposobów

- z drabiny wysokości 2 na 2 sposoby

- z drabiny wysokości 3 na 4 sposoby

Niech Tn oznacza ilość sposobów zejścia z drabiny wysokości n dla n>=4

Wówczas Tn = Tn-1 + Tn-2 + Tn-3

Czyli mamy x^n - x ^n-1 - x^n-2 - x^n-3 = 0

czyli x^3-x^2-x^1-1=0

no i to jedno rzeczywiste rozwiązanie ~1,8393, pozostałe 2 są zespolone nierzeczywiste (ja wiem nawet że to rzeczywiste jest niewymierne).

Pozostaje zakończyć zadanie analogicznie jak w przypadku Fibonacciego i otrzymamy ładniejszy lub brzydszy (pewnie brzydszy) wzorek.

Czy to Pan się kłócił fanatycznie ze mną kilka lat temu na tym forum o tym że studia i teoria są g*wnem, tylko jak najszybciej do pracy trzepać projekty i tak dalej? Jeśli nie to przepraszam, może źle zapamiętałem nick. Pamiętam, że tamten człowiek chyba skończył informatykę w Krakowie.