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

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

Мы можем решить эту задачу с помощью рекурсивной функции, которая будет подсчитывать количество программ, ведущих от числа к числу за определённое количество шагов . В данной задаче:

1. — текущее число на экране;

2. — число, к которому нужно прийти после выполнения всех команд;

3. — количество уже выполненных команд.

Алгоритм работы функции следующий:

1. Проверяем, достигли ли мы необходимого количества команд:

- Если , то программа завершена.

* В этом случае функция возвращает True (или 1), если текущее число равно , и False (или 0) в противном случае.

2. Если , то продолжаем рекурсию:

- Пробуем первую команду: прибавляем 4 к числу , увеличиваем счётчик команд на 1, и вызываем функцию рекурсивно.

- Пробуем вторую команду: прибавляем 7 к числу , увеличиваем счётчик команд на 1, и вызываем функцию рекурсивно.

- Пробуем третью команду: делим число на 2 нацело (используя целочисленное деление), увеличиваем счётчик команд на 1, и вызываем функцию рекурсивно.

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

Таким образом, вызов функции f(1, 1, 0) запускает подсчёт всех возможных последовательностей из 10 команд, начинающихся с числа 1 и заканчивающихся числом 1.

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

# Запускаем функцию от исходного числа 1, целевого числа 1, с 0 выполненными командами
print(f(1, 1, 0))