Облако знаний. Динамическое программирование как метод решения задач с сохранением промежуточных результатов (Паскаль). Информатика. 11 класс

Динамическое программирование как метод решения задач с сохранением промежуточных результатов (Паскаль)

Динамическое программирование – это метод решения сложных задач путём их разбиения на более простые подзадачи, при этом результаты решения подзадач сохраняются и повторно используются для избегания избыточных вычислений.
Числа Фибоначчи – классический пример, где динамическое программирование применяется наиболее естественно. Математически последовательность Фибоначчи определяется следующим образом:
- F (1) = 1,
- F (2) = 1,
- F (n) = F (n – 1) + F (n – 2) для n ＞ 2.
  Таким образом, ряд начинается как: 1, 1, 2, 3, 5, 8, 13, 21, ... где каждое последующее число равно сумме двух предыдущих.

Программная реализация демонстрирует этот принцип на практике:

function Fibonacci (n: integer): QWord;
var x, y, c: QWord; i: integer;
begin
  if (n = 1) or (n = 2) then Fibonacci := 1;
  x := 1; y := 1;
  for i := 2 to n - 1 do
  begin
    c := x + y; { Вычисляем текущий член как сумму двух предыдущих }
    x := y; { Сдвигаем значения для следующей итерации }
    y := c; { Теперь y хранит последнее вычисленное значение }
  end;
  Fibonacci := y;
end;
var k: integer;
Begin
  readln (k);
  write (Fibonacci (k));
End.

Было полезно?