23.02 Количество программ из A в B (на убывание)

Решение рекурсией

Идея решения с помощью рекурсии состоит в создании функции f(a, b), которая считает количество программ, преобразующих число в число . На каждом шаге проверяются следующие условия:

- Если равно , то найден корректный путь и функция возвращает 1;

- Если стало меньше , то путь невозможен и возвращается 0;

- Если ни одно из условий не выполнено, функция вызывает саму себя трижды, моделируя каждую из команд: a-1 (вычесть 1), a-3 (вычесть 3) и a//3 (целочисленное деление на 3). Сумма этих трёх вызовов даёт общее количество программ для текущего значения .

Таким образом, при вызове f(22, 2) функция рекурсивно перебирает все допустимые последовательности команд, подсчитывая количество способов достичь числа 2.

# Определяем рекурсивную функцию f(a, b) для подсчета программ
def f(a, b):
    # Если текущее число равно целевому числу,
    # то найден один корректный путь, возвращаем 1
    if a == b:
        return 1
    # Если текущее число меньше целевого,
    # дальнейшие преобразования невозможны, возвращаем 0
    if a < b:
        return 0
    # В остальных случаях считаем все возможные варианты:
    # 1) вычесть 1
    # 2) вычесть 3
    # 3) разделить нацело на 3
    # Суммируем количество программ из каждого варианта
    return f(a - 1, b) + f(a - 3, b) + f(a // 3, b)

# Запускаем функцию для исходного числа 22 и целевого числа 2
print(f(22, 2))

—

Решение динамикой

Динамический способ решения основывается на обратном построении массива, где индекс соответствует числу на экране, а значение в ячейке — количество способов из исходного числа 22 дойти до числа .

- Сначала создаём массив, заполненный нулями, длиной достаточной для хранения всех промежуточных значений, например, 70 элементов; - В ячейку с индексом 22 записываем 1, так как начинаем с числа 22 и существует ровно один способ быть в этом положении; - Затем проходим в цикле от 21 до 2 включительно, и для каждого числа вычисляем количество программ, суммируя:

   - — количество программ, которые придут к через команду "вычесть 1";

   - — количество программ, которые придут к через команду "вычесть 3";

   - , , — количество программ, которые придут к через команду "разделить нацело на 3 учитывая, что при делении нацело все числа , , дают в результате .

После заполнения всех ячеек, значение будет содержать общее количество программ, которые преобразуют число 22 в число 2.

# Создаем массив из 70 элементов, все значения изначально равны 0
a = [0] * 70
# Начальное число 22 имеет ровно один способ быть в позиции
a[22] = 1
# Перебираем все числа от 21 до 2 включительно в обратном порядке
for i in range(21, 1, -1):
    # Считаем количество программ для числа i,
    # суммируя варианты, которые приведут к i:
    # 1) из i+1 командой "вычесть 1"
    # 2) из i+3 командой "вычесть 3"
    # 3) из i*3, i*3+1, i*3+2 командой "разделить нацело на 3"
    a[i] = a[i + 1] + a[i + 3] + a[i * 3] + a[i * 3 + 1] + a[i * 3 + 2]

# Выводим количество программ, преобразующих 22 в 2
print(a[2])