Статья Автор: Лебедев Дмитрий Алексеевич

Решаем задание типа23. Подсчёт числа траекторий

Задание типа 23 (Динамическое программирование) относится к задания "повышенного уровня сложности", на решение которого отводится 8 минут.
Задание может быть решено "ручным" способом, с помощью табличного редактора (EXCEL) и "программным" способом.
Далее будет рассмотрен "программный способ решения с применением принципов динамического программирования. Можно сказать, что будет продолжен подход, использовавшийся при решении заданий типа 16 (рекурсия) и типа 19-20-21 (игровая стратегия)
Можно выделить несколько моделей заданий:

простые траектории
траектории с запретами
траектории с "узловыми точками"

Разберем некоторые примеры

Демоверсия 2025 года

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

A. Вычти 2
B. Найди целую часть от деления на 2

Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 38 результатом является число 2
и при этом траектория вычислений содержит число 16?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.

Траектория должна содержать "узловую точку" 16. Ответ можно определить как произведение чисел
\(N_{38}^{16}\cdot N_{16}^2, \ где\ N_a^b - \ количество\ траекторий\ a\ в\ b\)
Опишем программу получения значений \(N_a^b\)
Для стандартизации решения и уменьшения вероятности ошибки:

значения a, b будем вводить с клавиатуры
для упрощения передачи данных будем использовать словари dp и sf
"запреты", если они будут, занесем в множество zzz

Для решения можно пременить метод "снизу вверх" или "сверху вниз"

Применим метод "сверху вниз" или " end - start".
Для этого в точке "start" запишем 1 и определим "обратные" комнады, то есть поймем,
что в позицию pos можно попасть из "точек" pos+2, 2*pos, 2*pos +1

def f23a(pos):
  if (pos - sf['start'])*(pos - sf['end']) > 0 :
    return 0 # pos вне отрезка ['start','end']
  if pos in dp : # значение уже вычислено/задано 
    return dp[pos]
  dp[pos] = f23a(pos + 2) + f23a(2 * pos)+ f23a(2 * pos + 1)
  return dp[pos]
a, b = map(int,input().split())
sf = {'start': a, 'end': b}
dp = {a: 1}
print( f23a(b))

Запустим со значениями 38 и 16 (получим 3), 16 и 2 (получим 12). Ответ будет равен 36 (3*12)

Применим метод "снизу вверх" или "start - end".
Для этого в точке "end" запишем 1, операции изменять не надо.

