Задача
COM-B1-M10-P019 Шаги \(1\) и \(3\)
#19
★★★☆☆ Уровень 3 из 5
Сколькими способами можно подняться на \(12\) ступенек, если за ход можно подняться на \(1\) или \(3\) ступеньки?
Последний шаг имеет длину \(1\) или \(3\).
Пусть \(a_n\) - число способов. Тогда \(a_n=a_{n-1}+a_{n-3}\), где \(a_0=1\), \(a_1=1\), \(a_2=1\). Получаем \(a_3=2\), \(a_4=3\), \(a_5=4\), \(a_6=6\), \(a_7=9\), \(a_8=13\), \(a_9=19\), \(a_{10}=28\), \(a_{11}=41\), \(a_{12}=60\).
Показывает рекурсию с пропуском \(a_{n-2}\).