Question

Человек зашёл в подъезд и ему надо подняться на 20ю ступеньку. Найдите, сколько существует разных способов перехода на 20ю ступеньку, если человек за один шаг может перейти на следующую ступеньку или перепрыгнуть через неё.

Answer 1

Суть нужного алгоритма в следующем:
Заводим массив из 21 члена. Первый член будет соответствовать первой ступени. Приравняем его значение к единицы. Таким образом для каждой ступени будем считать количество вариантов на неё попадания. Для каждой ступени это будет суммой предыдущих двух членов. 
То есть a[0]=1, тогда:
a[1]=1 //на первую ступень можно попасть одним способом
a[2]=1+1=2 //на вторую ступень двумя - с нулевой и с первой
a[3]=2+1=3 //на третью ступень можно попасть либо с первой, либо со второй, на которую в свою очередь можно попасть двумя способами
a[4]=3+2=5
a[5]=5+3=8
и так далее

Заметим, что это последовательность Фибоначчи. Тогда решением будет 21-й член этой прогрессии. Можно посчитать вручную, либо через программу. Ответ 10 946.

Answer 2

Для решения данной задачи, нам необходимо найти количество различных способов перехода на 20-ю ступеньку, если человек может перейти на следующую ступеньку или перепрыгнуть через нее.

Решение:

Чтобы найти количество способов, мы можем использовать принцип динамического программирования. Пусть `dp[i]` будет количество способов достичь `i`-ю ступеньку. Тогда мы можем записать рекуррентное соотношение:

`dp[i] = dp[i-1] + dp[i-2]`

где `dp[i-1]` - количество способов достичь предыдущей ступеньки, а `dp[i-2]` - количество способов достичь ступеньки через одну.

Мы начинаем с базовых случаев `dp[0] = 1` и `dp[1] = 1`, так как для достижения первой и второй ступенек у нас есть только один способ.

Затем мы можем использовать цикл для вычисления `dp[i]` для всех ступенек от 2 до 20.

Реализация на Python:

```python def count_ways(n): dp = [0] * (n+1) dp[0] = 1 dp[1] = 1

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

return dp[n]

num_ways = count_ways(20) print(num_ways) ```

Ответ:

Существует 10946 различных способов перехода на 20-ю ступеньку, если человек может перейти на следующую ступеньку или перепрыгнуть через нее.