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

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

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

Р-04. Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя

три команды, которым присвоены номера:

1. прибавь 1

2. прибавь 2

3. прибавь следующее

Первая из них увеличивает число на экране на 1, вторая увеличивает это число на 2, а третья прибавляет к числу на экране число, большее на 1 (к числу 3 прибавляется 4, к числу 9 прибавляется 10 и т. д.). Программа для исполнителя Калькулятор– это последовательность команд. Сколько есть программ, которые число 2 преобразуют в число 10?

Решение (1 способ, составление таблицы):

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

• 
  увеличением на 1 числа N-1;
  
• 
  увеличением на 2 числа N-2;
  
• 
  из некоторого числа X увеличением на X+1 (следующее число), так что N = X + X + 1, откуда X = (N – 1) / 2; так могут быть получены только нечетные числа;
  

поэтому

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

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

5. 
   остается по этой формуле заполнить таблицу для всех значений от 2 до 10:
   

   N	2	3	4	5	6	7	8	9	10
   	1	1	2	4	6	11	17	30	47

6. 
   Ответ:– 47.
   

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

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

t = 10 # цель (target)

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

# x - текущее число.

def nProg( x ):

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

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

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

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

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

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

print( nProg( 2 ) )

16. 
    Ответ: 47.