(А.Богданов) На вход алгоритма подаётся натуральное число N.
Алгоритм строит по нему новое число R следующим образом:
1. Строится троичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N чётное, тогда в конец дописывается два младших разряда полученной троичной записи,
б) если число N нечётное, тогда в конец дописывается троичное представление суммы цифр полученной троичной записи.
Полученная таким образом запись является троичной записью искомого числа R.
Например, для исходного числа 1010 = 1013 результатом является число 101013 = 9110, а для числа 1110 = 1023 результатом является число 102103 = 10210.
Укажите N, большее 9, после обработки которого с помощью этого алгоритма получается минимальное число R.
В ответе запишите это число в десятичной системе счисления.
Решение
🔹 Шаг 1. Перебор чисел и троичная запись
# перебор чисел и троичная запись
def f3(x):
s = ''
while x:
x, ost = divmod(x, 3)
s += str(ost)
return s[::-1]
for N in range(1, 20):
R = f3(N)
print(N, '→', R)
📌 Результат: 1 → 1, 2 → 2, 3 → 10, 19 → 201 и т.д.
🔹 Шаг 2. Проверка чётности N
# проверка чётности N
def f3(x):
s = ''
while x:
x, ost = divmod(x, 3)
s += str(ost)
return s[::-1]
for N in range(1, 20):
R = f3(N)
if N % 2 == 0:
print(N, R, 'чётное')
else:
print(N, R, 'нечётное')
📌 Результат: 1 1 нечётное, 2 2 чётное, 3 10 нечётное, 19 201 нечётное и т.д.
🔹 Шаг 3. Изменение троичной строки
# изменение троичной строки
def f3(x):
s = ''
while x:
x, ost = divmod(x, 3)
s += str(ost)
return s[::-1]
for N in range(1, 20):
R = f3(N)
if N % 2 == 0:
R = R + R[-2:]
print(N, '→', R, '(приписали два младших разряда)')
else:
s = sum(int(c) for c in R)
R = R + f3(s)
print(N, '→', R, f'(приписали троичную запись суммы {s})')
📌 Результат: 1 → 11 (приписали троичную запись суммы 1), 2 → 22 (приписали два младших разряда), 3 → 101 (приписали троичную запись суммы 1), 19 → 20110 (приписали троичную запись суммы 3) и т.д.
🔹 Шаг 4. Перевод обратно в десятичное число
# перевод обратно в десятичное число
def f3(x):
s = ''
while x:
x, ost = divmod(x, 3)
s += str(ost)
return s[::-1]
for N in range(1, 20):
R = f3(N)
if N % 2 == 0:
R = R + R[-2:]
else:
R = R + f3(sum(int(c) for c in R))
print(N, '→', R, '→', int(R, 3))
📌 Результат: 1 → 11 → 4, 2 → 22 → 8, 3 → 101 → 10, 19 → 20110 → 174 и т.д.
🔹 Шаг 5. Поиск N при минимальном R (N > 9)
Цель: собрать всё вместе и понять задачу целиком.
def f3(x):
s = ''
while x:
x, ost = divmod(x, 3)
s += str(ost)
return s[::-1]
best_R = 10 ** 9
best_N = 0
for N in range(10, 10000):
R = f3(N)
if N % 2 == 0:
R = R + R[-2:]
else:
R = R + f3(sum(int(c) for c in R))
R = int(R, 3)
if R < best_R:
best_R = R
best_N = N
print(best_N)
📌 Результат: минимальное N больше 9, при котором R минимально. Ответ: 27.
