Задача. У исполнителя Кузнечик две команды:
- Прибавь 3
- Вычти 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 и замечать время выполнения программы.
