23.06 Количество программ из A в B где траектория вычислений N команда

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

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

1. Проверяем, достигли ли мы цели:

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

2. Проверяем, не превысили ли мы допустимое количество команд:

- если count > end_count, возвращаем 0, так как путь не соответствует требуемой длине программы.

3. Считаем количество программ для каждого возможного действия:

- x — количество программ, если применить команду "поделить на 2"(только если число четное, проверяем через st % 2 == 0).

- y — количество программ, если применить команду "прибавить 1".

- z — количество программ, если применить команду "прибавить треть числа"(только если число кратно 3, проверяем через st % 3 == 0).

4. Складываем x + y + z для получения общего количества программ из данного состояния.

Для ускорения вычислений мы используем кэширование с помощью functools.lru_cache, чтобы повторно не вычислять одно и то же значение. Вызов функции f(1, 60, 0, 25) вернёт итоговое количество программ, начиная с числа 1, заканчивая на числе 60 ровно после 25 команд.

# Импортируем кэш для ускорения рекурсии
from functools import lru_cache

# Определяем рекурсивную функцию для подсчета количества программ
@lru_cache(None)
def f(st, fn, count, end_count):
    # Если текущее число равно целевому и использовано точное количество команд
    if st == fn and count == end_count:
        return 1
    # Если количество использованных команд превысило допустимое
    if count > end_count:
        return 0
    # Вычисляем количество программ для каждой команды
    # Команда 1: деление на 2, если число четное
    x = f(st // 2, fn, count + 1, end_count) * (st % 2 == 0)
    # Команда 2: прибавить 1
    y = f(st + 1, fn, count + 1, end_count)
    # Команда 3: прибавить треть числа, если число кратно 3
    z = f(st + st // 3, fn, count + 1, end_count) * (st % 3 == 0)
    # Складываем все варианты и возвращаем результат
    return x + y + z

# Вызываем функцию для исходного числа 1, целевого 60, 0 использованных команд и 25 команд всего
print(f(1, 60, 0, 25))

—

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

Мы можем использовать динамическое программирование для подсчета всех возможных траекторий. Основная идея заключается в том, что мы храним список ans, который содержит все числа, которые могут быть получены после определённого количества команд.

1. Инициализируем список ans с исходным числом 1.

2. Для каждой операции от 1 до 25:

   - Создаем пустой список can_get для хранения чисел, которые могут быть получены на следующем шаге.

   - Для каждого числа i из текущего списка ans:

      - если i четное, добавляем в can_get число i // 2 (команда "делить на 2");

      - добавляем i + 1 (команда "прибавить 1");

   - если i кратно 3, добавляем i + i // 3 (команда "прибавить треть числа").

   - После обработки всех чисел обновляем ans = can_get.

3. После 25 шагов список ans содержит все числа, которые могут быть получены после 25 команд. Количество вхождений числа 60 в списке ans — это ответ.

# Инициализируем список с исходным числом
ans = []
ans.append(1)

# Перебираем все 25 команд
for operations in range(25):
    # Создаем новый список для чисел, которые можно получить на следующем шаге
    can_get = []
    for i in ans:
        # Если число четное, можно применить команду "делить на 2"
        if i % 2 == 0:
            can_get.append(i // 2)
        # Применяем команду "прибавить 1"
        can_get.append(i + 1)
        # Если число кратно 3, применяем команду "прибавить треть числа"
        if i % 3 == 0:
            can_get.append(i + i // 3)
    # Обновляем список чисел для следующей итерации
    ans = can_get

# Считаем, сколько раз число 60 встречается в итоговом списке
print(ans.count(60))