На вход алгоритма подаётся натуральное число N.
Алгоритм строит по нему новое число R следующим образом.
1. Строится троичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры троичной записи, и остаток от деления суммы на 3 дописывается в конец числа (справа). Например, запись 11110 преобразуется в запись 111101;
б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр на 3.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является троичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 1210 = 1103 результатом является число 110213 = 11510, а для исходного числа 1310 = 1113 — число 111003 = 11710.
Укажите такое наименьшее число N, для которого результат работы алгоритма больше числа 540.
В ответе запишите это число в десятичной системе счисления.
Решение
🔹 Шаг 1. Перебор чисел и троичная запись
# перебор чисел и троичная запись
for N in range(1, 20):
R = f3(N)
print(N, '→', R)
📌 Результат: примеры перевода N в троичную запись.
🔹 Шаг 2. Остаток от деления суммы цифр на 3
# остаток от деления суммы цифр на 3
for N in range(1, 20):
R = f3(N)
d = sum(int(c) for c in R) % 3
print(N, R, '→ дописать', d)
📌 Результат: какой бит (0 или 1) дописывается справа по сумме цифр.
🔹 Шаг 3. Дописывание двух разрядов справа
# дописывание двух разрядов справа
for N in range(1, 20):
R = f3(N)
R = R + str(sum(int(c) for c in R) % 3)
R = R + str(sum(int(c) for c in R) % 3)
print(N, '→', R)
📌 Результат: как именно меняется троичная строка по правилу из условия.
🔹 Шаг 4. Перевод обратно в десятичное число
# перевод обратно в десятичное число
for N in range(1, 20):
R = f3(N)
R = R + str(sum(int(c) for c in R) % 3)
R = R + str(sum(int(c) for c in R) % 3)
print(N, '→', R, '→', int(R, 3))
📌 Результат: всю цепочку N → запись → изменённая запись → R.
🔹 Шаг 5. Поиск первого N, при котором R > 540
Цель: собрать всё вместе и понять задачу целиком.
def f3(x):
s = ''
while x:
x, ost = divmod(x, 3)
s += str(ost)
return s[::-1]
for N in range(1, 1000):
R = f3(N)
R = R + str(sum(int(c) for c in R) % 3)
R = R + str(sum(int(c) for c in R) % 3)
R = int(R, 3)
if R > 540:
print(N)
break
📌 Результат: минимальное значение N, при котором R > 540. Ответ: 60.
