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

Пример задания: У исполнителя Утроитель две команды, которым присвоены номера: 1. прибавь 1 2. умножь на 3 Первая из них увеличивает число на экране на 1, вторая – утраивает его. Программа для Утроителя – это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 20? число 1 преобразуют в число 20? Ответ обоснуйте.

Решение (1 способ, составление таблицы): 1) заметим, что при выполнении любой из команд число увеличивается (не может уменьшаться) 2) число 1 у нас уже есть, значит, его можно получить с помощью пустой программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 1. Значит, R(1) =1. Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. 2) число 1 у нас уже есть, значит, его можно получить с помощью пустой программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 1. Значит, R(1) =1. Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя.

3) для числа 2, меньшего, чем 3, существует только одна программа, состоящая только из команды сложения; если через K N обозначить количество разных программ для получения числа N из 1, то K 2 =K 1 =1. теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую K N с предыдущими элементами последовательности K 1, K 2 …, K N, то есть с решениями таких же задач для меньших N 4) теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую K N с предыдущими элементами последовательности K 1, K 2 …, K N, то есть с решениями таких же задач для меньших N

5) если число N не делится на 3, то оно могло быть получено только последней операцией сложения, поэтому K N =K N -1 6) если N делится на 3, то последней командой может быть как сложение, так и умножение 7) поэтому, для получения К N нужно сложить K N-1 (количество программ с последней командой сложения) и K N/3 (количество программ с последней командой умножения). В итоге получаем: если N не делится на 3: К N = K N-1 если N делится на 3: К N = K N-1 + K N/3

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

Решение (2 способ, подстановка – вычисления по формулам « с конца »): 1)начало, как и в 1 способе. Надо получить рекуррентную формулу : если N не делится на 3: К N = K N-1 если N делится на 3: К N = K N-1 + K N/3 с начальными условиями К 1 =К 2 =1

2) начинаем с заданного конечного числа 20; применяем первую формулу (К N = K N-1 ) пока не дойдем до числа, делящегося на 3 (это 18): К 20 =К 19 =К 18 3) далее применяем вторую формулу ( К N = K N-1 + K N/3 ) К 20 =К 18 =К 17 +К 6 4) применяем первую формулу для 17: К 17 =К 16 =К 15 К 20 =К 15 +К 6

5) Применим вторую формулу для обоих слагаемых: К 20 =(К 14 +К 5 )+(К 5 +К 2 )=К 14 +2К 5 +1 здесь учтено, что К 2 =1 6) Рассмотрим каждое слагаемое и дойдем до чисел, делящихся на 3: К 14 =К 13 =К 12 а К 12 =К 11 +К 4 К 5 =К 4 =К 3 а К 3 =К 2 +К 1 К 5 =К 4 =К 3 а К 3 =К 2 +К 1следовательно: К 20 =К 12 +2К 3 +1=(К 11 +К 4 )+2(К 2 +К 1 )+1

так как К 2 =К 1 =1, мы имеем К 20 =К 11 +К 4 +2(1+1)+1=К 11 +К ) снова используем первую формулу К 20 =К 9 +К 3 +5 а затем – вторую: К 20 =(К 8 +К 3 )+(К 2 +К 1 )+5= =К 8 +2(К 2 +К 1 )+5=К ) и еще раз используем вторую формулу: К 20 =К 6 +9=К 5 +К 2 +9=К 5 +10=К 3 +10= =2+10=12 Ответ – 12.

Решение (3 способ). 1) будем составлять таблицу из трех столбцов: в первом записывается получаемое число от 1 до 20, во втором – какой последней командой может быть получено это число, а в третьем вычисляем количество различных программ для получения этого числа из 1 2) очевидно, что число 1 может быть получено с помощью одной единственной (пустой) программы: Число Как можно получить? Количество программ 11

Число Как можно получить? Количество программ =1 3) число 2 не делится на 3, поэтому его можно получить только командой сложения (+1), значит, количество программ для 2 совпадает с количеством программ для 1:

Число Как можно получить? Количество программ *31+1=2 4) число 3 делится на 3, поэтому его можно получить с помощью двух команд: +1 (из 2) и *3 (из 1):

Число Как можно получить? Количество программ *31+1= * =3 5) числа 4 и 5 не делятся на 3, поэтому их можно получить только с помощью команды +1, а число 6 может быть получено двумя командами :

Число Как можно получить? Количество программ * = * = * = 5 6) следующая группа – 7, 8 (не делятся на 3) и 9 (делится на 3):

ЧислоКак можно получить?Количество программ * = * = * = * = * = * =

7) ответ – количество программ, с помощью которых можно получить число 20 из 1, – считываем из последней ячейки третьего столбца 8)ответ – 12. Решение (4 способ) 1) основная идея – число программ, преобразующих начальное число 1 в конечное 20 с помощью заданных в условии команд, равно числу программ, преобразующих конечное число 20 в начальное 1 с помощью обратных команд: «вычти 1» и «раздели на 3»

2) будем строить «обратное дерево» – дерево всех способов преобразования конечного числа в начальное; это лучше (в сравнении с построением «прямого» дерева, от начального числа к конечному), потому что операция умножения необратима – каждое число можно умножить на 3, но не каждое можно разделить на 3; из-за этого сразу отбрасываются тупиковые ветви, не дающие новых решений

3) рисуем сокращенное дерево, в котором черные стрелки показывают действие первой команды («прибавь 1»), а красные – действие второй команды («умножь на 3»); красные стрелки подходят только к тем числам, которые делятся на 3 :

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

5) очевидно, что для получения 1 существует одна (пустая) программа; тогда для числа 2 тоже получается одна программа, а для числа 3 – две программы: (2) (1) (1)

6) далее, для чисел 4 и 5 получаем 2 программы (после числа 3 нет «разветвлений» – подходящих красных стрелок), а для числа 6 – 3 программы, так как «подошло» еще одно разветвление (6 можно получить умножением 2 на 3), а для числа 2 мы уже подсчитали количество программ – оно равно 1: (3) (2) (1) (1)

7) находить число программ для следующих чисел нам уже не понадобится, потому что при умножении на 3 они дают числа, большие, чем заданное конечное число 20 8) запишем полученные результаты в самой нижней строке для всех множителей от 1 до 6: (3) (2) (1) (3) (2) (2) (2) (1) (1)

9) теперь остается сложить все числа в скобках в нижнем ряду (количество программ с командами умножения) и добавить 1 (одна программа, состоящая только из команд сложения): = 12 10) ответ – 12.

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

Задание С 3. Вариант 1. Текст задачи : У исполнителя Увеличитель две команды, которым присвоены номера : 1. прибавь 1, 2. умножь на 4. Первая из них увеличивает число на экране на 1, вторая – умножает его на 4. Программа для Увеличителя – это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 32? Ответ обоснуйте.

Обозначим R(n) – количество программ, которые преобразуют число 1 в число n. Обозначим t(n) наибольшее кратное четырем, не превосходящее n. Обе команды исполнителя увеличивают исходное число, поэтому общее количество команд в программе не может превосходить 32. Верны следующие соотношения: 1. Если n не делится на 4, то тогда R(n) = R(t(n)), так как существует единственный способ получения n из t(n) – прибавлением единиц.

Поэтому достаточно по индукции вычислить значения R(n) для всех чисел, кратных четырем и не превосходящих Пусть n делится на 4. Тогда R(n) = R(n/4)+R(n-1)= R(n/4)+R(n-4) (если n>4). При n=4 R(n) = 2 (два способа: прибавлением трех единиц или однократным умножением на 4).

Имеем: R(1)= R(2)= R(3)= 1 R(4) = 2 = R(5)=R(6) =R(7) R(8) = R(2)+R(7) =1+2 = 3 = R(9)=R(10) =R(11) R(12) = R(3)+R(11) =1+3 =4 = R(13)=R(14) =R(15) R(16) = R(4)+R(15) = 2+4 = 6 = R(17)=R(18) =R(19) R(20) = R(5)+R(19) =2+6 =8 = R(21)=R(22) =R(23) R(24) = R(6)+R(23) = 2+8 = 10 = R(25)=R(26) =R(27) R(28) = R(7)+R(27) = 2+10 = 12 = R(29)=R(30) =R(31) R(32) = R(8)+R(31) = = 15 Ответ: 15

Пример решения экзаменуемого: 15 программ Обоснуем это: Обозначим Rn – количество программ, которые преобразуют число 1 в число n. Найдем R32 R32 = R8+R31, поскольку 32 можно получить за один шаг только из 8 (*4) или 31 (+1) R31 = R28, поскольку 31 из 28 можно получить только одним способом (+1 и +1 и +1) R28 = R7+R27, поскольку 28 можно получить за один шаг только из 7 (*4) или 27 (+1) R27 = R24, поскольку 27 из 24 можно получить только одним способом (+1 и +1 и +1)

R24 = R6+R23, поскольку 24 можно получить за один шаг только из 6 (*4) или 23 (+1) R23 = R20, поскольку 23 из 20 можно получить только одним способом (+1 и +1 и +1) R20 = R5+R19, поскольку 20 можно получить за один шаг только из 5(*4) или 19 (+1) R19 = R16, поскольку 19 из 16 можно получить только одним способом (+1 и +1 и +1) R16 = R4+R15, поскольку 16 можно получить за один шаг только из 4(*4) или 15 (+1) R15 = R12 поскольку 15 из 12 можно получить только одним способом (+1 и +1 и +1) R12 = R3+R11, поскольку 12 можно получить за один шаг только из 3(*4) или 11 (+1)

R11= R8, поскольку 11 из 8 можно получить только одним способом (+1 и +1 и +1) R8 = R2+R7, поскольку 8 можно получить за один шаг только из 2(*4) или 7 (+1) R7= R6 = R5= R4, поскольку 7 из 4 можно получить только одним способом (+1 и +1 и +1) R4= 2, поскольку 4 можно получить из 1 только двумя способами 1*4 и R3=1, поскольку 3 можно получить из 1 только одним способом R2=1, поскольку 2 можно получить из 1 только одним способом 1 +1

Отсюда R7= R6 = R5= R4 = 2 R8 = R2+R7=3 R12 = R3+R8=4 R16 = R4+R15=6 R20 = R5+R19=8 R24 = R6+R23=10 R28 = R7+R27=12 R32 = R8+R31=15