23.08 Прочие прототипы

Рекурсивный способ решения

Мы можем использовать рекурсивную функцию f(x, y), которая считает количество программ, преобразующих число x в число y. Логика работы функции следующая:

1. Если текущее число x больше целевого y, возвращаем 0, так как нельзя превысив цель достичь её.

2. Если x == y, возвращаем 1, так как найден один подходящий путь.

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

Далее перебираем все числа от 2 до 99. Для каждого числа y проверяем, если количество программ равно 36, добавляем его в множество a. После перебора выводим минимальное число из множества, что соответствует минимальному направлению.

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

# Создаем множество для хранения чисел, для которых количество программ равно 36
a = set()
# Перебираем числа от 2 до 99
for y in range(2, 100):
    # Если количество программ равно 36, добавляем число в множество
    if f(1, y) == 36:
        a.add(y)

# Выводим минимальное число из множества
print(min(a))

Динамический способ решения

Динамический способ позволяет избежать многократного пересчета одних и тех же значений. Мы создаём массив a, где a[i] хранит количество программ, которые преобразуют число 1 в число i.

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

2. Задаём исходное условие: a[1] = 1, так как из числа 1 в 1 существует один путь.

3. Перебираем все числа i от 1 до 29 включительно. Для каждого числа выполняем следующие шаги:

- К числу i+1 добавляем количество программ из числа i, так как можно прибавить 1.

- Если число i*2 не превышает размер массива, добавляем к нему количество программ из числа i, так как можно применить команду умножения на 2.

4. После заполнения массива ищем индекс числа, где количество программ равно 36 с помощью a.index(36), и выводим его.

# Создаем массив для хранения количества программ
a = [0] * 100
# Исходное число 1, одна программа длины 0
a[1] = 1

# Перебираем числа от 1 до 29
for i in range(1, 30):
    # Прибавляем к следующему числу количество программ текущего числа
    a[i + 1] += a[i]
    # Умножаем текущее число на 2 и добавляем количество программ
    a[i * 2] += a[i]

# Находим минимальное число, для которого количество программ равно 36
print(a.index(36))