У исполнителя Кузнечик две команды Прибавь 3 Вычти 2. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 68 команд? Программа решения задачи на языке Python

Задача. У исполнителя Кузнечик две команды:

1. Прибавь 3
2. Вычти 2

Программа для Кузнечика – это последовательность команд. Первая из них увеличивает число на экране на 3, вторая – уменьшает его на 2 (отрицательные числа допускаются). Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 68 команд?

Как будем решать задачу

Создадим пользовательскую функцию f(x, k), которая будет получать следующее число (+3 или -2) и уменьшать количество команд.

Пример:

Вызов f(x+3, k-1) будет получать число за счет команды x+3, количество команд уменьшится на 1. Возникнет рекурсия. Функция будет вызывать саму себя. Чтобы остановить вызовы функций воспользуемся условием k == 0, то есть команд для выполнения не осталось, в этом случае выведем число x.

if k == 0:

    print(x)

else:

    f(x+3, k-1)

    f(x-2, k-1)

Для вызова функции в основной программе запишем f(1, 68), это будет означать исходное число 1, количество выполняемых команд 68.

Если вызовем функцию f(1, 2), получим числа за 2 команды (как на рисунке выше).

def f(x,k):

    if k==0:

        print(x,end = ' ')

    else:

        f(x+3,k-1)

        f(x-2,k-1)

f(1,2)

Вывод: 7 2 2 -3

Чтобы сохранить различные числа воспользуемся множеством m. В качестве ответа выведем длину множества len(m).

def f(x,k):

    if k==0:

        m.add(x)

        print(x,end = ' ')

    else:

        f(x+3,k-1)

        f(x-2,k-1)

m = set()

f(1,2)

print('Длина множества ',len(m))

Вывод: 7 2 2 -3 Длина множества 3

Но для f(1,68) программа работает очень долго, происходит много вызовов функции (причем с одними и теми же аргументами), чтобы сократить время, воспользуемся кэшированием.

Модуль functools включает набор функций высокого уровня, взаимодействующих с другими функциями или возвращающие другие функции.

Декоратор @lru_cache() модуля functools оборачивает функцию с переданными в нее аргументами и запоминает возвращаемый результат, соответствующий этим аргументам. Такое поведение может сэкономить время и ресурсы, когда "дорогая" или связанная с вводом/выводом функция периодически вызывается с одинаковыми аргументами.

Аргумент maxsize позволяет сохранить результаты последних вызовов @lru_cache(maxsize = 128).

Программа решения на языке Python

from functools import *

@lru_cache(maxsize = 64)

def f(x,k):

    if k==0:

        m.add(x)

        #print(x,end = ' ')

    else:

        f(x+3,k-1)

        f(x-2,k-1)

m = set()

f(1,68)

print(len(m))

Ответ: 69

Для эксперимента можно изменять значение аргумента maxsize и замечать время выполнения программы.