Дорога к счастью1. Через две ступеньки; 2. Через одну ступеньку; 3. На следующую ступеньку. Сколько людей смогут обрести счастье, пройдя этой лестницей? РешениеОбозначим через 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. |