Условие
Лестница состоит из 9 ступенек. Мальчик поднимается от пола на верхнюю ступеньку, каждым шагом переходя либо на следующую ступеньку, либо через одну (на 2 ступеньки выше). Ступенька № 4 сломана, наступать на неё нельзя. Сколькими способами он может подняться на верхнюю ступеньку?
Подсказка
С каких ступенек можно попасть на данную ступеньку одним шагом?
Считайте число способов для каждой ступеньки по порядку снизу вверх.
Показать ответ
15
Пошаговое решение
- Вводим обозначения
Пусть W(k) — число способов добраться до k-й ступеньки. На k-ю ступеньку можно попасть только двумя способами: последним шагом с (k−1)-й или прыжком через одну с (k−2)-й. Поэтому W(k)=W(k−1)+W(k−2).
- Находим начальные значения
До первой ступеньки — один способ (один шаг), до второй — два: 1+1 или сразу 2. Удобно считать, что W(0)=1: стоять внизу можно одним способом.
- Учитываем сломанную ступеньку
На ступеньку № 4 наступать нельзя, поэтому W(4)=0: через неё можно только перешагнуть. Дальше формула та же: W(5)=W(4)+W(3)=0+3=3.
- Заполняем таблицу по порядку
W(1)=1, W(2)=2, W(3)=3, W(4)=0, W(5)=3, W(6)=3, W(7)=6, W(8)=9, W(9)=15. Каждое число — сумма двух предыдущих.
- Проверяем на маленьком примере
Для трёх ступенек способы 1+1+1, 1+2, 2+1 — их 3, как и в таблице. Значит, на 9-ю ступеньку можно подняться 15 способами.
Ответ: 15