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

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

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

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

#include <iostream> 
using namespace std; 
unsigned long int Fibonacci (int n) { 
  if (n == 1 || n == 2) return 1; 
  int x = 1, y = 1, c; 
  for (int i = 2; i < n; ++i) { 
    c = x + y;  // Вычисляем текущий член как
    сумму двух предыдущих 
    x = y;  // Сдвигаем значения для следующей итерации 
    y = c; }  // Теперь y хранит последнее
    вычисленное значение
  return y; } 
int main () { 
  int k; cin >> k;
  cout << Fibonacci (k); }

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