def f23b(pos):
  if (pos - sf['start'])*(pos - sf['end']) > 0 :
    return 0 # pos вне отрезка ['start','end']
  if pos in dp : # значение уже вычислено/задано 
    return dp[pos]
  dp[pos] = f23b(pos - 2) + f23b(pos//2) 
  return dp[pos]
a, b = map(int,input().split())
sf = {'start': a, 'end': b}
dp = {b: 1}
print( f23b(a))

Для проверки условия "X находится между A и B" используется значение выражения (X-A)(X-B), которое:

равно 0, если X равен А или X равен B
меньше 0, если X строго между A и B
больше 0, если X не расположен между A, B

Это способ "работает" для любых значений A и B.

Ещё одна задача

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

A. Вычесть 1
B. Вычесть 5
C. Прибавить 7
D. Умножить на 2

Найдите количество существующих программ, для которых при исходном числе 9 результатом является число 84, и при этом траектория вычислений содержит число 60 и не содержит чисел, оканчивающихся на 3, а программа не содержит двух команд вычитания подряд.

Обычно решаем сначала по маршруту из 9 в 60, затем из 60 в 84. Для ответа результаты перемножим.
Но это было для "однонаправленного движения без повторов".
Для решения надо понять, что алгоритм "не имеет право" уходить в минус.

ПОЧЕМУ?

Рассмотрим задание как ориентированный граф, определив его следующим образом:

есть Позиция = (число, последняя команда)
выполнение команды - это переход в новую Позицию

Например

из позиции (15,C) можно перейти в позиции (14,A), (10,B), (22,C), (30,D),
а из позиции (15,A) можно перейти только в позиции (22,C), (30,D)

Обозначим:

Зададим множества Истоков Стоков.

Истоки - "сделаем" из стартовой точки по одному ход, Тогда множество запретов можно записать как 3, 13, 23, 33, 43, 53, 63, 73, 83 и при желании (для Фомы неверующего) 93

from time import process_time as prt 
def f23(pos) : # программа обработки
  a,k = pos
  pi = [ (a - 1, 0), (a - 5, 1), (a + 7, 2), (a + a,3)]
  for p in pi :
    if p[1] < 2 and k < 2 : continue
    if p[0] > sge[2] : continue
    if abs(p[0]) % 10 == 3 : continue
    if p[0] == sge[1] : 
      kk[p[1]] += 1
      continue
    dp.append(p)
  return
# 1 этап - из 9 в 60
t0 =prt() # отсечка времени
start, goal, end = 9, 60, 65
sge = [start, goal, end]
kk = [0, 0, 0, 0] # инициализация итоговых приходов
# инициализация очереди стартовыми позициями - можно упростить
dp = [(start-1, 0),(start-5, 1), (start+7, 2),(start * 2, 3)]
while dp : # перебор до опустошения очереди (почти DFS)
  pos = dp.pop() # последняя позиция
  f23(pos) # обработка позиции
r10 = kk[0]+kk[1] # итоговые приходы по "минусу"/"запретом на повтор операции"
r12 = kk[2]+kk[3] # итоговые приходы без запретов
print (r10, r12, kk, 'time =', prt()-t0)  
# 2 этап - из 60 d 84 - два запуска из (60,0) и (60,2)
t0 = prt()
start, goal, end = 60, 84, 89
sge = [start, goal, end]
kk = [0, 0, 0, 0]
dp = [(start, 0)]
while dp :
  pos = dp.pop()
  f23(pos)
r20 = sum (kk)  # количество решений для старта "с запретом" 
kk = [0, 0, 0, 0]
dp = [(start, 2)]
while dp :
  pos = dp.pop()
  f23(pos)
r22 = sum (kk)  # количество решений для старта "без запретов"
ans = r10*r20 + r12 * r22 # "фонтанчик" для вычислния результатов
print ('{} = {} * {} + {} * {}  time = {}'.format(ans,r10, r20,r12,r22, prt() - t0))

from time import process_time as prt 
def f23_all(pos) : # программа обработки
  a, k, flag = pos
  pi = [ (a - 1, 0,flag), (a - 5, 1, flag), (a + 7, 2, flag), (a + a,3, flag)]
  for p in pi :
    if p[1] < 2 and k < 2 : continue
    if p[0] > sge[2] + 5 : continue
    if abs(p[0]) % 10 == 3 : continue
    if (p[0] == sge[2]) and (flag == True)   : 
      kk[p[1]] += 1
      continue
    if p[0] > sge[1] + 5 and p[2] == False : continue  
    if p[0] == sge[1] :
      p = (p[0], p[1], True)
    dp.append(p)
      
  return
# 1 этап - из 9 в 84
t0 =prt() # отсечка времени
start, goal, end = 9, 60, 84
sge = [start, goal, end]
kk = [0, 0, 0, 0] # инициализация итоговых приходов
# инициализация очереди стартовыми позициями - можно упростить
dp = [(start-1, 0,False),(start-5, 1,False), (start+7, 2,False),(start * 2, 3,False)]
while dp : # перебор до опустошения очереди (почти DFS)
  pos = dp.pop() # последняя позиция
  f23_all(pos) # обработка позиции
ans = sum(kk) # итог
print (ans,  kk, 'time =', prt()-t0)

Чтобы оставить комментарий нужна авторизация

Печать