Neuronis — ИИ-тренажёр ЕГЭ по информатике

5. Анализ алгоритмов Вариант Апробация 14.05.26

На вход алгоритма подаётся натуральное число N.

Алгоритм строит по нему новое число R следующим образом.

1. Строится троичная запись числа N.

2. Далее эта запись обрабатывается по следующему правилу:

a) если число N делится на 3, то слева к нему приписывается «1», а справа «02»;

б) если число N на 3 не делится, то остаток от деления на 3 умножается на 5, переводится в троичную запись и дописывается в конец числа.

Полученная таким образом запись является троичной записью искомого числа R.

3. Результат переводится в десятичную систему и выводится на экран.

Например, для исходного числа 11₁₀ = 102₃ результатом является число 102101₃ = 307₁₀, а для исходного числа 12₁₀ = 110₃ это число 111002₃ = 353₁₀

Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, не меньшее 177.

Решение

🔹 Шаг 1. Перебор чисел и троичная запись

def f3(x):
    s = ''
    while x:
        x, ost = divmod(x, 3)
        s += str(ost)
    return s[::-1]


for N in range(1, 20):
    s = f3(N)
    print(N, '→', s)

📌 Результат: 1 → 1, 2 → 2, 3 → 10, 19 → 201 и т.д.

🔹 Шаг 2. Проверка делимости на 3

def f3(x):
    s = ''
    while x:
        x, ost = divmod(x, 3)
        s += str(ost)
    return s[::-1]


for N in range(1, 20):
    s = f3(N)
    if N % 3 == 0:
        print(N, s, 'делится на 3')
    else:
        print(N, s, 'НЕ делится на 3')

📌 Результат: 1 1 НЕ делится на 3, 2 2 НЕ делится на 3, 3 10 делится на 3, 19 201 НЕ делится на 3 и т.д.

🔹 Шаг 3. Изменение троичной строки

def f3(x):
    s = ''
    while x:
        x, ost = divmod(x, 3)
        s += str(ost)
    return s[::-1]


for N in range(1, 20):
    s = f3(N)

    if N % 3 == 0:
        s_new = '1' + s + '02'
        print(N, s, '→', s_new, '(приписали 1 слева и 02 справа)')
    else:
        s_new = s + f3(N % 3 * 5)
        print(N, s, '→', s_new, f'(приписали {f3(N % 3 * 5)})')

📌 Результат: 1 1 → 112 (приписали 12), 2 2 → 2101 (приписали 101), 3 10 → 11002 (приписали 1 слева и 02 справа), 19 201 → 20112 (приписали 12) и т.д.

🔹 Шаг 4. Перевод обратно в десятичное число

def f3(x):
    s = ''
    while x:
        x, ost = divmod(x, 3)
        s += str(ost)
    return s[::-1]


for N in range(1, 20):
    s = f3(N)

    if N % 3 == 0:
        s = '1' + s + '02'
    else:
        s = s + f3(N % 3 * 5)

    R = int(s, 3)
    print(N, '→', s, '→', R)

📌 Результат: 1 → 112 → 14, 2 → 2101 → 64, 3 → 11002 → 110, 19 → 20112 → 176 и т.д.

🔹 Шаг 5. Поиск первого N, при котором R ≥ 177

Цель: собрать всё вместе и понять задачу целиком.

def f3(x):
    s = ''
    while x:
        x, ost = divmod(x, 3)
        s += str(ost)
    return s[::-1]


for N in range(1, 100):
    R = f3(N)
    if N % 3 == 0:
        R = '1' + R + '02'
    else:
        R += str(f3(N % 3 * 5))

    if int(R, 3) >= 177:
        print(N)
        break

📌 Результат: минимальное значение N, при котором R ≥ 177. Ответ: 8.

… — Neuronis