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

Суть нужного алгоритма в следующем:

Заводим массив из 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.