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

Человек зашел в подъезд и ему надо подняться на двадцатую ступеньку. Найдите, сколько существует разных способов перехода на 20-ю ступеньку, если человек за один шаг может перейти на следующую ступеньку или перепрыгнуть через неё. В ответе укажите только число
Гость
Ответ(ы) на вопрос:
Гость
Классическая задача на динамическое программирование. Применим этот принцип: Количество вариантов как попасть в какое-то состояние равно сумме количеств вариантов как попасть в предыдущие состояния. Например вариантов попасть на первую ступеньку  -1, на вторую - 2 и т.д. var i,n : Integer;     a : array [1..20] of integer; begin   n:=20;   a[1]:=1; a[2]:=2;   for i:=3 to n do     a[I] := a[i-1] + a[i-2];   writeln(a[n]); end. Ответ: 10946 способов.
Не нашли ответ?
Ответить на вопрос
Похожие вопросы