Sposoby schodzenia ze schodów

Lonc · Post autor: **Lonc** » 25 wrz 2010, o 20:45

Janek ma do pokonania 12 schodów. Może na raz pokonywać 1, 2 lub 3 schodki. Na ile sposobów Janek może zejść ze schodów?

Proszę o pomysł jak to policzyć nie wypisując wszystkich kombinacji

Konikov · Post autor: **Konikov** » 25 wrz 2010, o 21:21

Rekurencja ;D

\(\displaystyle{ s_0 = 1\\
s_1 = 1\\
s_2 = 2\\
s_n = s_{n-1} + s_{n-2} + s_{n-3}}\)

Wystarczy pojechać metodą równania charakterystycznego.

Voila!

Lonc · Post autor: **Lonc** » 25 wrz 2010, o 22:16

A jakiś sposób dla niezaprzyjaźnionych z równaniem charakterystycznym?

Fingon · Post autor: **Fingon** » 25 wrz 2010, o 22:19

12 jest małe więc można policzyć na palcach, jeśli natomiast uznamy, że 12 jest duże, to można wykorzystać szybkie potęgowanie macierzy, wymyślając wcześniej odpowiednie macierze.

Konikov · Post autor: **Konikov** » 25 wrz 2010, o 22:29

Lonc pisze:A jakiś sposób dla niezaprzyjaźnionych z równaniem charakterystycznym?

Przeczytać: 25578.htm
Krótkie i proste ;]