Сейчас будет математическая задачка, которую мы решим вроде бы варварским методом, но на самом деле по-умному.
Условия: есть лестница с известным количеством ступенек. На каждом шаге мы можем наступать на каждую ступеньку или шагнуть через одну, пройдя сразу 2 ступеньки за один шаг. Нужно найти число способов, которыми можно подняться по лестнице.
Например, если у лестницы 4 ступеньки, то варианты будут такие:
1→1→1→1
1→1→2
1→2→1
2→1→1
2→2
Сами варианты выводить не нужно, достаточно общего количества.
Мы могли бы решить эту задачу какой-то математикой, но мы не будем этого делать. Мы решим её с помощью программирования.
Вся сложность в этой задаче в том, что на каждом шаге у нас появляется выбор — шагнуть на одну или на две ступеньки.
Чтобы была понятна вся вариативность, нарисуем схему для пяти ступенек:
Если присмотреться к схеме, то видно, что начиная с третьей ступени количество вариантов начинает зависеть от предыдущего и предпредыдущего шага:
- для третьей ступеньки — от количества вариантов на второй и первой;
- для четвёртой ступеньки — от количества вариантов на третьей и второй;
- для пятой ступеньки — от количества вариантов на четвёртой и третьей.
Эта схема отлично укладывается в рекурсию — самоповторяющийся алгоритм, в котором известны только несколько начальных значений, а все остальные считаются на их основе. Единственное, с чем нам осталось разобраться, — с этими начальными значениями.
Если ступенек нет, рекурсия должна вернуть тоже ноль вариантов. Это логично: нет ступенек — нет вариантов, как шагать.
Если ступенька одна, то возвращаем тоже один вариант — это один шаг.
Если ступеньки две, то тут уже два варианта: 1→1 или сразу шагнуть на 2.
А если ступенек 3 и больше, то надо складывать количество вариантов на двух предыдущих этапах. В итоге у нас получилась классическая рекурсия, где на каждом шаге мы вычисляем, сколько вариантов у нас дойти до текущей ступеньки.
Чтобы было удобнее, все расчёты по каждой ступеньке будем хранить в массиве — так проще будет с ними работать. Зная всё это, напишем простую рекурсию на Python:
# функция расчёта количества вариантов
def climb(n):
# разбираем крайние случаи
# если нет ступенек — возвращаем 0 вариантов
if n==0: return 0
# если одна ступенька — её можно перешагнуть только одним способом
if n==1: return 1
# если две ступеньки — то двумя способами: 1→1 или сразу 2
if n==2: return 2
# создаём массив из заданного количества ступенек +1
# в нём будет храниться количество вариантов шагов для очередной ступеньки
dp = [0]*(n+1)
# первую ступеньку можно перешагнуть только одним способом
dp[1] = 1
# вторую — уже двумя способами
dp[2] = 2
# перебираем все ступеньки, начиная с третьей, потому что как пройти первые две, мы уже знаем
for i in range(3,n+1):
# до каждой следующей ступеньки можно добраться одним или двумя шагами с предыдущих
dp[i] = dp[i-1] +dp[i-2]
# в конце — возвращаем количество вариантов для последней ступеньки
return dp[n]
# считаем количество вариантов для пяти ступенек
print(climb(5))После запуска программа выдаст число 8 — значит, мы всё сделали правильно и уложились в 10 минут.
