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

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

Мы используем рекурсивный подход для подсчета количества программ, учитывая ограничение на повторение команд. Для этого мы определяем функцию f(a, b, c1, c2), где:

1. – текущее число на экране;

2. – целевое число, к которому нужно прийти;

3. – количество последовательных применений команды 1 ("увеличь на 1");

4. – количество последовательных применений команды 2 ("умножь на 2").

Алгоритм функции состоит из следующих шагов:

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

2. Проверяем, если равно , то мы достигли цели, возвращаем как количество одного успешного пути.

3. В остальных случаях создаём переменную , которая будет накапливать количество успешных программ.

4. Если команда 1 применялась меньше трёх раз подряд (), то вызываем функцию рекурсивно с аргументами и добавляем результат к . Здесь мы увеличиваем на 1, увеличиваем счётчик , а счётчик обнуляем, так как сменили команду.

5. Если команда 2 применялась меньше трёх раз подряд (), вызываем функцию рекурсивно с аргументами и добавляем результат к . Здесь мы умножаем на 2, обнуляем , а увеличиваем на 1.

6. Возвращаем сумму , которая содержит количество всех программ из текущего состояния.

Вызов функции f(5, 299) даёт искомое количество программ, начинающихся с числа 5 и приводящих к числу 299 с учётом ограничения на повторение команд.

# Определяем функцию f(a, b, c1=0, c2=0), которая считает количество программ
def f(a, b, c1 = 0, c2 = 0):
    # Если текущее число a больше целевого b, путь невозможен, возвращаем 0
    if a > b:
        return 0
    # Если текущее число a равно целевому b, найден один успешный путь, возвращаем 1
    if a == b:
        return 1
    else:
        # Создаём переменную s для накопления количества успешных программ
        s = 0
        # Если команда 1 применялась меньше 3 раз подряд, выполняем её и добавляем результат
        if c1 < 3:
            s += f(a + 1, b, c1 + 1, 0)
        # Если команда 2 применялась меньше 3 раз подряд, выполняем её и добавляем результат
        if c2 < 3:
            s += f(a * 2, b, 0, c2 + 1)
    # Возвращаем общее количество успешных программ из текущего состояния
    return s

# Вызываем функцию с начальным числом 5 и целевым 299 и выводим результат
print(f(5, 299))