23.08 Прочие прототипы

Решение рекурсией

Идея рекурсивного решения заключается в том, что мы создаем функцию f(st, count_operation, set_prime), которая перебирает все возможные программы от текущего состояния st, учитывая количество использованных команд count_operation и множество простых чисел set_prime, через которые уже прошли.

1. Сначала определяем вспомогательную функцию is_prime(n), которая проверяет, является ли число простым.

- Проходим по всем числам от 2 до квадратного корня из включительно.

- Если делится на любое из этих чисел, возвращаем False.

- Иначе возвращаем True, если .

2. В функции f проверяем ограничения:

- Если count_operation больше текущего минимального найденного количества команд count, выходим из функции, так как дальнейшие действия не улучшат результат.

- Если текущее число st простое, добавляем его в множество set_prime.

- Если длина множества простых чисел равна 8, обновляем глобальное минимальное количество команд count и возвращаемся.

3. Рекурсивно вызываем функцию для каждого возможного перехода:

- st + 3 (команда 1) с увеличением count_operation на 1.

- st * 2 - 1 (команда 2) с увеличением count_operation на 1.

- Если st > 9, выполняем реверс числа, прибавляем 1 (команда 3) и вызываем функцию рекурсивно.

4. Инициализируем глобальную переменную count большим числом, запускаем рекурсию с st = 2, count_operation = 0, set() и выводим count в конце.

# Функция проверки простого числа
def is_prime(n):
    # Проходим по всем числам от 2 до квадратного корня из n включительно
    for i in range(2, int(n ** 0.5) + 1):
        # Если n делится на i, то число не простое
        if n % i == 0:
            return False
    # Если делителей нет и n>1, число простое
    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)
    # Если в множестве уже 8 простых чисел, обновляем минимальное количество команд
    if len(set_prime) == 8:
        count = min(count, count_operation)
        return
    # Пробуем первый вариант команды: прибавить 3
    f(st + 3, count_operation + 1, set_prime.copy())
    # Пробуем второй вариант команды: умножить на 2 и вычесть 1
    f(st * 2 - 1, count_operation + 1, set_prime.copy())
    # Пробуем третий вариант команды: реверс + 1, только если st > 9
    if st > 9:
        f(int(str(st)[::-1]) + 1, count_operation + 1, set_prime.copy())

# Инициализируем минимальное количество команд большим числом
count = 10000000000
# Запускаем рекурсию с начальным числом 2, 0 команд, пустое множество простых чисел
f(2, 0, set())
# Выводим минимальное количество команд
print(count)

—

Решение динамикой

Идея динамического решения заключается в том, что мы храним список состояний, где каждый элемент — это кортеж (a, pr), где a — текущее количество камней, pr — количество уникальных простых чисел, через которые прошли.

1. Сначала создаем массив primes длиной 100000, где каждый элемент указывает, простое число или нет.

- Проходим по всем числам от 2 до 99999, проверяем простоту через функцию is_prime, заполняем массив единицами для простых чисел.

2. Инициализируем список ans с начальным состоянием (2,1), так как стартовое число 2 простое.

3. Для каждого количества операций (от 0 до 1000) строим новый список can_get:

- Для каждого состояния (a, pr) проверяем, если уже достигли 8 простых чисел, сохраняем текущий номер операций как ответ и завершаем цикл.

- Иначе добавляем все возможные новые состояния:

      - a + 3, pr + primes[a + 3]       - a * 2 - 1, pr + primes[a * 2 - 1]       - Если a > 9, выполняем реверс и +1, добавляем new_num, pr + primes[new_num]

4. После перебора всех операций выводим минимальное количество команд.

# Функция проверки простого числа
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

# Массив для отметки простых чисел от 0 до 99999
primes = [0] * 100000
# Заполняем массив единицами для простых чисел
for i in range(2, 100000):
    if is_prime(i):
        primes[i] = 1

# Начальное состояние: число 2, уже одно простое число
ans = []
ans.append((2, 1))
otv, flag = 100000000, 0

# Перебираем количество операций до 1000
for operations in range(1000):
    can_get = []
    # Проходим по всем состояниям на текущем шаге
    for i in ans:
        a, pr = i
        # Если уже достигли 8 простых чисел, сохраняем результат
        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)