|
Путь к счастью
Чтоб вы знали: путь к счастью - это вовсе не дорога, а лестница. Лестница о
тридцати ступенях. Hо мало по ней просто прошагать. Для счастья нужно
пройти все ступени только вперёд таким сочетанием разных шагов, как этого ещё
никто не делал. А шаги получаются только трёх видов:
1. Через две ступеньки;
2. Через одну ступеньку;
3. Hа следующую ступеньку.
Сколько людей смогут обрести счастье, пройдя этой лестницей?
|
|
53 798 080 счастливцев.
Обозначим через S(n) число людей, которые могут пройти по лестнице в n
ступенек. Тогда S(1)=1 (один одинарный шаг), S(2)=2 (два одинарных, либо один
двойной), S(3)=4 (одинарный+двойной, двойной+одинарный, три одинарных, один
тройной). Дальше. Свяжем последовательность S(n) рекуррентной формулой. Все
последовательности шагов заканчиваются либо одинарным, либо двойным, либо
тройным шагом. Тогда число разных людей, закончивших восхождение на n-ю
ступеньку одинарным шагом равно S(n-1); число разных людей, закончивших
восхождение на n-ю ступеньку двойным шагом равно S(n-2); число разных людей,
закончивших восхождение на n-ю ступеньку тройным шагом равно S(n-3). Значит
S(n)=S(n-1)+S(n-2)+S(n-3). Что-то похожее на числа Фибоначчи, только
суммируются не предыдущие 2 члена, а предыдущие 3.
|
