(В.Лашин) На вход алгоритма подаётся натуральное число N.
Алгоритм строит по нему новое число R следующим образом.
1. Строится троичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если сумма цифр троичной записи числа кратна 9, то к этой записи справа дописывается 2
б) если сумма цифр троичной записи числа не кратна 9, то к этой записи справа дописывается троичная запись остатка от деления суммы цифр записи на 9;
Полученная таким образом запись является троичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 9 = 1003 результатом является число 10013 = 28.
А для исходного числа 161 = 122223 результатом является число 1222223 = 485
Укажите минимальное число R, которое может быть результатом работы данного алгоритма, при условии, что N больше 166.
В ответе запишите это число в десятичной системе счисления.
Решение
🔹 Шаг 1. Функция 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. Проверка кратности суммы цифр на 9
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)
x = sum(map(int, R))
if x % 9 == 0:
print(n, R, f'сумма цифр {x} кратна 9')
else:
print(n, R, f'сумма цифр {x} не кратна 9')
📌 Результат: 1 1 сумма цифр 1 не кратна 9, 2 2 сумма цифр 2 не кратна 9, 3 10 сумма цифр 1 не кратна 9, 19 201 сумма цифр 3 не кратна 9 и т.д.
🔹 Шаг 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)
x = sum(map(int, R))
if x % 9 == 0:
R += '2'
print(n, '→', R, '(дописали 2)')
else:
R += f(x % 9)
print(n, '→', R, f'(дописали {f(x % 9)})')
📌 Результат: 1 → 11 (дописали 1), 2 → 22 (дописали 2), 3 → 101 (дописали 1), 19 → 20110 (дописали 10) и т.д.
🔹 Шаг 5. Поиск минимального R при N > 166
Цель: собрать всё вместе и понять задачу целиком.
def f(n):
s = ''
while n:
n, r = divmod(n, 3)
s = str(r) + s
return s
ans = 100000
for n in range(167, 10000):
R = f(n)
x = sum(map(int, R))
if x % 9 == 0:
R += '2'
else:
R += f(x % 9)
ans = min(ans, int(R, 3))
print(ans)
📌 Результат: минимальное значение R при условии N > 166. Ответ: 647.
