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

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



НазваниеТема : динамическое программирование
Дата конвертации24.06.2012
Размер200.41 Kb.
ТипРешение

© К. Поляков, 2009-2012

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


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

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

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

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

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

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

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

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

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


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

1. прибавь 1

2. умножь на 3

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

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

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

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

Решение (1 способ, составление таблицы):

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

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

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

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

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

  6. поэтому для получения gif" name="object6" align=absmiddle width=31 height=21> нужно сложить (количество программ с последней командой сложения) и (количество программ с последней командой умножения). В итоге получаем:

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

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

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

    N

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20



    1

    1

    2

    2

    2

    3

    3

    3

    5

    5

    5

    7

    7

    7

    9

    9

    9

    12

    12

    12

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

    N

    1

    3

    6

    9

    12

    15

    18

    21



    1

    2

    3

    5

    7

    9

    12

    15

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

  4. ответ – 12.

Решение (2 способ, подстановка – вычисления по формулам «с конца»):

  1. п. 1-6 выполняются так же, как и при первом способе; главная задача – получить рекуррентную формулу:

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

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

с начальными условиями

  1. начинаем с заданного конечного числа 20; применяем первую формулу (), пока не дойдем до числа, делящегося на 3 (это 18):



  1. далее применяем вторую формулу ():



  1. применяем первую формулу для 17:



  1. применяем вторую формулу для обоих слагаемых:



где учтено, что

  1. с помощью первой формулы переходим в правой части к числам, делящимся на 3:



а затем применяем вторую формулу для каждого слагаемого



  1. снова используем первую формулу



а затем – вторую:



  1. и еще раз



  1. ответ – 12.

Решение (3 способ, О.В. Шецова, лицей № 6, г. Дубна):

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

  2. очевидно, что число 1 может быть получено с помощью одной единственной (пустой) программы:

    Число

    Как можно получить?

    Количество программ

    1




    1

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

    Число

    Как можно получить?

    Количество программ

    1




    1

    2

    +1

    = 1

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

Число

Как можно получить?

Количество программ

1




1

2

+1

1

3

+1 *3

1 + 1 = 2




  1. числа 4 и 5 не делятся на 3, поэтому их можно получить только с помощью команды +1, а число 6 может быть получено двумя командами:

    Число

    Как можно получить?

    Количество программ

    1




    1

    2

    +1

    1

    3

    +1 *3

    1 + 1 = 2

    4

    +1

    2

    5

    +1

    2

    6

    +1 *3

    2 + 1 = 3

  2. следующая группа – 7, 8 (не делятся на 3) и 9 (делится на 3):

    Число

    Как можно получить?

    Количество программ

    1




    1

    2

    +1

    1

    3

    +1 *3

    1 + 1 = 2

    4

    +1

    2

    5

    +1

    2

    6

    +1 *3

    2 + 1 = 3

    7

    +1

    3

    8

    +1

    3

    9

    +1 *3

    3 + 2 = 5

  3. далее – 10, 11 и 12:

    Число

    Как можно получить?

    Количество программ

    1




    1

    2

    +1

    1

    3

    +1 *3

    1 + 1 = 2

    4

    +1

    2

    5

    +1

    2

    6

    +1 *3

    2 + 1 = 3

    7

    +1

    3

    8

    +1

    3

    9

    +1 *3

    3 + 2 = 5

    10

    +1

    5

    11

    +1

    5

    12

    +1 *3

    5 + 2 = 7

  4. и так далее, вот полностью заполненная таблица (до конечного числа 20):

Число

Как можно получить?

Количество программ

1




1

2

+1

1

3

+1 *3

1 + 1 = 2

4

+1

2

5

+1

2

6

+1 *3

2 + 1 = 3

7

+1

3

8

+1

3

9

+1 *3

3 + 2 = 5

10

+1

5

11

+1

5

12

+1 *3

5 + 2 = 7

13

+1

7

14

+1

7

15

+1 *3

7 + 2 = 9

16

+1

9

17

+1

9

18

+1 *3

9 + 3 = 12

19

+1

12

20

+1

12




  1. ответ – количество программ, с помощью которых можно получить число 20 из 1, – считываем из последней ячейки третьего столбца

  2. ответ – 12.

Решение (4 способ, М.В. Кузнецова и её ученики, г. Новокузнецк):

  1. пусть – искомое конечное число, количества программ получения числа

  2. тогда для построения рекуррентной формулы определения , нужно знать 2 факта:

  1. какой может быть последняя команда и сколько есть видов этого последнего действия?

  2. для каждого «последнего» действия нужно знать число программ получения предыдущего числа, сумма этих количеств и есть искомое значение число программ получения числа .

Например, общее количество программ получения числа 6 с помощью Утроителя равно , т.к. есть ДВА способа завершения программ получения этого значения: 6=5+1 и 6=2∙3 .

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

  2. составим рекуррентную формулу для определения числа программ получения числа :

при имеем

если не кратно 3:

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

  1. с помощью это формулы заполняем таблицу следующим образом:

– в первом столбце записываем все натуральные числа от 1 до заданного ;

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

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

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

N

N-1

N/3

K(N)

1прямая со стрелкой 33






1

2прямая со стрелкой 30полилиния 31

1




1

3

2

1

1+1= 2

4

3




2

5полилиния 32

4




2

6

5

2

2+1=3

7

6




3

8

7




3

9

8

3

3 + 2=5

10

9




5

11

10




5

12

11

4

5 + 2 = 7

13

12




7

14

13




7

15

14

5

7 + 2 = 9

16

15




9

17

16




9

18

17

6

9+3 = 12

19

18




12

20

19




12

  1. ответ – 12.

Решение (5 способ, А. Сидоров):

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

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

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



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

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



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



  1. находить число программ для следующих чисел нам уже не понадобится, потому что при умножении на 3 они дают числа, большие, чем заданное конечное число 20

  2. запишем полученные результаты в самой нижней строке для всех множителей от 1 до 6:



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

3 + 2 + 2 + 2 + 1 + 1 + 1 = 12

  1. ответ – 12.




Возможные проблемы:

    • неверно определенные начальные условия

    • неверно выведенная рекуррентная формула

    • ошибки при заполнении таблицы (невнимательность)

    • второй способ (подстановка), как правило, приводит к бОльшему количеству вычислений; конечно, можно отдельно выписывать все полученные ранее значения , но тогда мы фактически придем к табличному методу




^ За что снимают баллы:

    • за то, что нет обоснования полученного результата (хотя получен правильный ответ)

    • за то, что нет строгого доказательства того, что найдены все возможные программы; например, снимут 1 балл, если просто перечислить все возможные программы или построить полное дерево возможных программ, но без доказательства

    • за арифметические ошибки
^

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


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

1. прибавь 1

2. умножь на 2

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

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

1. прибавь 1

2. умножь на 4

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

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

1. прибавь 1

2. умножь на 2

3. умножь на 3

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

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

1. прибавь 1

2. умножь на 2

3. умножь на 4

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

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

1. прибавь 1

2. умножь на 3

3. умножь на 4

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

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

1. прибавь 1

2. прибавь 2

3. умножь на 3

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

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

1. прибавь 1

2. прибавь 3

3. умножь на 2

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

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

1. прибавь 1

2. прибавь 3

3. умножь на 3

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

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

1. прибавь 1

2. прибавь 3

3. умножь на 4

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

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

1. прибавь 1

2. прибавь 2

3. умножь на 4

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

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

1. прибавь 1

2. умножь на 4

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

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

1. прибавь 2

2. умножь на 2

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

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

1. прибавь 1

2. умножь на 3

Сколько есть программ, которые число 5 преобразуют в число 49? Ответ обоснуйте.

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

1. прибавь 3

2. умножь на 3

Сколько есть программ, которые число 5 преобразуют в число 27? Ответ обоснуйте.

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

1. прибавь 1

2. прибавь 3

3. умножь на 2

Сколько есть программ, которые число 3 преобразуют в число 15? Ответ обоснуйте.

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

1. прибавь 1

2. умножь на 2

3. возведи в квадрат

Сколько есть программ, которые число 2 преобразуют в число 38? Ответ обоснуйте.

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

1. прибавь 1

2. прибавь 3

3. возведи в квадрат

Сколько есть программ, которые число 2 преобразуют в число 19? Ответ обоснуйте.

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

1. прибавь 1

2. умножь на 2

3. возведи в квадрат

Сколько есть программ, которые число 2 преобразуют в число 27? Ответ обоснуйте.


1 Источники заданий:

  1. Демонстрационный вариант ЕГЭ 2012 гг.

  2. Проверочные работы МИОО.




Похожие:

Тема : динамическое программирование iconДокументы
1. /лекции динамическое программирование+ио гольдштейн/Глава 1.doc
2. /лекции...

Тема : динамическое программирование iconДокументы
...
Тема : динамическое программирование iconНейро-Динамическое Программирование Автономных Агентов Как обучаемые агенты решают задачи оптимизации
Формально сводится к определению оптимального варианта решения в текущих условиях
Тема : динамическое программирование iconУроки №5-6 тема: " Программирование ветвящихся алгоритмов. Оператор выбора ". Оператор
Оператор служит для выбора одного из помеченных вариантов действия (операторов), в зависимости от значения "параметра". Оператор...
Тема : динамическое программирование iconУроки №3-4 тема: " Программирование линейных алгоритмов. Стандартные математические функции Паскаля. Модуль crt". Основные операции в Паскале
В тп 0 все операции делятся на: математические, логические, операции с символами и строкам, операции над множествами, операции отношения,...
Тема : динамическое программирование iconДокументы
1. /Лаб раб 10 Программирование в MS Access часть 3.doc
2. /Лаб...

Тема : динамическое программирование iconДокументы
1. /Информатика/Информационный фонд/Источники по информатике.DOC
2. /Информатика/Информационный...

Тема : динамическое программирование iconЛинейное программирование. Методы решения одношаговых задач оптимального управления
Методы решения таких задач получили название математического программирования. Простейшим случаем математического программирования...
Тема : динамическое программирование iconСценарный подход и субъектно-ориентированное программирование развития народов севера (к постановке проблемы)*
Сценарный подход и субъектно-ориентированное программирование развития народов севера
Тема : динамическое программирование iconДокументы
1. /Авторский коллектив.doc
2. /Введение.doc
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов