Задание 23
тема 2 из 2

Количество программ исполнителя

Число программ, которые переводят одно число в другое, равно сумме таких чисел для всех чисел, из которых цель получается одной командой. Его считают таблицей от начального числа к конечному или рекурсивной функцией с мемоизацией. Обязательное число делит путь на два участка, и их количества перемножают, а запрещённое число получает в таблице ноль.

Главная тема в задании23На карте навыков

Как посчитать программы

K(n)K(n) — число программ, которые переводят начальное число в число nn.

  • Начальному числу ставят K=1K = 1: пустая программа.
  • K(n)K(n) равно сумме KK всех чисел, из которых nn получается одной командой.
  • Таблицу заполняют подряд от начального числа к конечному.
  • Обязательное число cc: K(a→b)=K(a→c)⋅K(c→b)K(a \to b) = K(a \to c) \cdot K(c \to b).
  • Запрещённому числу ставят K=0K = 0, и через него программы не проходят.
  • Программа: функция f(x, y) возвращает 1 при x == y, 0 при x > y или запрещённом x, иначе сумму вызовов для каждой команды.

Таблица количества программ

Программа — последовательность команд исполнителя. Траектория программы — все числа, которые появляются на экране после каждой команды. Разные программы с одним результатом — это разные пути от начального числа к конечному.

Последняя команда программы переводит в nn некоторое число mm. Поэтому все программы, которые дают nn, делятся на группы по предпоследнему числу mm, и K(n)K(n) — сумма K(m)K(m) по всем таким mm. Для команд «прибавить 1» и «умножить на 2»: K(n)=K(n−1)+K(n/2)K(n) = K(n - 1) + K(n / 2), второе слагаемое есть только при чётном nn, и только если n/2n / 2 не меньше начального числа. Если команды только увеличивают число, числа меньше начального в таблицу не попадают.

Пример

У исполнителя две команды: «прибавить 1» и «умножить на 2». Сколько существует программ, которые переводят число 2 в число 12?

  1. 1.K(2)=1K(2) = 1. В 3 можно попасть только из 2: K(3)=1K(3) = 1.
  2. 2.K(4)=K(3)+K(2)=2K(4) = K(3) + K(2) = 2, K(5)=K(4)=2K(5) = K(4) = 2.
  3. 3.K(6)=K(5)+K(3)=3K(6) = K(5) + K(3) = 3, K(7)=3K(7) = 3.
  4. 4.K(8)=K(7)+K(4)=5K(8) = K(7) + K(4) = 5, K(9)=5K(9) = 5.
  5. 5.K(10)=K(9)+K(5)=7K(10) = K(9) + K(5) = 7, K(11)=7K(11) = 7, K(12)=K(11)+K(6)=10K(12) = K(11) + K(6) = 10.

Ответ: 1010

Запрещённое число

Условие «траектория не содержит число dd» запрещает проходить через dd. В таблице поставьте K(d)=0K(d) = 0 и считайте дальше по той же формуле: все программы, которые прошли бы через dd, исчезнут из сумм. Если запрещённых чисел несколько, ноль ставят каждому.

Пример

Команды «прибавить 1» и «умножить на 2». Сколько программ переводят 2 в 12, если траектория не содержит число 6?

  1. 1.До 6 таблица прежняя: K(2)=1K(2) = 1, K(3)=1K(3) = 1, K(4)=2K(4) = 2, K(5)=2K(5) = 2.
  2. 2.K(6)=0K(6) = 0: число запрещено. K(7)=K(6)=0K(7) = K(6) = 0.
  3. 3.K(8)=K(7)+K(4)=2K(8) = K(7) + K(4) = 2, K(9)=2K(9) = 2, K(10)=K(9)+K(5)=4K(10) = K(9) + K(5) = 4, K(11)=4K(11) = 4.
  4. 4.K(12)=K(11)+K(6)=4+0=4K(12) = K(11) + K(6) = 4 + 0 = 4.

Ответ: 44

Обязательное число: произведение двух участков

Условие «траектория содержит число cc» делит каждую программу на две части: от начального числа aa до cc и от cc до конечного bb. Любую первую часть можно соединить с любой второй, поэтому K(a→b)=K(a→c)⋅K(c→b)K(a \to b) = K(a \to c) \cdot K(c \to b). Вторую таблицу начинают заново: K(c)=1K(c) = 1.

Если обязательных чисел два, участков три, и множителей тоже три. Числа ставят по пути: для увеличивающих команд — по возрастанию, для уменьшающих — по убыванию.

Пример задания

Открытый банк ФИПИ

Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
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. 1.Возврат 0 при x > y останавливает ветки, которые перескочили цель.
  2. 2.Возврат 0 при x == 25 убирает программы через запрещённое число.
  3. 3.В return три слагаемых, по одному на каждую команду.
  4. 4.Обязательное 10 даёт произведение f(3, 10) * f(10, 40). Программа печатает 8188906.

Ответ: 81889068188906

Команды, которые уменьшают число

Команды «вычти 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 не применяется. Такая команда тоже увеличивает число: большая цифра переходит в разряд десятков.

В таблице число nn получает слагаемое от этой команды, только если команда применима к предыдущему числу. В функции f(x, y) слагаемое команды добавляют под if. Цифра десятков — x // 10 % 10, цифра единиц — x % 10.

Пример

Команды: A — «прибавь 1», B — «поменяй местами две младшие цифры», если цифра десятков меньше цифры единиц. Сколько программ переводят 110 в 132?

  1. 1.Все команды увеличивают число, поэтому ветка останавливается при x > y.
  2. 2.Команда A есть всегда: слагаемое f(x + 1, y).
  3. 3.Команда B есть только при x // 10 % 10 < x % 10. Функция swap собирает число из сотен, цифры единиц на месте десятков и цифры десятков на месте единиц.
  4. 4.Программы вручную: только A; 112 в 121 командой B; 123 в 132 командой B; обе замены, 112 в 121 и 123 в 132; 113 в 131 командой B. Программа печатает 5.

Ответ: 55

Количество путей в ориентированном графе

Числа исполнителя и команды образуют ориентированный ациклический граф: вершины — числа, дуги — команды, и по стрелкам нельзя вернуться в ту же вершину. Поэтому число путей в таком графе считают тем же способом. Начальной вершине пишут 1. Каждой следующей вершине пишут сумму чисел всех вершин, из которых в неё входит стрелка. Вершины обходят так, чтобы все входящие стрелки шли из уже посчитанных вершин.

Путь через обязательную вершину — произведение числа путей до неё и от неё. Запрещённой вершине пишут 0.

Пример

Дороги с односторонним движением показаны на рисунке. Сколько путей ведёт из А в Е? Сколько из них не проходит через Г?

АБВГДЕ
Стрелка показывает, в какую сторону можно ехать.
  1. 1.А — 1. В Б входит стрелка из А: 1. В В — из А и Б: 1+1=21 + 1 = 2.
  2. 2.В Г — из Б и В: 1+2=31 + 2 = 3. В Д — из В и Г: 2+3=52 + 3 = 5. В Е — из Г и Д: 3+5=83 + 5 = 8.
  3. 3.Без Г: ставим Г — 0. Д: 2+0=22 + 0 = 2. Е: 0+2=20 + 2 = 2.

Ответ: 88 путей, из них 22 не проходят через Г

Потренируйте навык

Все задания на этот навык

Решать