Question

В торговом центре остановился эскалатор, а Андрею срочно нужно подняться наверх. За один шаг он может подняться на 1, 2 или 3 ступеньки. Найдите количество способов добраться с текущей ступеньки эскалатора ровно на 11 ступенек вверх. Необходимо привести развёрнутое решение и (или) код программы, который решает данную задачу (если выбираете второй способ, то опишите алгоритм программы, а также укажите использованный язык программирования и его версию). Решение двумя способами будет оценено дополнительными баллами.

Answer 1

Один из способов:
def count_ways(n): # n -> количество ступенек

   if n == 0: # если нулевая ступенька

       return 1 # возвращаем 1

   if n < 0: # если негативное число

       return 0 # возвращаем 0

   return count_ways(n - 1) + count_ways(n - 2) + count_ways(n - 3) # возвращаем сумму всех вариантов

print(count_ways(11))

#программа написана на языке Python 3.6.5

Answer 2

Для решения этой задачи можно воспользоваться динамическим программированием. Пусть $dp[i]$ обозначает количество способов добраться до ступеньки номер $i$. Тогда:

$dp[i] = dp[i-1] + dp[i-2] + dp[i-3]$

с начальными значениями $dp[0] = 1, dp[1] = 1, dp[2] = 2$, так как для 0 ступенек есть только один способ - не делать шагов, для 1 ступеньки тоже только один способ - сделать один шаг, и для 2 ступенек два способа: сделать два одноступенчатых шага или один двухступенчатый.

Приведу пример кода на Python:

pythonCopy code
def count_ways_to_reach_n_steps(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    elif n == 2:
        return 2

    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    dp[2] = 2

    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

    return dp[n]

# Пример использования для n = 11
result = count_ways_to_reach_n_steps(11)
print(result)

Этот код выведет количество способов добраться до 11 ступенек.

Если вы предпочитаете другой язык программирования, принцип решения останется тем же, просто синтаксис и некоторые детали могут отличаться.