Траектории программ и подсчёт путей
Почему количества альтернатив складываются, последовательные участки перемножаются и когда для подсчёта требуется дополнительное состояние.
Одно и то же число может быть результатом множества программ. Чтобы посчитать их без полного перечисления, нужно объединять одинаковые задачи продолжения, сохраняя количество способов до них добраться. Основание такого подсчёта — устройство переходов между состояниями исполнителя.
Программа, траектория и граф
Для числового исполнителя состоянием в простейшей задаче служит число на экране. Каждая разрешённая команда переводит его в следующее число. Если изобразить числа точками, а команды стрелками, получится ориентированный граф состояний.
Программа задаёт последовательность команд, то есть переходов по стрелкам. Траектория записывает результаты этих переходов. Различие существенно: две команды иногда ведут из одного числа в одно и то же другое число. Например, для числа 2 умножение на 2 и возведение в квадрат дают 4, но остаются разными командами. На графе им соответствуют две отдельные стрелки между теми же точками.
Поэтому количество программ не равно ни количеству достигнутых чисел, ни обязательно количеству различных числовых траекторий. Информация о выборе команды сохраняется даже при совпадении соседних состояний.
Почему складываются количества
Пусть F(n) — количество программ от выбранного старта до числа n. Для команд «прибавить 1» и «прибавить 3» любая программа в n заканчивается ровно одной из двух команд. Перед ней на экране было соответственно n-1 или n-3.
Удаление последней команды даёт программу до соответствующего предшественника. Обратно, добавление этой команды к любой программе до предшественника даёт программу до n. Группы не пересекаются, поскольку их последние команды различны. Поэтому:
F(n)=F(n-1)+F(n-3).
Если разрешено также умножение на 3, добавляется F(n/3), но только при делимости n на 3. Это не округлённое деление: для обратного перехода нужен целый предшественник, который после умножения даст ровно нужное число.
Сложение по командам сохраняет и совпадающие результаты. При командах удвоения и возведения в квадрат две стрелки из 2 в 4 дают два вклада по F(2). Они относятся к разным последним командам, поэтому двойного учёта одной программы здесь нет.
Начальная единица и порядок вычислений
В начальном числе a принимается F(a)=1. Единица обозначает один пустой путь. Если поставить ноль, добавление первой команды не создаст ни одного способа: все последующие суммы тоже окажутся нулевыми.
Чтобы вычислить сумму, количества для её предшественников должны быть уже известны. Когда все команды строго увеличивают число, подходят возрастающие значения. При строго убывающих командах — убывающие. Такой подсчёт с сохранением результатов подзадач называется динамическим программированием.
Строгое изменение в одном направлении не позволяет вернуться к прежнему числу. Поэтому граф не содержит циклов. Для конечного целевого диапазона это даёт конечное число рассматриваемых состояний и порядок, в котором каждое зависит только от уже обработанных.
Что означает запрет
Запрещённое число не должно появляться в траектории ни одной учтённой программы. Поэтому для запрещённого состояния b устанавливается F(b)=0, даже если арифметически оно достижимо. Последующие состояния уже не получат из него никаких допустимых программ.
При этом переход через запрещённое значение без попадания в него допустим. Команда +3 из 10 сразу даёт 13: состояния 11 и 12 не возникают. Если запрещено 12, такой переход сохраняется. Запрещаются результаты команд, а не все числа между началом и концом стрелки.
Почему обязательные участки перемножаются
Пусть начало равно a, цель — c, а обязательное промежуточное число — b. Предположим, что каждый подходящий путь проходит b ровно один раз и после него допустимые продолжения не зависят от способа прихода. Это верно для рассматриваемых монотонных задач с запретом отдельных чисел.
Каждая полная программа однозначно разделяется на часть до b и часть после него. Если первую часть можно выбрать p способами, а вторую — q, у каждого из p начал есть все q продолжений. Получается p\cdot q пар, то есть столько же полных программ.
Например, при 60 началах и трёх продолжениях число пар равно 60\cdot3=180. Обязательная точка сама не является дополнительной командой: первый участок заканчивается в ней, второй начинает выполнение из неё.
Для нескольких обязательных чисел используется цепочка участков. При возрастании точки располагаются по возрастанию, при убывании — по убыванию. Условие «содержит оба числа» задаёт последовательное прохождение, поэтому количества участков перемножаются. Сложение применяется к непересекающимся альтернативам, а не к последовательным требованиям.
Когда одного числа в состоянии недостаточно
Если команды допускают возврат, граф может содержать цикл. Повторный приход в то же число уже не обязательно означает, что пройден тот же объём допустимой программы. При ограничении длины состояние должно хранить пару: текущее число и количество выполненных команд.
Учебный пример: из нуля разрешены +2 и -1, требуется выполнить ровно две команды. Каждому выбору первой команды соответствуют два выбора второй, поэтому программ четыре. Их результаты:
| Последовательность команд | Конечное число |
|---|---|
| +2,+2 | 4 |
| +2,-1 | 1 |
| -1,+2 | 1 |
| -1,-1 | -2 |
Различных результатов только три: \{-2,1,4\}. Для вопроса о программах количества одинаковых результатов складываются; для вопроса о разных результатах совпадения объединяются в множество. Отрицательное число не отбрасывается, поскольку в учебном примере оно разрешено. Условие «ровно две» использует только второй слой шагов; «не более двух» потребовало бы рассмотреть также более короткие программы.
Почему в задаче с обязательным числом количества участков умножаются, а внутри каждого участка — складываются? Как изменится порядок вычислений, если все команды уменьшают число? Оба случая разобраны в материале «Задание №13. Подсчёт программ: обязательные и запрещённые числа».