Что нужно знать: динамическое программирование – это способ решения сложных задач путем сведения их к более простым задачам того же типа динамическое. - презентация

1

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

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

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

5 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

6 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

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

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

9 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

10 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

11 так как К 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

29 Поэтому достаточно по индукции вычислить значения 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).

30 Имеем: 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

31 Пример решения экзаменуемого: 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)

32 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)

33 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

34 Отсюда 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