Группа Вопросы Вопросы Kotik 1 месяц назад

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

104 просмотра

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

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
Kotik
1 месяц назад
0
  1. n = 2
  1. finish = 51
  1. stop = 33
  1. commands = []
  1. flag = False
  1. def f():
  1. global n, flag
  1. if n == 18:
  1. flag = True
  1. if n > 18 and not flag:
  1. return 0
  1. if n == finish:
  1. if '33' in ''.join(commands):
  1. return 0
  1. else:
  1. return 1
  1. elif n == stop:
  1. return 0
  1. elif n > finish:
  1. return 0
  1. n += 1
  1. commands.append('1')
  1. b = flag
  1. s1 = f()
  1. flag = b
  1. commands.pop()
  1. n -= 1
  1. n += 3
  1. commands.append('2')
  1. b = flag
  1. s2 = f()
  1. flag = b
  1. commands.pop()
  1. n -= 3
  1. n *= 2
  1. commands.append('3')
  1. b = flag
  1. s3 = f()
  1. flag = b
  1. commands.pop()
  1. n /= 2
  1. return s1 + s2 + s3
  1. print ("start")
  1. c = f()
  1. print ("finish")
  1. print (c)
#