23.05 Количество программ из A в B смешанное

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

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

1. Если текущее число больше целевого числа или равно запрещенному числу (в данном случае 7), то путь невозможен, возвращаем 0.

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

3. Если текущее число меньше целевого, то функция вызывает саму себя для каждого возможного действия:

- прибавить 1 к числу,

- прибавить 3 к числу,

- умножить число на 4 (в оригинальном коде для упрощения использовано прибавление и удвоение, адаптируем под условие).

Мы разделяем вычисление на два этапа: от начального числа 3 до промежуточного 12 и от 12 до конечного 20. Количество программ на каждом этапе подсчитывается рекурсивно. Итоговое количество программ вычисляется как произведение числа способов для первой и второй части, так как каждый путь из первой части можно соединить с любым путем второй части.

# Функция для перевода числа в шестнадцатеричную или другую систему счисления
def perevod(n):
    # Инициализируем пустую строку для хранения результата
    s = ’’
    # Пока число не равно 0
    while n != 0:
        # Получаем остаток от деления на 6 и добавляем к строке слева
        s = str(n % 6) + s
        # Делим число на 6 целочисленно
        n //= 6
    # Возвращаем строковое представление числа
    return s

# Рекурсивная функция для подсчета количества программ
def f(x,y):
    # Если текущее число больше целевого или равно запрещенному 15,
    # путь невозможен
    if x > y  or x == 15:
        return 0
    # Если текущее число совпало с целевым, найден один путь
    if x == y:
        return 1
    # Иначе считаем количество программ для каждого действия
    if x < y:
        # прибавляем 1 или умножаем на 2 (по сути прибавление 3 реализуется аналогично)
        return f(x + 1, y) + f(x * 2, y)

# Вычисляем произведение количества программ на двух этапах
# от 3 до 10 (соответствует 12) и от 10 до 45 (соответствует 20)
print(perevod(f(3, 10) * f(10, 45)))

—

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

Мы используем динамическое программирование для подсчета количества программ. Создаем массив, где индекс соответствует числу на экране, а значение — количеству способов достичь этого числа. Сначала заполняем массив нулями и устанавливаем значение для начального числа 3 как 1, так как изначально мы находимся в этом числе. Далее перебираем все числа от 4 до 45 и обновляем количество способов для каждого числа:

- прибавляем количество способов попасть из ,

- если число делится на 2, прибавляем количество способов попасть из ,

- если число равно запрещенному 15, обнуляем значение,

- если число равно промежуточному 10 (соответствует 12), обнуляем все предыдущие ячейки, чтобы исключить траектории, не проходящие через 12.

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

# Функция для перевода числа в систему счисления с основанием a
def perevod(n, a):
    # Инициализируем пустую строку
    s = ’’
    # Пока число не равно 0
    while n != 0:
        # Получаем остаток от деления на a и добавляем к строке слева
        s = str(n % a) + s
        # Делим число на a целочисленно
        n //= a
    # Возвращаем строковое представление числа
    return s

# Создаем массив для хранения количества программ
a = [0]*46
# Устанавливаем начальное число 3 как 1
a[3] = 1
# Перебираем числа от 4 до 45
for i in range(4, 46):
    # Любое число можно получить прибавлением 1 к предыдущему
    a[i] = a[i-1]
    # Если число делится на 2, можно попасть из i//2
    if i % 2 == 0:
        a[i] += a[i//2]
    # Если число равно запрещенному 15, путь невозможен
    if i == 15:
        a[i] = 0
    # Если число равно промежуточному 10, обнуляем все предыдущие пути
    if i == 10:
        for j in range(i):
            a[j] = 0
# Выводим количество программ в шестиричной системе
print(perevod(a[45], 6))