Динамическое программирование
Скачать 0.94 Mb.
|
Ещё пример задания:Р-08 (демо-вариант 2018 г.). Исполнитель М17 преобразует число на экране. У исполнителя есть три команды, которым присвоены номера: 1. Прибавить 1 2. Прибавить 2 3. Умножить на 3 Первая команда увеличивает число на экране на 1, вторая – увеличивает его на 2, а третья – умножает его на 3. Программа для исполнителя М17 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 12 и при этом траектория вычислений содержит числа 8 и 10? Решение:
, если N не делится на 3 , если N делится на 3
– переход от 2 до 8 – переход от 8 до 10 – переход от 10 до 12
Решение (программа на 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 ) + nProg( x*3, t ) print( nProg( 2, 8 ) * nProg( 8, 10 ) * nProg( 10, 12 ) )
|