Вопросы Kotik 1 год назад

Задача на динамическое программирование

442 просмотра

Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавь 1
2. Прибавь 3
3. Умножь на 2

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 3, третья – умножает на 2. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 2 в число 51, и при этом траектория вычислений содержит число 18 и не содержит число 33. Также программа не должна содержать двух команд «Умножь на 2» подряд.

Мой код и ответ неправильный.

from functools import lru_cache@lru_cache(None)def fn(s, f, c, k): if s == 33: return 0 if '33' in c: return 0 if '33' in k: return 0 if s == f: if not '33' in c: if '18' in k: if not '33' in k: return 1 else: return 0 else: return 0 else: return 0 elif s > f: return 0 else:

        return fn(s+1, f, c+'1', k + '_' + str(s)) + fn(s+3, f, c+'2', k + '_' + str(s)) + fn(s*2, f, c+'3', k + '_' + str(s))

print(fn(2, 51, '', '_'))

вопрос помощь егэ

Kotik+55

Я вернулся

1 комментарий

Kotik
1 год назад

n = 2

finish = 51

stop = 33

commands = []

flag = False

def 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 + s3

print ("start")

c = f()

print ("finish")

print (c)