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

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

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

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

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

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

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

Решение:

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

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

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

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

4. 
   для начального числа 2 количество программ равно 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.
   

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

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

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

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

def nProg( x, t ):

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

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

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

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

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

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

print( nProg( 2, 14 ) * nProg( 14, 29 ) )

4. 
   Ответ: 13.
   

Решение (2 таблицы, Python, А.Н. Носкин):

1. 
   идея: смотри разбор Р-09
   

a =[0]*15 # массив от 0 - 14

# заполняем от 2 до 14

a[2] = 1

for i in range(3,14+1):

if i%2==0 and i>=4:

a[i] = a[i-1] + a[i//2]

else: a[i] = a[i-1]
b =[0]*30 # массив от 0 - 29

# заполняем от 14 до 29

b[14] = 1

for i in range(15,29+1):

if i==25: b[25] = 0

elif i%2==0 and i>=28:

b[i] = b[i-1] + b[i//2]

else: b[i] = b[i-1]
print(a[14]*b[29])

# или так: print(a[-1]*b[-1])

2. 
   Ответ: 13.
   

Решение (динамическое программирование, Python, А.Н. Носкин):

1. 
   использование одной таблицы
   

a =[0]*30 # массив от 0 - 29

# заполняем от 2 до 14

a[2] = 1

for i in range(3,14+1):

if i % 2 == 0:

a[i] = a[i-1] + a[i//2]

else: a[i] = a[i-1]
# заполняем с 15 до 29

for i in range(15,29+1):

if i==25: a[25] = 0

elif i%2 == 0 and i>=28:

a[i] = a[i-1] + a[i//2]

else: a[i] = a[i-1]

print( a[29] )

2. 
   Ответ: 13.