Задание №5: Анализ алгоритмов для исполнителей
Основные типы и прототипы задания №5:
Двоичные автоматы
Троичные и n-ичные автоматы
Поиск минимального N или R
Условие задания
(Е. Джобс) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:
1. Строится двоичная запись числа N.
2. Если число кратно 5, то слева дописывается 1, справа две последние цифры (младшие разряды). Иначе слева дописывается двоичное представления остатка от деления числа на 5.
3. Полученная таким образом запись является двоичной записью искомого числа R.
Например, для числа 13 = 11012 получается 1111012 = 61, для числа 10 = 10102 получается 11010102 = 106. Укажите максимальное число R, не превышающее 223, которое может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.
2. Если число кратно 5, то слева дописывается 1, справа две последние цифры (младшие разряды). Иначе слева дописывается двоичное представления остатка от деления числа на 5.
3. Полученная таким образом запись является двоичной записью искомого числа R.
Ответ:
219
Шаблон решения на 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