Задание №5: Анализ алгоритмов для исполнителей
Основные типы и прототипы задания №5:
Двоичные автоматы
Троичные и n-ичные автоматы
Поиск минимального N или R
Условие задания
(Н. Сафронов) Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом:
Укажите максимальное значение N, после обработки которого с помощью этого алгоритма получается число R, меньшее чем 100.
1. Строится троичная запись числа N.
2. К этой записи дописываются разряды по следующему правилу. Если сумма троичных разрядов кратна 3, слева дописывается 20, иначе слева дописывается 10.
3. Полученная таким образом запись является троичной записью искомого числа R.
Например, для числа 10 троичная запись 1013 преобразуется в запись 101013 = 91, для числа 11 троичная запись 1023 преобразуется в 201023 = 173. 2. К этой записи дописываются разряды по следующему правилу. Если сумма троичных разрядов кратна 3, слева дописывается 20, иначе слева дописывается 10.
3. Полученная таким образом запись является троичной записью искомого числа R.
Укажите максимальное значение N, после обработки которого с помощью этого алгоритма получается число R, меньшее чем 100.
Ответ:
18
Шаблон решения на Python
# === Задание 5: Автомат преобразования двоичных чисел ===
for n in range(1, 1000):
b = bin(n)[2:]
if b.count('1') % 2 == 0:
b = b + '0'
b = '10' + b[2:]
else:
b = b + '1'
b = '11' + b[2:]
r = int(b, 2)
if r > 40:
print(f"Ответ: N={n}, R={r}")
break