фыфы. Динамическое программирование
Скачать 0.85 Mb.
|
Ещё пример задания:Р-05. Исполнитель Июнь15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 21 и при этом траектория вычислений содержит число 10? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17. Решение (вариант 1): заметим, что при выполнении любой из команд число увеличивается (не может уменьшаться) для начального числа 1 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; если через обозначить количество разных программ для получения числа N из начального числа 1, то . теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую с предыдущими элементами последовательности , то есть с решениями таких же задач для меньших N число N могло быть получено одной из двух операций: увеличением на 1 числа N-1; умножением на 2 числа N/2 (только для N, которые делятся на 2); для нечётных чисел для чётных чисел поскольку траектория должна проходить через число 10, сначала выясняем, сколькими способами можно получить 10 из 1, а затем будем считать, сколько есть способов получить 21 из 10 заполняем таблицу от 1 до 10 по полученным формулам:
второй этап – определяем таким же образом (и по таким же формулам!), сколько есть способов получить конечное число 21 из 10, только левую часть таблицы (от 1 до 10) мы уже не рассматриваем:
Ответ: 28. Решение (вариант 2, А.Н. Носкин): первый этап (п. 1-6) такой же, как и в первом варианте (см. выше); на втором этапе используем такую идею: если мы знаем количество команд, с помощью которых из начального числа 1 можно получить 10 и определим количество команд, с помощью которых из 10 можно получить конечное значение 21, останется только перемножить эти два числа – это и будет ответ составляем таблицу для получения 21 из 10, используя те же рекуррентные формулы:
результат – 14 2 = 28 Ответ: 28. Решение (программа на Python, Б.С. Михлин): полная программа: # Функция подсчета количества цепочек команд (программ). # 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 ) ) Ответ: 28. |