Matematické Fórum

pajuska79 · 25. 04. 2014 13:15

Ahoj všichni :),
příklad : Používám schody raději než výtah. Když pospíchám beru schody po dvou. Jindy šlápnu na každý. Pokud používám následující : krok (K) na následující schod a skok ( S) což je vynechání jednoho schodu . Kolika ruznými zpusoby mohu zdolat n schodu ?

Napr,. pro pocet schodu 4
1. KKKKK
2.KKS
3.KSK
4.SKK
5.SS
5 ruzných zpusobu pro prekonání 4 schodu ( jsme schopni vypsat )

Hypoteza : Existuje Fn+1 zpusobu jak prekonat n schodu.
Indukcí :
Pro n=1 platí
Predpokladejme, ze na schod n-2 se dostanete Fn-1 zpuosby a na schod n-1 Fn zpusoby. Dokazme na schod n se dostaneme Fn+1.

Na schod n se dostaneme bud skokem ze schodu n-2 nebo krokem ze schodu n-1. Dle indukcniho predpokladu to znamena, za na schod n-2 se dostanu Fn-1 zpusoby a na schod n-1 Fn zpusoby, coz znamená ze na schod n se dostanu Fn-1 + Fn zpusoby coz je Fn+1 zpusoby ( hypoteza overena).

Dotud tomu chápu .
Co kdyz ale polozíme otázku typu :
Kolik je zpusobu pro napr. n= 150 schodu ?

Dokáže mě někdo prosím nějak poradit popípade názorne ukaáza jaký součet či co vlastne vbc využít ?

děkuju moc :))

Eratosthenes

ahoj ↑ pajuska79:,

právě jsi indukcí dokázal, že n schodů překonáš n+1 způsoby. Pokud je to pravda, pak na 150 schodů je 151 způsobů. Ale pravda to není. Pro n=1, 2, 3 to totiž neplatí. Tam je těch způsobů jenom n.

PS: Až teď jsem si všiml, že to máš "Fn+1" a ne je "n+1". Je-li Fn Fibonacciho posloupnost, pak to opravdu vypadá rozumně a odpověď pro 500 schodů by byla rovněž jednoduchá - stačí zjistit F500 ...

pajuska79 · 25. 04. 2014 14:30

Děkuju moc za reakci :)..

A jak prosím zjistím F500?
Nemužu si to dát nějak dohromady :/

Je na to nějaký vzorec ?
Děkuju :)

SO(4) · 25. 04. 2014 16:15

Viz kapitola Explicitní vyjádření na Wiki:
http://cs.wikipedia.org/wiki/Fibonacciho_posloupnost
Na tom vzorci je zajímavé, že se vždy dvě iracionální čísla sečtou tak, že výsledek je celé číslo.

Eratosthenes · 25. 04. 2014 17:15

↑ SO(4):

SO(4) napsal(a):
Na tom vzorci je zajímavé, že se vždy dvě iracionální čísla sečtou tak, že výsledek je celé číslo.

To těžko.

$\frac {\varphi ^2} {\sqrt 5} - \frac {$1- \varphi $^2} {\sqrt 5} \not \in \mathbb{Q}$

SO(4) · 25. 04. 2014 18:07

To sis asi špatně dosadil, protože hodnota výrazu, o kterém píšeš, je 1. Vzorec z Wikipedie jsem teď zkoušel pro několik $n$ a výsledek je vždy celočíselný. Zkus si pohrát tady.

pajuska79 · 29. 04. 2014 12:30

↑ SO(4):

A může mě někdo ukázat tedy dosazení a výsledek např pro počet schodů 150 ?
Pořád se v tom nějak ztrácím .
Děkuji moc

Rumburak

↑ pajuska79:

Ahoj. Připojím pár poznámek.

Nech't $a_n$ je počet způsobů, jak zdolat $n$ schodů. Zřejmě

(1) $a_1 = 1$ ... vystoupíme na tento schod (K) ,

(2) $a_2 = 2$ ... (KK) , (S) ,

(3) $a_{n+2} = a_{n+1} + a_n$ .

Snadné odůvodnění vztahu (3) :
Výstup do $n+2$ schodů zahájíme buďto krokem (K) a pak zbude zdolat ještě $n+1$ schodů $a_{n+1}$ způsoby,
nebo skokem (S) a pak zbude zdolat ještě $n$ schodů $a_n$ způsoby. Vskutku tedy jde o Fibonacciho posloupnost.
Explicitní vyjádření jejího n-tého členu jako funkce proměnné $n$ lze nalézt metodami, jimiž se řeší lineární
diferenční rovnice, jejichž příkladem je rovnice (3).

Honzc · 30. 04. 2014 10:44

↑ pajuska79:
Jenom poznámka.
Ja ti odvodil ↑ Rumburak: bude řada pro schody od n=1 taková
1,2,3,5,8,13,...
Protože Fibonacciho posloupnost (od n=1)
1,1,2,3,5,8,13,...
budeš při výpočtu muset pro n schodů počítat F.poslounost pro n+1
Ještě ti napíšu jeden vzoreček pro výpočet Fibonacciho čísla $F_{n}$ (to je n-tého F.čísla)
$F_{n}=[\frac{\varphi ^{n}}{\sqrt{5}}]$ kde $\varphi =\frac{1+\sqrt{5}}{2}$ a $[]$ značí zaokrouhelní na nejbližší celé číslo.

↑ SO(4): a ↑ Eratosthenes:
Ten voreček $\frac {\varphi ^n} {\sqrt 5} - \frac {$1- \varphi $^n} {\sqrt 5}$ se dá přepsat na $F_{n}=\frac{(1+\sqrt{5})^{n}-(1-\sqrt{5})^{n}}{2^{n}\sqrt{5}}$
a z toho je vidět (binomický rozvoj), že se v čitateli odečtou členy neobsahující výraz $\sqrt{5}$ a tudíš pak se $\sqrt{5}$ v čitateli vykrátí s $\sqrt{5}$ ve jmenovateli. a dokonce součet čísel v čitateli se dá rozložit na $2^{n}\cdot x$ a po vykrácení dostaneme celé číslo a to $F_{n}$