• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

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

Fiszki IT
Fiszki IT
0 głosów
89 wizyt
pytanie zadane 11 listopada 2020 w Matematyka, fizyka, logika przez Wiciorny Mędrzec (165,520 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 :) 
 

1
komentarz 11 listopada 2020 przez Whistleroosh Nałogowiec (29,500 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 Mędrzec (165,520 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 Nałogowiec (29,500 p.)
Chcesz odpowiedź czy może podpowiedź?
komentarz 11 listopada 2020 przez Wiciorny Mędrzec (165,520 p.)
(fib(n-m-3+1))
komentarz 11 listopada 2020 przez Whistleroosh Nałogowiec (29,500 p.)
Nie rozumiem

1 odpowiedź

+1 głos
odpowiedź 19 kwietnia przez J0ker Stary wyjadacz (11,790 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.

Podobne pytania

+1 głos
2 odpowiedzi 792 wizyt
pytanie zadane 8 grudnia 2016 w Matematyka, fizyka, logika przez DamianW Bywalec (2,070 p.)
0 głosów
1 odpowiedź 136 wizyt
pytanie zadane 24 lutego 2020 w Matematyka, fizyka, logika przez damiang19 Nowicjusz (220 p.)
0 głosów
2 odpowiedzi 140 wizyt
Porady nie od parady
Nie wiesz jak poprawnie zredagować pytanie lub pragniesz poznać którąś z funkcji forum? Odwiedź podstronę Pomoc (FAQ) dostępną w menu pod ikoną apteczki.FAQ

84,702 zapytań

133,503 odpowiedzi

295,887 komentarzy

55,979 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...