Na ile różnych sposobów można wejść po drabinie liczącej 16 szczebli jeśli możemy pokonywać 1,2,3 lub 4 szczeble podczas jednego kroku.
ilość sposobów wchodzenia po drabinie
Rozpoczęty przez Jamnowaczek89, Dec 22 2007 22:14
2 odpowiedzi w tym temacie
#1
Napisano 22.12.2007 - 22:14
Napisano 25.09.2011 - 17:55
#3
Napisano 23.12.2007 - 17:27
Rozwiązanie:
Wprowadźmy oznaczenie S(n) - jest to ilość możliwości wejścia po drabinie złożonej z n stopni, wchodząc co 1,2,3 lub 4 stopnie.
Oczywiście:
Dalej zauważamy, że licząc S(n):
-zaczynając od kroku o 4 szczeble, pozostałe kroki muszą dać n-4 stopni ( S(n-4) możliwości )
-zaczynając od kroku o 3 szczeble, mamy potem S(n-3) możliwości
-zaczynając od kroku o 2 szczeble, mamy potem S(n-2) możliwości
-zaczynając od kroku o 1 szczebel, mamy potem S(n-1) możliwości
Otrzymujemy więc wzór rekurencyjny:
I liczymy ze wzoru kolejne S(n):
Rekurencję tę można by próbować rozwiązywać szukając wzoru ogólnego ciągu, ale próbując tego napotkałem problemy techniczne. Inna sprawa że się na tym słabo znam
Wprowadźmy oznaczenie S(n) - jest to ilość możliwości wejścia po drabinie złożonej z n stopni, wchodząc co 1,2,3 lub 4 stopnie.
Oczywiście:
Dalej zauważamy, że licząc S(n):
-zaczynając od kroku o 4 szczeble, pozostałe kroki muszą dać n-4 stopni ( S(n-4) możliwości )
-zaczynając od kroku o 3 szczeble, mamy potem S(n-3) możliwości
-zaczynając od kroku o 2 szczeble, mamy potem S(n-2) możliwości
-zaczynając od kroku o 1 szczebel, mamy potem S(n-1) możliwości
Otrzymujemy więc wzór rekurencyjny:
I liczymy ze wzoru kolejne S(n):
Rekurencję tę można by próbować rozwiązywać szukając wzoru ogólnego ciągu, ale próbując tego napotkałem problemy techniczne. Inna sprawa że się na tym słabo znam
"It is so hard to believe, that all this is the way that it has to be."
It's five o'clock - Aphrodite's Child
Prawdopodobieństwo może być co najwyżej równe 1!
It's five o'clock - Aphrodite's Child
Prawdopodobieństwo może być co najwyżej równe 1!