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

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

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

1. Проверяем, если текущее число s больше целевого fi, то возвращаем 0, так как нельзя получить целевое число, если мы уже его превысили.

2. Если s == fi, значит, мы достигли цели, возвращаем 1 — одна подходящая программа найдена.

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

Далее перебираем все числа начиная с 6 и до 99. Для каждого числа проверяем, если количество программ, получаемое вызовом f(5, i), равно 34, выводим это число и завершаем поиск, так как найдено первое подходящее число.

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

# Перебираем все числа от 6 до 99
for i in range(6, 100):
    # Если количество программ равно 34, выводим число и прекращаем поиск
    if f(5, i) == 34:
        print(i)
        break

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

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

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

2. Задаём исходное условие: a[5] = 1, так как из числа 5 в 5 можно получить число одной программой длины 0.

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

- Количество программ, которые приводят к числу i, равно сумме программ, приводящих к числам i-2 и i-5, так как можно к ним прибавить соответствующую команду.

- То есть a[i] = a[i-2] + a[i-5].

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

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

# Перебираем числа от 6 до 100
for i in range(6, 101):
    # Количество программ для текущего числа равно сумме программ для i-2 и i-5
    a[i] = a[i - 2] + a[i - 5]

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