Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Прибавь 2
B. Поменяй местами
Первая из этих команд увеличивает число на экране на 2.
Вторая команда применяется только к числу, у которого цифра в разряде десятков по значению меньше цифры, стоящей в разряде единиц, и действует, заменяя число на экране числом, в котором цифры двух младших разрядов поменялись местами.
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 20 результатом является число 98?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы ABA при исходном числе 23 траектория состоит из чисел 25, 52, 54.
Способ 1 (С рекурсией)
🔹 Шаг 1. Идея решения задачи
📌 Нужно посчитать количество программ, которые переводят число 20 → 98. У исполнителя две команды: прибавить 2 и поменять местами цифры десятков и единиц, если разряд десятков меньше разряда единиц.
🔹 Шаг 2. Функция и запретный случай
def f(x, y):
if x > y:
return 0
if x == y:
return 1
a = x // 100
b = (x // 10) % 10
c = x % 10
if b < c:
return f(x + 2, y) + f(a * 100 + c * 10 + b, y)
return f(x + 2, y)
print(f(20, 98))
📌 Функция f(x, y) считает число программ из x в y. Если x > y — путь невозможен, возвращаем 0.
🔹 Шаг 3. Успешное завершение
if x == y:
return 1
📌 Если текущее число равно целевому — найден один корректный путь.
🔹 Шаг 4. Цифры и команды
a = x // 100
b = (x // 10) % 10
c = x % 10
if b < c:
return f(x + 2, y) + f(a * 100 + c * 10 + b, y)
return f(x + 2, y)
📌 Выделяем цифры: a — сотни, b — десятки, c — единицы. Если b < c, доступны обе команды; иначе только +2.
🔹 Финальный шаг. Подсчёт
print(f(20, 98))
📌 Считаем количество программ из 20 в 98 — это и есть ответ 49.
Способ 1 (С рекурсией)
🔹 Шаг 1. Идея решения задачи
📌 Нужно посчитать количество программ, которые переводят число 20 → 98. У исполнителя две команды: прибавить 2 и поменять местами цифры десятков и единиц, если разряд десятков меньше разряда единиц.
🔹 Шаг 2. Функция и запретный случай
def f(x, y):
if x > y:
return 0
if x == y:
return 1
a = x // 100
b = (x // 10) % 10
c = x % 10
if b < c:
return f(x + 2, y) + f(a * 100 + c * 10 + b, y)
return f(x + 2, y)
print(f(20, 98))
📌 Функция f(x, y) считает число программ из x в y. Если x > y — путь невозможен, возвращаем 0.
🔹 Шаг 3. Успешное завершение
if x == y:
return 1
📌 Если текущее число равно целевому — найден один корректный путь.
🔹 Шаг 4. Цифры и команды
a = x // 100
b = (x // 10) % 10
c = x % 10
if b < c:
return f(x + 2, y) + f(a * 100 + c * 10 + b, y)
return f(x + 2, y)
📌 Выделяем цифры: a — сотни, b — десятки, c — единицы. Если b < c, доступны обе команды; иначе только +2.
🔹 Финальный шаг. Подсчёт
print(f(20, 98))
📌 Считаем количество программ из 20 в 98 — это и есть ответ 49.
Способ 1 (С рекурсией)
🔹 Шаг 1. Идея решения задачи
📌 Нужно посчитать количество программ, которые переводят число 20 → 98. У исполнителя две команды: прибавить 2 и поменять местами цифры десятков и единиц, если разряд десятков меньше разряда единиц.
🔹 Шаг 2. Функция и запретный случай
def f(x, y):
if x > y:
return 0
if x == y:
return 1
a = x // 100
b = (x // 10) % 10
c = x % 10
if b < c:
return f(x + 2, y) + f(a * 100 + c * 10 + b, y)
return f(x + 2, y)
print(f(20, 98))
📌 Функция f(x, y) считает число программ из x в y. Если x > y — путь невозможен, возвращаем 0.
🔹 Шаг 3. Успешное завершение
if x == y:
return 1
📌 Если текущее число равно целевому — найден один корректный путь.
🔹 Шаг 4. Цифры и команды
a = x // 100
b = (x // 10) % 10
c = x % 10
if b < c:
return f(x + 2, y) + f(a * 100 + c * 10 + b, y)
return f(x + 2, y)
📌 Выделяем цифры: a — сотни, b — десятки, c — единицы. Если b < c, доступны обе команды; иначе только +2.
🔹 Финальный шаг. Подсчёт
print(f(20, 98))
📌 Считаем количество программ из 20 в 98 — это и есть ответ 49.
