Исполнитель Щелчок преобразует число на экране. У исполнителя есть четыре команды:
1. Прибавить 1
2. Умножить на 2 и прибавить 1
3. Умножить на 2 и вычесть 1
4. Умножить на 4 и прибавить 1
Программа для исполнителя — это последовательность команд.
Исполнитель хочет выяснить какое минимальное количество простых чисел он может посетить при перемещении из числа 10 в число 300.
Решение 1 (Рекурсия)
def is_prime(n):
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return n != 1
from functools import lru_cache
@lru_cache(None)
def f(st, fn, primes):
global count
if is_prime(st):
primes += 1
if st == fn:
if primes < count:
count = primes
return
if st > fn:
return
f(st + 1, fn, primes)
f(st * 2 + 1, fn, primes)
f(st * 2 - 1, fn, primes)
f(st * 4 + 1, fn, primes)
count = 100000000000
f(10, 300, 0)
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
a, primes = [10000000] * 301, [0] * 301
a[10] = 0
# для начала определим для каждого числа от 1 до 300
# простое оно, или нет
for i in range(2, 301):
if is_prime(i):
primes[i] = 1
# далее реализуем динамическое решение задачи
for i in range(10, 300):
a[i + 1] = min(a[i + 1], a[i] + primes[i + 1])
if i * 2 + 1 < 301:
a[i * 2 + 1] = min(a[i * 2 + 1], a[i] + primes[i * 2 + 1])
if i * 2 - 1 < 301:
a[i * 2 - 1] = min(a[i * 2 - 1], a[i] + primes[i * 2 - 1])
if i * 4 + 1 < 301:
a[i * 4 + 1] = min(a[i * 4 + 1], a[i] + primes[i * 4 + 1])
print(a[300])