Облако знаний. Динамическое программирование в электронных таблицах. Информатика. 9 класс

Динамическое программирование в электронных таблицах

Основные отличия динамического программирования от рекурсии:
1. Запоминание результатов. Динамическое программирование сохраняет результаты уже решённых подзадач, что предотвращает повторные вычисления.
2. Эффективность. Динамическое программирование обычно более эффективно по времени и памяти, так как избегает избыточных вычислений.
3. Структура решения. Динамическое программирование часто использует итеративный подход или таблицы для хранения промежуточных результатов.
Пример. Алгоритм вычисления функции G (n) задан следующими соотношениями:
G (n) = 2n при n ≤ 3
G (n) = G (n – 2) + 3 · G (n/2), если n ＞ 3 и чётно,
G (n) = G (n – 1) + G (n – 2), если n ＞ 3 и нечётно.
Чему равно значение функции G (9) + G (10)?
Решение.
1. Заполним значения диапазон ячеек A1:A10 аргументами n от 1 до 10.
2. Затем введём первые три значения G (n) по формуле (для ячейки В1): =А1*2. Автозаполнением скопируем формулу на весь диапазон B2:B3.
3. Используя функцию ЕСЛИ, введём формулу для расчёта значений для чётных и нечётных значений n (для ячейки В4): =ЕСЛИ(ОСТАТ(A4;2)=0;B2+3*СМЕЩ(A4;-A4/2;1);B2+B3). Автозаполнением скопируем формулу на весь диапазон B4:B10.
4. В ячейку B11 введём формулу для расчёта окончательного результата: =B9+B10. Ответ задания 286.

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