Исполнитель Сотка преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1.
2. Отнять 2.
3. Умножить на 3.
Первая команда увеличивает число на 1, вторая уменьшает число на 2, третья – умножает на 3. Сколько различных результатов можно получить из исходного числа 2 после выполнения программы, содержащей 20 команд, если известно, что запрещено повторять команду, сделанную на предыдущем шаге.
Программное решение:
from functools import lru_cache
@lru_cache(None)
def f(a, k, last = 0): #Ввёдем в функцию 2 параметра: ’k’ и ’last’. Параметр ’k’ является счётчиком команд.
# Параметр ’last’ записывает последнюю выполненную команду для того чтобы две одинаковые команды не совершались друг за другом
if k == 20:
s.add(a)
if k < 20: # Пока количество команд меньше 20, мы изменяем число
if last == 0:
f(a+1, k+1, 1)
f(a-2, k+1, 2)
f(a*3, k+1, 3)
if last == 1:
f(a-2, k+1, 2)
f(a*3, k+1, 3)
if last == 2:
f(a+1, k+1, 1)
f(a*3, k+1, 3)
if last == 3:
f(a+1, k+1, 1)
f(a-2, k+1, 2)
s = set()
f(2, 0) #Вызываем функцию
print(len(s)) #Выводим количество различных результатов программы
Ответ: 35093