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

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

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

На каждом шаге выполняются следующие проверки:

- Если st == fn, значит текущее число совпало с целевым, найден один путь, возвращаем 1.

- Если st < fn, то текущее число меньше целевого, дальнейшие преобразования невозможны, возвращаем 0.

- Иначе функция делает три рекурсивных вызова:

1. f(st // 3, fn) * (st % 3 == 0) — учитываем команду "поделить на 3"только если число кратно 3, иначе результат будет 0.

2. f(st // 2, fn) * (st % 2 == 0) — учитываем команду "поделить на 2"только если число кратно 2, иначе результат будет 0.

3. f(st - 3, fn) — учитываем команду "вычесть 3".

Итоговое количество программ вычисляется как сумма этих трёх значений. Запуск функции с начальными аргументами f(30, 3) подсчитает все возможные последовательности команд.

# Определяем рекурсивную функцию f(st, fn), которая считает количество программ
def f(st, fn):
    # Если текущее число совпало с целевым, возвращаем 1
    if st == fn:
        return 1
    # Если текущее число меньше целевого, пути нет, возвращаем 0
    if st < fn:
        return 0
    # Считаем количество программ, использующих команду "поделить на 3", если число кратно 3
    x = f(st // 3, fn) * (st % 3 == 0)
    # Считаем количество программ, использующих команду "поделить на 2", если число кратно 2
    y = f(st // 2, fn) * (st % 2 == 0)
    # Считаем количество программ, использующих команду "вычесть 3"
    z = f(st - 3, fn)
    # Суммируем все возможные варианты
    return x + y + z

# Вызываем функцию для исходного числа 30 и целевого числа 3
print(f(30, 3))

—

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

Идея динамического решения состоит в том, чтобы построить массив a, где индекс соответствует числу, а значение — количеству способов добраться от этого числа до целевого.

- Инициализируем массив нулями: a = [0] * 100.

- В ячейку с индексом 30 записываем 1, так как мы начинаем с числа 30.

- Проходим по всем числам от 29 до 3 (включительно) в обратном порядке. Для каждого числа i считаем количество способов, складывая:

1. a[i + 3] — вариант "вычесть 3"из числа i + 3 приводит в i.

2. a[i * 3] — вариант "поделить на 3"из числа i * 3 приводит в i.

3. a[i * 2] — вариант "поделить на 2"из числа i * 2 приводит в i.

После заполнения массива, значение a[3] будет содержать количество программ, преобразующих число 30 в число 3.

# Создаем массив из 100 элементов, все значения изначально равны 0
a = [0] * 100
# Исходное число 30 имеет один способ быть на этом месте
a[30] = 1
# Перебираем числа от 29 до 3 включительно в обратном порядке
for i in range(29, 2, -1):
    # Количество способов для i равно сумме способов из i+3, i*3 и i*2
    a[i] = a[i + 3] + a[i * 3] + a[i * 2]

# Выводим количество программ, которые ведут от 30 к 3
print(a[3])