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

Решаем задание типа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


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

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


Для проверки условия "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



 


Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать