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