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

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

Для нахождения длины самой короткой программы мы используем динамическое программирование. Создаём массив a, где a[i] хранит минимальное количество команд, необходимых для получения числа i из числа 1.

1. Инициализируем массив достаточно большой длины, чтобы покрыть целевое число: a = [0] * 300.

2. Задаём начальные условия: a[1] = 0, так как число 1 — это начальное число, а a[0] = 10**20, чтобы предотвратить использование недостижимых чисел.

3. Перебираем все числа от 2 до 299 включительно. Для каждого числа i делаем следующие шаги:

- Инициализируем три переменные x, y, z большими числами (10**20), чтобы корректно использовать функцию min.

- x = a[i - 1] + 1 — если текущее число получено прибавлением 1, добавляем одну команду к числу команд для i-1.

- Если i >= 5, y = a[i - 5] + 1 — если число получено прибавлением 5.

- Если i % 3 == 0, z = a[i // 3] + 1 — если число делится на 3, получаем его делением на 3 и прибавляем одну команду.

4. Для числа i выбираем минимальное значение из трёх возможных переходов: a[i] = min(x, y, z).

После заполнения массива значение a[227] будет равно длине самой короткой программы для получения числа 227 из числа 1.

# Создаем массив для хранения минимального количества команд
a = [0] * 300
# Число 0 недостижимо
a[0] = 10**20
# Исходное число 1, команд не требуется
a[1] = 0

# Перебираем все числа от 2 до 299
for i in range(2, 300):
    # Инициализируем количество команд для всех трёх возможных переходов большими числами
    x = y = z = 10**20
    # Если число получено прибавлением 1
    x = a[i - 1] + 1
    # Если число получено прибавлением 5
    if i >= 5:
        y = a[i - 5] + 1
    # Если число получено умножением на 3
    if i % 3 == 0:
        z = a[i // 3] + 1
    # Выбираем минимальное количество команд для текущего числа
    a[i] = min(x, y, z)

# Выводим длину самой короткой программы для числа 227
print(a[227])