Шаблон программного решения:
def F(x, y): # возвращает количество путей из x в y
# если начальное больше
if x > y or x == <число, не содержащееся в траектории>:
return 0 # возвращаем 0 путей
# количество путей из числа в само себя равно 1
if x == y:
return 1
# в остальных случаях x < y
return <Сумма функций с учетом команд>
# в выводе указываем начало, конец, а также все промежуточные числа по траектории
print(F(<начальное знач>, <доп. знач. 1>) * F(<доп. знач. 2>, <конечное знач.>) )
Если в условии есть команды «вычти» или «подели», то изменяем в шаблоне: if x > y: на if x < y:
Пример задания
Исполнитель К20 преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Увеличить старшую цифру числа на 1
Первая команда увеличивает число на экране на 1, вторая увеличивает на 1 старшую (левую) цифру числа. Например, число 23 с помощью такой команды превратится в число 33. Если старшая цифра числа равна 9, то вторая команда оставляет это число неизменным. Программа для исполнителя — это последовательность команд. Сколько существует таких программ, которые исходное число 10 преобразуют в число 43?
Решение. Выполнить команду 2 для исполнителя, зная, что в данной ситуации работа ведется с двузначными числами, можно следующим образом: x + 10. Напишем программу с использованием рекурсии для поиска количества путей:
def F(x, y):
if x > y:
return 0 # возвращаем 0 путей
if x == y:
return 1
return F(x + 1, y) + F(x + 10, y)
print(F(10, 43))
Ответ: 150
Или вот такую программу предлагает ИИ для той же задачи:
def count_programs(start, target):
dp = [0] * (target + 1)
dp[start] = 1
for x in range(start, target):
# Команда 1: Прибавить 1
dp[x + 1] += dp[x]
# Команда 2: Увеличить старшую цифру на 1
str_x = str(x)
if str_x[0] != '9': # Если старшая цифра не 9
new_number = int(str_x[0]) + 1
new_x = new_number * (10 ** (len(str_x) - 1)) + int(str_x[1:])
if new_x <= target:
dp[new_x] += dp[x]
return dp[target]
start = 10
target = 43
result = count_programs(start, target)
print(f"Количество программ, преобразующих {start} в {target}: {result}")
Прототипы с ЕГЭ
Задача №1 Исполнитель А16 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 2
Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает его на 2. Программа для исполнителя А16 – это последовательность команд.
Сколько существует таких программ, которые исходное число 3 преобразуют в число 12 и при этом траектория вычислений программы содержит число 10?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 16, 18.
Ответ: 60
Задача №2 Исполнитель Май преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Май — это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 39 и при этом траектория вычислений содержит числа 7 и 16?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
Ответ: 45
Задача №3 Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 3
Первая команда увеличивает число на 1, вторая – на 2, третья - втрое. Программа для исполнителя – это последовательность команд.
Сколько существует таких программ, которые исходное число 2 преобразуют в число 19 и при этом траектория вычислений программы проходит через 9 и не проходит через 12?
Ответ: 650
Задача №4 Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Вычти 1
2. Найди целую часть от деления на 2
Первая из них уменьшает число на экране на 1, вторая заменяет число на экране на целую часть от деления числа на 2. Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 30 результатом является число 1, и при этом траектория вычислений содержит число 12?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 122 при исходном числе 10 траектория состоит из чисел 9, 4, 2.
Ответ: 376
Задача №5 Исполнитель Троечка преобразует число, записанное на доске. У Троечки есть две команды:
1. Вычесть 3
2. Умножить на -3
Первая команда уменьшает число на 3, вторая команда умножает его на –3. Сколько различных отрицательных результатов можно получить из исходного числа 333 в ходе исполнения программы, содержащей ровно 13 команд?
Ответ: 2224
Задача №6 Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Умножить на 2
C. Возвести в квадрат
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 20, при этом траектория вычислений не содержит числа 11?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 4 траектория будет состоять из чисел 16, 32, 33.
Ответ: 37
Задания уровня ЕГЭ
Задача №1 Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 2
Первая команда увеличивает число на 1, вторая – на 2, третья – вдвое. Программа для исполнителя – это последовательность команд.
Сколько существует таких программ, которые исходное число 3 преобразуют в число 25 и при этом в программе есть все три команды?
Ответ: 15092
Задача №2 Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
3. Сделать нечетное
Первая команда увеличивает число на 1, вторая – вдвое, третья прибавляет к четному числу 1, к нечетному – 2. Программа для исполнителя – это последовательность команд.
Сколько существует таких программ, которые исходное число 3 преобразуют в число 25 и при этом траектория вычислений программы содержит число 9 и число 17?
Ответ: 229635
Задача №3 Исполнитель Джысум преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить значение младшего разряда
2. Умножить на значение старшего разряда
3. Прибавить разность большего и меньшего по значению разрядов
Первая команда не применима к числам, кратным 10. Вторая команда не применима к числам, меньшим 20. Третья команда не применима к числам c одинаковыми цифрами. Например, при применении команды 1 к числу 19 получим число 28, при применении команды 2 к числу 22 – 44, команды 3 к 41 – 44.
Сколько существует таких программ, которые исходное число 21 преобразуют в число 62?
Ответ: 142
Задача №4 У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 1
2. увеличь число десятков на 1
Например: при помощи команды 2 число 23 преобразуется в 33. Если перед выполнением команды 2 вторая с конца цифра равна 9, она не изменяется.
Сколько есть программ, которые число 10 преобразуют в число 33?
Ответ: 25
