Динамическое программирование
 Скачать 0.94 Mb.
|
Ещё пример задания:Р-04. Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя три команды, которым присвоены номера: 1. прибавь 1 2. прибавь 2 3. прибавь следующее Первая из них увеличивает число на экране на 1, вторая увеличивает это число на 2, а третья прибавляет к числу на экране число, большее на 1 (к числу 3 прибавляется 4, к числу 9 прибавляется 10 и т. д.). Программа для исполнителя Калькулятор– это последовательность команд. Сколько есть программ, которые число 2 преобразуют в число 10? Решение (1 способ, составление таблицы): заметим, что при выполнении любой из команд число увеличивается (не может уменьшаться) для начального числа 2 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; если через  обозначить количество разных программ для получения числа N из начального числа 2, то  .теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую с предыдущими элементами последовательности  , то есть с решениями таких же задач для меньших Nчисло N могло быть получено одной из трёх операций сложения: увеличением на 1 числа N-1; увеличением на 2 числа N-2; из некоторого числа X увеличением на X+1 (следующее число), так что N = X + X + 1, откуда X = (N – 1) / 2; так могут быть получены только нечетные числа; поэтому  для чётных чисел для нечётных чиселостается по этой формуле заполнить таблицу для всех значений от 2 до 10:
Ответ:– 47. Решение (программа на Python, Б.С. Михлин): полная программа: 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 ) ) Ответ: 47. |