Количество программ с нестандартным условием: Исполнитель; 42, 1, 100, 152 · ЕГЭ №13

Условие, ответ и разбор задачи

Оператор присваивания и ветвления. Перебор вариантов, построение дерева

Профиматика Инф.

Исполнитель преобразует число на экране.

У исполнителя есть две команды, которые обозначены латинскими буквами:

A. Прибавь 1

B. Поменяй местами

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

Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 100 результатом является число 152?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы ABA при исходном числе 13 траектория состоит из чисел 14, 41, 42.

Ответ:

Решение

def f(x, y):
    if x > y: return 0
    if x == y: return 1
    k = f(x + 1, y)                               # команда A: прибавь 1
    if x // 10 % 10 < x % 10:                     # команда B применима
        k += f(x // 100 * 100 + x % 10 * 10 + x // 10 % 10, y)
    return k

print(f(100, 152))

$\textbf{Ответ: 42.}$

Количество программ с нестандартным условием: Исполнитель; 42, 1, 100, 152 · ЕГЭ №13

Похожие задачи