Человек зашёл в подъезд и ему надо подняться ** 20ю ступеньку. Найдите, сколько...

0 голосов
94 просмотров

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


Информатика (26 баллов)
оставил комментарий Начинающий (332 баллов)

тебе код написать или сказать ответ?

оставил комментарий (26 баллов)

Ответ

оставил комментарий Начинающий (332 баллов)

без решения?

оставил комментарий (26 баллов)

Если можно, то с решением плиз)

оставил комментарий (10 баллов)

а мне не можете скинуть решение пожалуйста

Дан 1 ответ
0 голосов
Начинающий (332 баллов)

Суть нужного алгоритма в следующем:
Заводим массив из 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.

оставил комментарий (26 баллов)

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

оставил комментарий Начинающий (332 баллов)

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

оставил комментарий (26 баллов)

))

...