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

• Название: Тема динамическое программирование
• Анкор: Шпраргалка егэ
• Дата: 02.03.2023
• Размер: 466.5 Kb.
• Имя файла: ege22.doc
• Тип: Задача; #965635
• страница: 1 из 6

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

22 (повышенный уровень, время –7 мин)

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

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

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

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

Р-06. Исполнитель Июнь15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14 и не содержит числа 25?

Решение:

1. 
   у нас в задании две особые точки – числа 14 (через которое должна проходить траектория) и 25 (а сюда она попасть НЕ должна)
   
2. 
   сначала, так же, как и в задачах, рассмотренных ниже, составляем рекуррентную формулу, по которой будем вычислять количество обозначить количество разных программ для получения числа N из начального числа 1:
   
3. 
   число N могло быть получено одной из двух операций:
   

• 
  увеличением на 1 числа N-1;
  
• 
  умножением на 2 числа N/2 (только для N, которые делятся на 2);
  

для нечётных чисел

для чётных чисел

4. 
   для начального числа 1 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; .
   
5. 
   составляем таблицу до первой особой точки – числа 14:
   

   N	2	3	4	5	6	7	8	9	10	11	12	13	14
   	1	1	2	2	3	3	5	5	7	7	10	10	13

6. 
   поскольку число 14 должно обязательно войти в траекторию, начинаем составлять вторую часть таблицы (до второй контрольной точки, 25) с этого числа заново, считая, что все ячейки для меньших чисел – нулевые
   

   N	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29
   	13	13	13	13	13	13	13	13	13	13	13	0

7. 
   поскольку траектория не может проходить через 25, для N = 25 принимаем K_N = 0 (в таблице эта ячейка выделена красным цветом)
   
8. 
   дальше заполняем оставшиеся ячейки второй части таблицы обычным способом (см. задачи ниже):
   

   N	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29
   	13	13	13	13	13	13	13	13	13	13	13	0	0	0	13	13

9. 
   Ответ: 13.