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

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

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

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

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

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

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

выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Решение (вариант 1):

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

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

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

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

5. 
   поскольку траектория должна проходить через число 10, сначала выясняем, сколькими способами можно получить 10 из 1, а затем будем считать, сколько есть способов получить 21 из 10
   
6. 
   заполняем таблицу от 1 до 10 по полученным формулам:
   

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

7. 
   второй этап – определяем таким же образом (и по таким же формулам!), сколько есть способов получить конечное число 21 из 10, только левую часть таблицы (от 1 до 10) мы уже не рассматриваем:
   

   N	10	11	12	13	14	15	16	17	18	19	20	21
   	14	14	14	14	14	14	14	14	14	14	28	28

8. 
   Ответ: 28.
   

Решение (вариант 2, А.Н. Носкин):

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

   N	10	11	12	13	14	15	16	17	18	19	20	21
   	1	1	1	1	1	1	1	1	1	1	2	2

4. 
   результат – 14  2 = 28
   
5. 
   Ответ: 28.
   

Решение (программа на Python, Б.С. Михлин):

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

# Функция подсчета количества цепочек команд (программ).

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

def nProg( x, t ):

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

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

if x > t: # если перелет, то

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

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

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

print( nProg( 1, 10 ) * nProg( 10, 21 ) )

4. 
   Ответ: 28.