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

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

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

1. Если s > fi, возвращаем 0, так как количество задач превысило цель.

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

3. Если s нечетное, можем выполнить только команду «прибавь 1» и вызываем рекурсию: f(s + 1, fi).

4. Если s четное, суммируем два возможных действия:

- f(s + 1, fi) — прибавление 1 задачи;

- f(s * 1.5, fi) — увеличение количества задач в 1.5 раза.

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

# Выводим количество способов, чтобы дойти от 1 до 20
print(f(1, 20))

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

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

1. Инициализируем a[1] = 1.

2. Для чисел от до :

- прибавляем a[i - 1] для команды «прибавь 1»;

- прибавляем a[i - i // 3] для команды «умножь на 1.5», только если делится на (так как , значит делится на 3).

После заполнения массива значение a[20] покажет количество всех последовательностей действий.

# Создаем массив для динамического программирования
a = [0] * 21
# Начальная точка (1 решенная задача) имеет один способ
a[1] = 1
# Заполняем массив для чисел от 2 до 20
for i in range(2, 21):
    # Количество способов через команду +1
    a[i] = a[i - 1]
    # Добавляем путь через команду *1.5, если текущее число делится на 3
    if i % 3 == 0:
        a[i] += a[i - i // 3]
# Выводим количество способов для числа 20
print(a[20])