Задачи

Задача про лестницы

Вы поднимаетесь по лестнице. До вершины лестницы n ступенек. Каждый раз вы можете подняться либо на 1, либо на 2 ступеньки. Сколькими различными способами вы можете взобраться на вершину?

Пример 1:

# Входные данные: n = 2
# Выход: 2
# Пояснение: Есть два способа подняться на вершину.
#  - 1 ст. + 1 ст.
#  - 2 ст.

Пример 2:

  # Входные данные: n = 3
  # Выход: 3
  # Пояснение: Есть три способа подняться на вершину.
  #  - 1 ст. + 1 ст. + 1 ст.
  #  - 1 ст. + 2 ст.
  #  - 2 ст. + 1 ст.

Ограничения: 1 <= n <= 45

Решение

def countWays(n):
  if n==1:
    return 1
  elif n==2:
    return 2
  else:
    return countWays(n-1) + countWays(n-2)

steps = 6  
ways = countWays(steps)
print("Существует " + str (ways) + " различных способов подъема по лестнице из " + str (steps) + " ступеней при подъеме по одной или двум ступенькам за раз.")