У исполнителя Щелчок есть куча камней, но он очень одинок, с ним никто не играет в камушки, поэтому он придумал игру для себя сам. У исполнителя есть 3 команды:
1. Прибавить 3 камушка в кучу
2. Умножить количество камушков в куче на 2 и вычесть 1
3. Если количество камней в куче больше 9, то реверсировать количество камней в куче и прибавить 1 (10 
2 , 123 
322)
Программа для исполнителя — это последовательность команд.
Какое минимальное количество команд содержит программа, которая проходит через 8 различных простых чисел. Исполнитель начинает с числа 2 (первое число тоже считается, если оно простое)
Решение 1 (Рекурсия)
def is_prime(n):
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return n > 1
def f(st, count_operation, set_prime):
global count
if count_operation > count:
return # выход из программы без действий
if is_prime(st):
set_prime.add(st)
if len(set_prime) == 8:
count = min(count, count_operation)
return
f(st + 3, count_operation + 1, set_prime.copy())
f(st * 2 - 1, count_operation + 1, set_prime.copy())
if st > 9:
f(int(str(st)[::-1]) + 1, count_operation + 1, set_prime.copy())
count = 10000000000
f(2, 0, set())
print(count)
Решение 2 (Динамика)
def is_prime(n):
if n < 2:
return 0
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return 0
return 1
primes = [0] * 100000
# для начала определим для каждого числа от 1 до 99999
# простое оно, или нет
for i in range(2, 100000):
if is_prime(i):
primes[i] = 1
# далее реализуем динамическое решение задачи
ans = []
ans.append((2, 1))
otv, flag = 100000000, 0
for operations in range(1000):
can_get = []
for i in ans:
a, pr = i
if pr == 8:
otv = operations
flag = 1
break
can_get.append((a + 3, pr + primes[a + 3]))
can_get.append((a * 2 - 1, pr + primes[a * 2 - 1]))
if a > 9:
s = str(a)
s = s[::-1]
new_num = int(s) + 1
can_get.append((new_num, pr + primes[new_num]))
if flag:
break
ans = can_get
print(otv)