Задание №5: Анализ алгоритмов для исполнителей
Основные типы и прототипы задания №5:
Двоичные автоматы
Троичные и n-ичные автоматы
Поиск минимального N или R
Условие задания
(Е. Джобс) На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом.
Пример. Дано число N = 13. Алгоритм работает следующим образом:
1. Строится двоичная запись числа N.
2. Складываются все цифры полученной двоичной записи. Если сумма получилась нечетной, справа к двоичной записи дописываются две единицы, иначе две единицы дописываются слева.
Полученная таким образом запись является двоичной записью искомого числа R.2. Складываются все цифры полученной двоичной записи. Если сумма получилась нечетной, справа к двоичной записи дописываются две единицы, иначе две единицы дописываются слева.
Пример. Дано число N = 13. Алгоритм работает следующим образом:
1. Двоичная запись числа N: 13 = 1101.
2. Сумма цифр двоичной записи 3, число нечетное. Значит получается число 110111.
3. 1101112 = 5510.
Найдите наименьшее число N, для которого результат работы автомата больше, чем 102.
2. Сумма цифр двоичной записи 3, число нечетное. Значит получается число 110111.
3. 1101112 = 5510.
Ответ:
17
Шаблон решения на 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