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

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

Ещё пример задания:

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

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

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

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

Решение:

1. 
   итак, мы знаем предпоследнюю команду – 1, при этом последняя команда может быть любая – 1 или 2
   
2. 
   выходит, что нужно получить количество всех программ вида «*11» и «*12», где звёздочка обозначает любые команды
   
3. 
   если программа заканчивается на «11», то до выполнения цепочки «11» у нас было число
   

24 – 1 – 1 = 22; поэтому нужно найти число программ для преобразования 4 в 22

4. 
   для начального числа 1 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; если через обозначить количество разных программ для получения числа N из начального числа 1, то .
   
5. 
   теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую с предыдущими элементами последовательности , то есть с решениями таких же задач для меньших N
   
6. 
   число N могло быть получено одной из двух операций:
   

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

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

для чётных чисел, таких, что N/2  4

7. 
   составляем таблицу:
   

   N	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
   	1	1	1	1	2	2	3	3	4	4	5	5	7	7	9	9	12	12	15

8. 
   теперь рассматриваем случай, когда программа заканчивается на «12», это значит, что до выполнения цепочки «12» у нас было число (24/ 2) – 1 = 11; поэтому нужно найти число программ для преобразования 4 в 11, берём его из таблицы: 3
   
9. 
   ответ к задаче – сумма двух значений, выделенных жёлтым маркером: 15 + 3 = 18, поскольку мы рассмотрели все варианты программ, в которых предпоследняя команда – 1
   
10. 
    Ответ: 18.