Задание №5: Анализ алгоритмов для исполнителей
Основные типы и прототипы задания №5:
Двоичные автоматы
Троичные и n-ичные автоматы
Поиск минимального N или R
Условие задания
(Е. Джобс) Автомат обрабатывает десятичное натуральное число N по следующему алгоритму:
1) Строится двоичная запись числа N.
2) К полученному числу справа дописывается 0, если в числе единиц больше, чем нулей; иначе дописывается 1.
3) Из середины двоичного числа убирается 2 разряда, если количество разрядов получилось четным, и 3 разряда, если нечетное.
4) Результат переводится в десятичную систему.
Пример. Дано число N = 11. Алгоритм работает следующим образом.2) К полученному числу справа дописывается 0, если в числе единиц больше, чем нулей; иначе дописывается 1.
3) Из середины двоичного числа убирается 2 разряда, если количество разрядов получилось четным, и 3 разряда, если нечетное.
4) Результат переводится в десятичную систему.
1) Двоичная запись числа N: 11 = 10112
2) Единиц больше, чем нулей, новая запись 101102.
3) Длина начётная, удаляем три средних разряда, новая запись 102.
4) Десятичное значение полученного числа 2.
Каково должно быть исходное число, чтобы в результате его обработки автомат получил значение 55?
2) Единиц больше, чем нулей, новая запись 101102.
3) Длина начётная, удаляем три средних разряда, новая запись 102.
4) Десятичное значение полученного числа 2.
Ответ:
195
Шаблон решения на 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