РЕШУ ЕГЭ — информатика

Задания

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

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

2.  В конец записи (справа) дописывается остаток от деления числа N на 3.

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

Пример. Дано число N  =  11. Алгоритм работает следующим образом.

1.  Троичная запись числа N: 102.

2.  Остаток от деления 11 на 3 равен 2, новая запись: 1022.

3.  На экран выводится число 35.

Какое наименьшее трёхзначное число может появиться на экране в результате работы автомата?

Решение. Рассмотрим числа, большие 99, и определим наименьшее из них, которое может являться результатом работы алгоритма. Заметим, что остаток от деления числа на 3  — это последняя цифра троичной записи числа. В соответствии с заданным алгоритмом эта цифра дописывается справа от записи числа. Таким образом, получающееся в результате работы автомата число должно иметь в троичной записи в конце две одинаковые цифры.

100₁₀  =  10201₃  — не может являться результатом работы алгоритма.

101₁₀  =  10202₃  — не может являться результатом работы алгоритма.

102₁₀  =  10210₃  — не может являться результатом работы алгоритма.

103₁₀  =  10211₃  — может являться результатом работы алгоритма.

Таким образом, ответ  — 103.

Ответ: 103.

Приведём другое решение на языке Python.

for i in range(1, 100):

n = i

s = ""

while n > 0: # перевод в троичную систему

s += str(n % 3)

n //= 3

s = str(i % 3) + s

r = 0

for j in range(len(s)): # перевод в десятичную систему

r += int(s[j]) * 3 ** j

if r > 99:

print(r)

break

Приведём другое решение Овсянникова Павла на языке Python.

for n in range(100):

i = n

s = ''

while i>0:

s+=(str(i%3))

i //= 3

s = s[::-1]

s+=(str(n%3))

s = int(s,3)

if s > 99:

print(s)

break

№ п/п	№ задания	Ответ
1	27375	103

Ключ