• 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

VPS Starter Arubacloud
0 głosów
199 wizyt
pytanie zadane 11 listopada 2020 w Matematyka, fizyka, logika przez Wiciorny Ekspert (269,120 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 Maniak (56,900 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 (269,120 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 (56,900 p.)
Chcesz odpowiedź czy może podpowiedź?
komentarz 11 listopada 2020 przez Wiciorny Ekspert (269,120 p.)
(fib(n-m-3+1))
komentarz 11 listopada 2020 przez Whistleroosh Maniak (56,900 p.)
Nie rozumiem

1 odpowiedź

+1 głos
odpowiedź 19 kwietnia 2021 przez J0ker Pasjonat (15,400 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 1,432 wizyt
pytanie zadane 8 grudnia 2016 w Matematyka, fizyka, logika przez DamianW Bywalec (2,080 p.)
0 głosów
1 odpowiedź 280 wizyt
pytanie zadane 24 lutego 2020 w Matematyka, fizyka, logika przez damiang19 Nowicjusz (220 p.)

92,452 zapytań

141,262 odpowiedzi

319,085 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...