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

• Название: Динамическое программирование
• Дата: 18.12.2021
• Размер: 0.7 Mb.
• Имя файла: ege23.doc
• Тип: Решение; #307871
• страница: 4 из 11

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

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

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.
    

Решение (программа на Python):

1. 
   полная программа:
   

TARGET = 4

def nProg( x ):

if x == TARGET: # если цель достигнута, то

return 1 # завершить функцию, посчитав программу

if x < TARGET: # если перелет, то

return 0 # завершить функцию, не считая цепочку

# x > TARGET - продолжаем строить дерево:

n = nProg( x - 1 )

if x % 2 == 0:

n += nProg( x // 2 )

return n

START = 24

print( nProg( START//2-1 ) + nProg( START-1-1 ) )

2. 
   Ответ: 18.
   

Решение (ещё один варианты программы на Python, Б.С. Михлин):

1. 
   полная программа:
   

def nProg( x, t ): # x - текущее число, t - цель (target)

if x == t:

return 1

if x > t:

return 0

# x < t - строим дерево:

return nProg( x + 1, t ) + nProg( x * 2, t )

# Т.к. предпоследняя команда +1, то 22 +1 +1 = 24, (11 +1) *2 = 24

print( nProg( 4, 22 ) + nProg( 4, 11 ) )

2. 
   Ответ: 18.