На вход алгоритма подаётся натуральное число N.
Алгоритм строит по нему новое число R следующим образом.
1. Строится троичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 7, то к этой записи справа дописываются две последние троичные цифры, а слева дописывается 10;
б) если число N на 7 не делится, то вычисляется сумма цифр полученной троичной записи, эта сумма умножается на 3, переводится в троичную систему счисления и дописывается в конец числа.
Полученная таким образом запись является троичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 1010 = 1013 результатом является число 101203 = 9610, а для исходного числа 1410 = 1123 — число 10112123 = 86010.
Укажите минимальное нечётное число R, большее 906, которое может быть получено с помощью описанного алгоритма.
В ответе запишите это число в десятичной системе счисления.
Решение
🔹 Шаг 1. Функция f — троичная запись
# функция f — троичная запись
def f(n):
s = ''
while n:
n, r = divmod(n, 3)
s = str(r) + s
return s
📌 Результат: функция f переводит число в троичную запись.
🔹 Шаг 2. Перебор чисел и троичная запись
# перебор чисел и троичная запись
def f(n):
s = ''
while n:
n, r = divmod(n, 3)
s = str(r) + s
return s
for n in range(1, 20):
R = f(n)
print(n, '→', R)
📌 Результат: 1 → 1, 2 → 2, 3 → 10, 19 → 201 и т.д.
🔹 Шаг 3. Проверка делимости на 7
# проверка делимости на 7
def f(n):
s = ''
while n:
n, r = divmod(n, 3)
s = str(r) + s
return s
for n in range(1, 20):
R = f(n)
if n % 7 == 0:
print(n, R, 'делится на 7')
else:
print(n, R, 'НЕ делится на 7')
📌 Результат: 1 1 НЕ делится на 7, 2 2 НЕ делится на 7, 3 10 НЕ делится на 7, 19 201 НЕ делится на 7 и т.д.
🔹 Шаг 4. Изменение троичной строки
# изменение троичной строки
def f(n):
s = ''
while n:
n, r = divmod(n, 3)
s = str(r) + s
return s
for n in range(1, 20):
R = f(n)
if n % 7 == 0:
R = '10' + R + R[-2:]
print(n, '→', R, '(слева 10 и последние 2 цифры)')
else:
R = R + f(3 * sum(map(int, R)))
print(n, '→', R, f'(приписали {f(3 * sum(map(int, R)))})')
📌 Результат: 1 → 110 (приписали 20), 2 → 220 (приписали 110), 3 → 1010 (приписали 20), 19 → 201100 (приписали 110) и т.д.
🔹 Шаг 5. Поиск минимального нечётного R больше 906
Цель: собрать всё вместе и понять задачу целиком.
def f(n):
s = ''
while n:
n, r = divmod(n, 3)
s = str(r) + s
return s
ans = 100000
for n in range(1, 10000):
R = f(n)
if n % 7 == 0:
R = '10' + R + R[-2:]
else:
R += f(3 * sum(map(int, R)))
r = int(R, 3)
if r > 906 and r % 2 == 1:
ans = min(ans, r)
print(ans)
📌 Результат: минимальное нечётное R, большее 906. Ответ: 921.
