фыфы. Динамическое программирование
Скачать 0.85 Mb.
|
Ещё пример задания:Р-06. У исполнителя Удвоитель две команды, которым присвоены номера: 1. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Удвоитель – это последовательность команд. Сколько существует программ, преобразующих число 4 в число 24, предпоследней командой которых является команда «1»? Решение: итак, мы знаем предпоследнюю команду – 1, при этом последняя команда может быть любая – 1 или 2 выходит, что нужно получить количество всех программ вида «*11» и «*12», где звёздочка обозначает любые команды если программа заканчивается на «11», то до выполнения цепочки «11» у нас было число 24 – 1 – 1 = 22; поэтому нужно найти число программ для преобразования 4 в 22 для начального числа 1 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; если через обозначить количество разных программ для получения числа N из начального числа 1, то . теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую с предыдущими элементами последовательности , то есть с решениями таких же задач для меньших N число N могло быть получено одной из двух операций: увеличением на 1 числа N-1; умножением на 2 числа N/2 (только для N, которые делятся на 2, и таких, что N/2 4); для нечётных чисел для чётных чисел, таких, что N/2 4 составляем таблицу:
теперь рассматриваем случай, когда программа заканчивается на «12», это значит, что до выполнения цепочки «12» у нас было число (24/ 2) – 1 = 11; поэтому нужно найти число программ для преобразования 4 в 11, берём его из таблицы: 3 ответ к задаче – сумма двух значений, выделенных жёлтым маркером: 15 + 3 = 18, поскольку мы рассмотрели все варианты программ, в которых предпоследняя команда – 1 Ответ: 18. Решение (программа на Python): полная программа: 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 ) ) Ответ: 18. Решение (ещё один варианты программы на Python, Б.С. Михлин): полная программа: 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 ) ) Ответ: 18. |