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