Объясните решение задачи. ЕГЭ 23

В данном задании мы должны пройтись по дереву (как структуре данных) с использованием определенных условий. Есть более формализованные объяснения задания (пример), но я попробую объяснить на наглядном упрощенном примере - достаточно уменьшить предельное число.

Возьмем условия: преобразуем 1 в 6, с обязательным включением 3, без 4.

Ожидаемый результат - "сколько существует программ". Максимально упрощенно это количество допустимых комбинаций действий "прибавить 1" и "умножить на 2", которые успешно преобразуют исходное число в итоговое.

Как посчитаем комбинации? Сделаем рекурсивную функцию, которая будет продолжаться с измененным двумя способами x - прибавлением и умножением:

def f(x, y):
    if x > y:
        # если `x` превысил `y`, значит комбинация вычислений оказалась неверна
        # не считаем комбинацию в результат (+0)
        return 0
    elif x == y:
        # если `x` равен `y`, значит ветка древа подходит под условия
        # считаем комбинацию в результат (+1)
        return 1
    else:
        # иначе можно продолжать создавать комбинации из 2х способов
        return f(x + 1, y) + f(x * 2, y)

Здесь мы можем обеспечить выполнение условия "траектория вычислений содержит число" - для этого посчитаем количество комбинаций, которые сначала обязательно приведут нас к числу 3 в процессе вычислений.

Проще говоря, вызовем указанную функцию с параметрами (1, 3):

1 узел:                        (1, 3)

2 узел:          (2, 3)           |          (2, 3)

3 узел: (3, 3) -> 1 | (4, 3) -> 0 | (3, 3) -> 1 | (4, 3) -> 0

Всего подходящих комбинаций: 2

То есть, всего от числа 1 до числа 3 нас успешно приведут 2 комбинации:

+1, +1 и *2, +1.

Они в конечном итоге по своей ветке дали return 1, а неподходящие наоборот - return 0. Все эти значения просуммировались в итоговый результат функции - 2.

Далее мы можем той же функцией посчитать количество комбинаций от 3 до итогового числа 6, а потом перемножить между собой первое полученное число и второе (правило умножения). Так получится число комбинацией, обязательно проходящих через число 3:

1 узел:                                 (3, 6)

2 узел:                   (4, 6) -> 0      |        (6, 6) -> 1

3 узел:           (5, 6)     |    (8, 6) -> 0

4 узел: (6, 6) -> 1 | (10, 6) -> 0 

Всего подходящих комбинаций: 2

Однако, нам нужно из последующего пути исключить прохождение вычислений через число 4. Для этого дополним функцию так, чтобы при x = 4 функция тоже возвращала 0, то есть не считала ветку дерева как годную:

def f(x, y):
    if x > y or x == 4:
        return 0
    elif x == y:
        return 1
    else:
        return f(x + 1, y) + f(x * 2, y)

При этом, если вызывать новую функцию с параметрами (1, 3) из первой части вычислений, то ничего не изменится, т.к. из-за предела в число 3 x = 4 это одновременно и условие x > y - в ограничивалось и до этого.

А вот уже при параметрах (3, 6) для второй части вычислений это убирает неподходящие комбинации:

1 узел:          (3, 6)

2 узел: (4, 6) -> 0 | (6, 6) -> 1

Всего подходящих комбинаций: 1

То есть, всего от числа 3 до числа 6, не заходя в число 4 нас успешно доведет только 1 комбинация: *2

Как указано выше, по правилу умножения перемножаем 2 полученных числа (2 и 1) для получения всех комбинаций (что и получится при вызове как f(1, 3) * f(3, 6)).

В итоге, мы получили ответ 2 - именно столько комбинаций из действий "прибавить 1" и "умножить на 2" существует, чтобы преобразовать 1 в 6, при этом обязательно получив в процессе вычислений 3, но не получив 4.

Выглядели бы эти комбинации как:

1 траектория: 112
(1 + 1 = 2 --> 2 + 1 = 3 --> 3 * 2 = 6)

2 траектория: 212
(1 * 2 = 2 --> 2 + 1 = 3 --> 3 * 2 = 6)

Если брать условия из исходной задачи, то дерево выйдет больше, будет сложнее его удержать в голове / нарисовать. Но принцип тот же.

Для большего понимания, можно заменить условие задачи. Например, допустимыми действиями программы будут "прибавить 1" и "прибавить 2". Тогда нам достаточно заменить в функции f(x + 1, y) + f(x * 2, y) на f(x + 1, y) + f(x + 2, y). В результате, рекурсивная функция будет просчитывать дерево из комбинаций новых действий.