Считаем способы, как подняться по лестнице
easy

Считаем способы, как подняться по лестнице

Очередная задачка с собеседования

Сейчас будет математическая задачка, которую мы решим вроде бы варварским методом, но на самом деле по-умному.

Условия: есть лестница с известным количеством ступенек. На каждом шаге мы можем наступать на каждую ступеньку или шагнуть через одну, пройдя сразу 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 минут.

Крутая математика для крутых крутанов
Вы прочитали задачу с непростой математикой. Но это не предел: есть математика для аналитиков и дата-сайентистов, и там вообще космос.
Расчехляйте арифмометры и заходите в «Практикум» на продвинутую математику.
Начать бесплатно
Крутая математика для крутых крутанов Крутая математика для крутых крутанов Крутая математика для крутых крутанов Крутая математика для крутых крутанов
Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
Еще по теме
easy