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

Решение 1: Рекурсия

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

1. Сначала проверяем, достигли ли мы цели: если текущее число st равно целевому fn и количество использованных команд count равно end_count, то мы нашли подходящую программу и возвращаем 1.

2. Если текущее число меньше целевого или количество команд превысило end_count, путь невозможен, возвращаем 0.

3. В остальных случаях считаем все возможные переходы:

- Вызываем функцию для варианта st // 2, увеличивая счётчик команд на 1. Умножаем результат на (st % 2 == 0), чтобы учитывать деление только для чётных чисел.

- Вызываем функцию для варианта st - 3, увеличивая счётчик команд на 1.

- Вызываем функцию для варианта st - 1, увеличивая счётчик команд на 1.

4. Складываем результаты всех трёх вызовов, чтобы получить общее количество программ для текущего состояния.

5. Вызываем функцию с начальными значениями st = 33, fn = 12, count = 0, end_count = 9 и выводим результат.

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

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

—

Решение 2: Динамика

Мы используем динамический способ через перебор всех возможных чисел на каждом шаге программы.

1. Создаём список a, изначально содержащий одно число 33. Этот список хранит все текущие значения чисел после каждой команды.

2. Запускаем цикл по количеству команд (9 итераций). На каждой итерации:

- Сохраняем текущую длину списка n = len(a) для перебора всех элементов на текущем шаге.

- Для каждого элемента списка:

   - Убираем число из списка с помощью pop(0).

   - Если число больше целевого (12), добавляем в список новые значения, полученные применением каждой команды:

      - Деление на 2 для чётных чисел ((k // 2) * (k % 2 == 0)).

      - Вычитание 3 (k - 3).

      - Вычитание 1 (k - 1).

3. После всех 9 итераций считаем, сколько раз число 12 встречается в списке с помощью a.count(12), это и есть количество программ, которые за 9 шагов приводят число 33 к 12.

# Создаём список с исходным числом 33
a = [33]
# Перебираем все 9 команд
for i in range(9):
    # Сохраняем количество элементов на текущем шаге
    n = len(a)
    # Перебираем все текущие элементы
    for j in range(n):
        # Извлекаем число из списка
        k = a.pop(0)
        # Если число больше целевого 12, создаём новые состояния
        if k > 12:
            # Деление на 2, только если число чётное
            a.append((k // 2) * (k % 2 == 0))
            # Вычитание 3
            a.append(k - 3)
            # Вычитание 1
            a.append(k - 1)
# Считаем количество раз, когда в списке встречается число 12
print(a.count(12))