Решение задачи из ЕГЭ. №23 Динамическое программирование
380 просмотров
Условие задачи:
Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавь 1
2. Прибавь 3
3. Умножь на 2
Первая команда увеличивает число на экране на 1, вторая увеличивает его на 3, третья – умножает на 2. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 2 в число 51, и при этом траектория вычислений содержит число 18 и не содержит число 33. Также программа не должна содержать двух команд «Умножь на 2» подряд.
Решение:
n = 2finish = 51stop = 33commands = []flag = Falsedef f(): global n, flag if n == 18: flag = True if n > 18 and not flag: return 0 if n == finish: if '33' in ''.join(commands): return 0 else: return 1 elif n == stop: return 0 elif n > finish: return 0 n += 1 commands.append('1') b = flag s1 = f() flag = b commands.pop() n -= 1 n += 3 commands.append('2') b = flag s2 = f() flag = b commands.pop() n -= 3 n *= 2 commands.append('3') b = flag s3 = f() flag = b commands.pop() n /= 2 return s1 + s2 + s3print ("start") c = f()print ("finish")print (c)
