Решение 50 типовых задач по программированию на языке Pascal Дата размещения сборника в сети

n-
го членов. Для этого можно создать некую вспомогательную переменную fib, в которую поме-
стить результат сложения fib0 и fib1, после чего в fib0 у нас будет значение (n – 2)-го члена, в fib1 
– (n – 1)-
го, а в fib – n-го. Теперь нужно только скопировать значение fib1 в fib0 и fib в fib1, после 
чего значение переменной fib на этом шаге уже не имеет значения. С учетом того, что мы уже по-
считали необходимое количество повторений для получения необходимого результата, цикл будет 
выглядеть так: 
for i := 1 to n - 1 do begin 
fib := fib1 + fib0; 
fib0 := fib1; 
fib1 := fib 
end; 
Такой метод решения общей задачи, основанный на использовании в ней решений задач с 
меньшей размерностью исходных данных (в данном случае под размерностью понимается величина 
n
), называется динамическим программированием. 
Если говорить конкретнее, то мы применили метод восходящего динамического программиро-
вания, основывающийся на решении задач сначала минимальной размерности с постепенным полу-
чением решений более обширных задач. Этот метод наиболее оптимален в плане реализации, быст-
родействия и используемой памяти. 
Однако далеко не для всех задач, решаемых с помощью динамического программирования, 
можно выяснить, решения каких подзадач потребуются для решения данной. Для этого существует 
метод нисходящего динамического программирования, с которым мы познакомимся позже. 
Другой пример нисходящего динамического программирования – вычисление факториала (
за-
дача 28). Чтобы вычислить n!, необходим вычисленный (n – 1)! и т. д. 
Итак, вернемся к текущей задаче. Ранее было сказано, что по исчерпании n – 1 шагов цикла в 
переменной fib1, которая пойдет на вывод в программе, будет храниться значение F