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

А не много ли в итоге способов получается?)

Answer 3

Можешь попробовать, когда из школы будешь возвращаться.

Answer 4

))