ЕГЭ по информатике: динамическое программирование

Курс построен на базе статьи К.Ю. Полякова. Динамическое программирование в задачах обработки последовательностей ЕГЭ по информатике. // Информатика в школе, № 5, 2020 с. 55–63.

Задание 27 в текущей версии ЕГЭ по информатике — это традиционная «серая лошадка» — неизвестная заранее задача, предусматривающая написание учащимся программы длиной в несколько десятков операторов. Задания 27 в ЕГЭ последних лет, как правило, связаны с обработкой последовательности чисел, причем для полного решения задачи (на 4 балла) эти данные нельзя сохранять в массиве или в другой структуре данных. Требуется найти некоторую характеристику входной последовательности, например, пару значений с максимальной суммой или количество пар с суммой, кратной 13. Алгоритмы решения задач этого типа чаще всего основаны на использовании формул комбинаторики или применении динамического программирования. В настоящем курсе мы подробно рассмотрим второй из этих подходов на примере решения серии типовых задач возрастающей сложности.