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

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

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

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

2. Если x равно y, возвращаем 1, что обозначает найденную подходящую программу.

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

Для нахождения числа, для которого количество программ равно 1001, мы перебираем целевые значения y начиная с 32 и проверяем результат функции f(31, y). Как только находим y, где функция возвращает 1001, выводим его.

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

# Перебираем возможные целевые числа, начиная с 32
for y in range(32, 70):
    # Если количество программ равно 1001, выводим результат
    if f(31, y) == 1001:
        print(y)

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

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

1. Инициализируем массив нулями и задаем a[31] = 1, так как есть ровно один способ быть в начальном числе.

2. Перебираем все числа от 32 до верхней границы (100) и заполняем массив:

- Для каждого числа i считаем сумму значений a[i-2], a[i-4] и a[i-5], что соответствует прибавлению 2, 4 и 5 соответственно.

3. Если значение a[i] становится равным 1001, выводим это число и прекращаем вычисления, так как цель достигнута.

# Массив для хранения количества программ
a = [0] * 100
# Начальное число 31
a[31] = 1

# Перебираем все числа от 32 до 100
for i in range(32, 100 + 1):
    # Количество программ для i = сумма программ для i-2, i-4 и i-5
    a[i] = a[i-2] + a[i-4] + a[i-5]
    # Если нашли число с 1001 программой, выводим его
    if a[i] == 1001:
        print(i)
        break