Исполнитель Щелчок преобразует число на экране. У исполнителя есть три команды:
1. Вычесть 10
2. Умножить на -2
3. Модуль числа
Программа для исполнителя — это последовательность команд.
Сколько существует различных результатов выполнения программ, содержащих 10 команд и начинающих свою работу из 1. При этом исполнитель не может совершать ходы, которые не изменяют знак числа. Например, из числа 1 нельзя попасть в число 1, но можно в -9 и в -2.
Решение 1 (Рекурсия)
def f(st, count, end_count):
global A
if count == end_count:
A.add(st)
else:
if st > 0:
f(st * (-2), count + 1, end_count)
if st < 10:
f(st - 10, count + 1, end_count)
if st < 0:
f(st * (-1), count + 1, end_count)
f(st * (-2), count + 1, end_count)
A = set() # Лучший вариант для данной задачи,
# в множестве не повторяются элементы
f(1, 0, 10)
print(len(A))
Решение 2 (Динамика)
ans = set()
ans.add(1)
for operations in range(10):
can_get = set()
for i in ans:
if i > 0:
can_get.add(i * (-2))
if i - 10 < 0:
can_get.add(i - 10)
else:
can_get.add(abs(i))
can_get.add(i * (-2))
ans = can_get
print(len(ans))