Количество программ исполнителя
Число программ, которые переводят одно число в другое, равно сумме таких чисел для всех чисел, из которых цель получается одной командой. Его считают таблицей от начального числа к конечному или рекурсивной функцией с мемоизацией. Обязательное число делит путь на два участка, и их количества перемножают, а запрещённое число получает в таблице ноль.
Как посчитать программы
— число программ, которые переводят начальное число в число .
- Начальному числу ставят : пустая программа.
- равно сумме всех чисел, из которых получается одной командой.
- Таблицу заполняют подряд от начального числа к конечному.
- Обязательное число : .
- Запрещённому числу ставят , и через него программы не проходят.
- Программа: функция
f(x, y)возвращает 1 приx == y, 0 приx > yили запрещённомx, иначе сумму вызовов для каждой команды.
Таблица количества программ
Программа — последовательность команд исполнителя. Траектория программы — все числа, которые появляются на экране после каждой команды. Разные программы с одним результатом — это разные пути от начального числа к конечному.
Последняя команда программы переводит в некоторое число . Поэтому все программы, которые дают , делятся на группы по предпоследнему числу , и — сумма по всем таким . Для команд «прибавить 1» и «умножить на 2»: , второе слагаемое есть только при чётном , и только если не меньше начального числа. Если команды только увеличивают число, числа меньше начального в таблицу не попадают.
Пример
У исполнителя две команды: «прибавить 1» и «умножить на 2». Сколько существует программ, которые переводят число 2 в число 12?
- 1.. В 3 можно попасть только из 2: .
- 2., .
- 3., .
- 4., .
- 5., , .
Ответ:
Запрещённое число
Условие «траектория не содержит число » запрещает проходить через . В таблице поставьте и считайте дальше по той же формуле: все программы, которые прошли бы через , исчезнут из сумм. Если запрещённых чисел несколько, ноль ставят каждому.
Пример
Команды «прибавить 1» и «умножить на 2». Сколько программ переводят 2 в 12, если траектория не содержит число 6?
- 1.До 6 таблица прежняя: , , , .
- 2.: число запрещено. .
- 3., , , .
- 4..
Ответ:
Обязательное число: произведение двух участков
Условие «траектория содержит число » делит каждую программу на две части: от начального числа до и от до конечного . Любую первую часть можно соединить с любой второй, поэтому . Вторую таблицу начинают заново: .
Если обязательных чисел два, участков три, и множителей тоже три. Числа ставят по пути: для увеличивающих команд — по возрастанию, для уменьшающих — по убыванию.
Пример задания
Открытый банк ФИПИ
Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1) Прибавить 1
2) Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 20 и при этом траектория вычислений содержит число 10? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
Программа: рекурсивная функция
Функция f(x, y) считает программы из x в y. Если x == y, программа одна. Если x уже больше y или x запрещён, программ нет. Иначе ответ — сумма f от результата каждой команды. Это та же формула, что в таблице, только записанная с начала пути. Строка @lru_cache(None) запоминает найденные значения, и программа работает быстро даже для больших чисел: мемоизация.
Обязательное число учитывают произведением вызовов: f(a, c) * f(c, b). Запрещённое — условием x == d рядом с x > y.
Пример
Команды: «прибавить 1», «прибавить 2», «умножить на 3». Сколько программ переводят 3 в 40, если траектория содержит 10 и не содержит 25?
- 1.Возврат 0 при
x > yостанавливает ветки, которые перескочили цель. - 2.Возврат 0 при
x == 25убирает программы через запрещённое число. - 3.В
returnтри слагаемых, по одному на каждую команду. - 4.Обязательное 10 даёт произведение
f(3, 10) * f(10, 40). Программа печатает 8188906.
Ответ:
Команды, которые уменьшают число
Команды «вычти 1» и «найди целую часть от деления на 2» уменьшают число. Тогда путь идёт сверху вниз: ветка останавливается, когда x стал меньше цели, то есть условие x < y вместо x > y. Целую часть от деления в Python даёт x // 2. Обязательные числа ставят по убыванию: от 50 через 20 к 1.
Пример задания
Открытый банк ФИПИ
Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами:
А) Вычти 1
В) Найди целую часть от деления на 2
Первая из них уменьшает число на экране на 1, вторая заменяет число на экране на целую часть от деления числа на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 50 результатом является число 1, и при этом траектория вычислений содержит число 20 и не содержит 10? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы АВВ при исходном числе 10 траектория состоит из чисел 9, 4, 2.
Команда с условием
Бывает команда, которую можно выполнить не с каждым числом. Пример — «поменяй местами две младшие цифры»: она применяется, только если цифра десятков меньше цифры единиц. Число 113 она переводит в 131, а к числу 131 не применяется. Такая команда тоже увеличивает число: большая цифра переходит в разряд десятков.
В таблице число получает слагаемое от этой команды, только если команда применима к предыдущему числу. В функции f(x, y) слагаемое команды добавляют под if. Цифра десятков — x // 10 % 10, цифра единиц — x % 10.
Пример
Команды: A — «прибавь 1», B — «поменяй местами две младшие цифры», если цифра десятков меньше цифры единиц. Сколько программ переводят 110 в 132?
- 1.Все команды увеличивают число, поэтому ветка останавливается при
x > y. - 2.Команда A есть всегда: слагаемое
f(x + 1, y). - 3.Команда B есть только при
x // 10 % 10 < x % 10. Функцияswapсобирает число из сотен, цифры единиц на месте десятков и цифры десятков на месте единиц. - 4.Программы вручную: только A; 112 в 121 командой B; 123 в 132 командой B; обе замены, 112 в 121 и 123 в 132; 113 в 131 командой B. Программа печатает 5.
Ответ:
Количество путей в ориентированном графе
Числа исполнителя и команды образуют ориентированный ациклический граф: вершины — числа, дуги — команды, и по стрелкам нельзя вернуться в ту же вершину. Поэтому число путей в таком графе считают тем же способом. Начальной вершине пишут 1. Каждой следующей вершине пишут сумму чисел всех вершин, из которых в неё входит стрелка. Вершины обходят так, чтобы все входящие стрелки шли из уже посчитанных вершин.
Путь через обязательную вершину — произведение числа путей до неё и от неё. Запрещённой вершине пишут 0.
Пример
Дороги с односторонним движением показаны на рисунке. Сколько путей ведёт из А в Е? Сколько из них не проходит через Г?
- 1.А — 1. В Б входит стрелка из А: 1. В В — из А и Б: .
- 2.В Г — из Б и В: . В Д — из В и Г: . В Е — из Г и Д: .
- 3.Без Г: ставим Г — 0. Д: . Е: .
Ответ: путей, из них не проходят через Г