Динамическое программирование

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. 
   поэтому для получения нужно сложить (количество программ с последней командой сложения) и (количество программ с последней командой умножения). В итоге получаем:
   

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

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

7. 
   остается заполнить таблицу для всех значений от 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

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

   N	1	3	6	9	12	15	18	21
   	1	2	3	5	7	9	12	15

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

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

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

1. прибавь 1

2. умножь на 2

3. умножь на 3

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

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

1. прибавь 1

2. умножь на 2

3. умножь на 4

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

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

1. прибавь 1

2. умножь на 3

3. умножь на 4

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

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

1. прибавь 1

2. прибавь 2

3. умножь на 3

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

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

1. прибавь 1

2. прибавь 3

3. умножь на 2

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

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

1. прибавь 1

2. прибавь 3

3. умножь на 3

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

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

1. прибавь 1

2. прибавь 3

3. умножь на 4

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

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

1. прибавь 1

2. прибавь 2

3. умножь на 4

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

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

1. прибавь 1

2. умножь на 4

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

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

1. прибавь 2

2. умножь на 2

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