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

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

Мы используем рекурсивный подход, который позволяет проверить все возможные последовательности команд от числа 10 до числа 300 и определить минимальное количество посещённых простых чисел.

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

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

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

- Если делителей не найдено и , возвращаем True.

2. Далее определяем рекурсивную функцию f(st, fn, primes) с кэшированием lru_cache, чтобы избежать повторных вычислений для одинаковых аргументов.

- st — текущее число,

- fn — конечное число,

- primes — количество посещённых простых чисел на текущем пути.

3. В теле функции проверяем:

- Если текущее число st простое, увеличиваем счётчик primes на 1.

- Если st == fn, значит мы достигли конечного числа:

      - Если текущее значение primes меньше глобального минимального count, обновляем count.

      - Возвращаемся из функции, так как дальнейшие шаги не нужны.

- Если st > fn, дальнейшие шаги не ведут к цели, возвращаемся.

4. В противном случае рекурсивно вызываем функцию для всех четырёх команд:

- st + 1 — прибавить 1

- st * 2 + 1 — умножить на 2 и прибавить 1

- st * 2 - 1 — умножить на 2 и вычесть 1

- st * 4 + 1 — умножить на 4 и прибавить 1

5. После запуска рекурсии с начального числа 10 и конечного 300, глобальная переменная count будет содержать минимальное количество посещённых простых чисел.

# Функция проверки простого числа
def is_prime(n):
    # Перебираем все числа от 2 до квадратного корня из n
    for i in range(2, int(n ** 0.5) + 1):
        # Если делится на i, число не простое
        if n % i == 0:
            return False
    # Число простое, если оно не 1
    return n != 1

# Подключаем кэширование для рекурсивной функции
from functools import lru_cache

@lru_cache(None)
def f(st, fn, primes):
    # Если текущее число простое, увеличиваем счетчик 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 очень большим числом
count = 100000000000
# Запускаем рекурсию от числа 10 до 300
f(10, 300, 0)
                                                                                                     
                                                                                                     
# Выводим минимальное количество посещенных простых чисел
print(count)

—

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

Мы применяем динамическое программирование, чтобы последовательно вычислить минимальное количество посещённых простых чисел для каждого числа от 10 до 300, используя известные результаты для меньших чисел.

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

- Если , возвращаем 0 (не простое).

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

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

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

2. Создаём два массива длиной 301:

- a[i] — минимальное количество простых чисел, которое можно посетить, чтобы добраться до числа .

- primes[i] — является ли число простым (1 — простое, 0 — нет).

3. Инициализируем:

- Все значения a[i] большим числом, кроме стартового числа 10, для которого a[10] = 0.

- Для каждого числа от 2 до 300 проверяем простоту и заполняем массив primes[i].

4. Для каждого числа от 10 до 299 обновляем минимальное количество посещённых простых чисел для всех чисел, до которых можно попасть командой:

-

- , если меньше 301

- , если меньше 301

- , если меньше 301

При этом к значению a[i] добавляется primes[target], чтобы учесть, посещено ли новое число простым.

5. После прохода по всем числам a[300] содержит минимальное количество посещённых простых чисел для пути от 10 до 300.

# Функция проверки простого числа
def is_prime(n):
    # Если число меньше 2, не простое
    if n < 2:
        return 0
    # Перебираем числа от 2 до квадратного корня из n
    for i in range(2, int(n ** 0.5) + 1):
        # Если делится на i, число не простое
        if n % i == 0:
            return 0
    # Число простое
    return 1

# Инициализация массивов
a, primes = [10000000] * 301, [0] * 301
# Стартовое число 10 имеет 0 посещенных простых чисел
a[10] = 0

# Заполняем массив простых чисел
for i in range(2, 301):
    if is_prime(i):
        primes[i] = 1

# Динамическое вычисление минимального количества простых чисел
for i in range(10, 300):
    # Переход командой +1
    a[i + 1] = min(a[i + 1], a[i] + primes[i + 1])
    # Переход командой *2 + 1
    if i * 2 + 1 < 301:
        a[i * 2 + 1] = min(a[i * 2 + 1], a[i] + primes[i * 2 + 1])
    # Переход командой *2 - 1
    if i * 2 - 1 < 301:
        a[i * 2 - 1] = min(a[i * 2 - 1], a[i] + primes[i * 2 - 1])
    # Переход командой *4 + 1
    if i * 4 + 1 < 301:
        a[i * 4 + 1] = min(a[i * 4 + 1], a[i] + primes[i * 4 + 1])

# Выводим минимальное количество посещенных простых чисел при достижении 300
                                                                                                     
                                                                                                     
print(a[300])