C3 (высокий уровень, время – 30 мин)

C3 (высокий уровень, время – 30 мин)

Тема: динамическое программирование.

Что нужно знать:

· динамическое программирование – это способ решения сложных задач путем сведения их к более простым задачам того же типа

· с помощью динамического программирования решаются задачи, которые требуют полного перебор вариантов:

o «подсчитайте количество вариантов…»

o «как оптимально распределить…»

o «найдите оптимальный маршрут…»

· динамическое программирование позволяет ускорить выполнение программы за счет использования дополнительной памяти; полный перебор не требуется, поскольку запоминаются решения всех задач с меньшими значениями параметров

Пример задания:

У исполнителя Утроитель две команды, которым присвоены номера:

1. прибавь 1

2. умножь на 3

Первая из них увеличивает число на экране на 1, вторая – утраивает его.

Программа для Утроителя – это последовательность команд.

Сколько есть программ, которые число 1 преобразуют в число 20?

Ответ обоснуйте.

Решение:

1) заметим, что при выполнении любой из команд число увеличивается (не может уменьшаться)

2) начнем с простых случаев, с которых будем начинать вычисления: для чисел 1 и 2, меньших, чем 3, существует только одна программа, состоящая только из команд сложения; если через обозначить количество разных программ для получения числа N из 1, то .

3) теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую с предыдущими элементами последовательности , то есть с решениями таких же задач для меньших N

4) если число N не делится на 3, то оно могло быть получено только последней операцией сложения, поэтому

5) если N делится на 3, то последней командой может быть как сложение, так и умножение

6) поэтому для получения нужно сложить (количество программ с последней командой сложения) и (количество программ с последней командой умножения). В итоге получаем:

если N не делится на 3:

если N делится на 3:

7) остается заполнить таблицу для всех значений от 1 до N:

8) Заметим, что количество вариантов меняется только в тех столбцах, где N делится на 3, поэтому из всей таблицы можно оставить только эти столбцы:

N

9) заданное число 20 попадает в последний интервал (от 18 до 21), поэтому …

10) ответ – 12.

Возможные проблемы: · неверно определенные начальные условия · неверно выведенная рекуррентная формула · ошибки при заполнении таблицы (невнимательность)

За что снимают баллы: · за то, что нет обоснования полученного результата (хотя получен правильный ответ) · за то, что нет строгого доказательства того, что найдены все возможные программы; например, снимут 1 балл, если просто перечислить все возможные программы или построить полное дерево возможных программ, но без доказательства · за арифметические ошибки

Задачи для тренировки[1]:

1) У исполнителя Калькулятор две команды, которым присвоены номера:

12 Следующая ⇒