Задание №5: Анализ алгоритмов для исполнителей
Основные типы и прототипы задания №5:
Двоичные автоматы
Троичные и n-ичные автоматы
Поиск минимального N или R
Условие задания
(Е. Джобс) На вход алгоритма подается натуральное число N > 1. Алгоритм строит по нему новое число R следующим образом.
Например, для исходного числа 4 = 1002 результатом будет являться число 8 = 10002, а для исходного числа 6 = 1102 результатом будет являться число 12 = 11002.
Укажите максимальное число R, меньшее 450, которое может являться результатом работы алгоритма. В ответе запишите это число в десятичной системе счисления.
1. Строится двоичная запись числа N.
2. Из полученной записи убирается старшая (левая) единица.
3. Далее эта запись обрабатывается по следующему правилу:
a) если в полученной записи количество единиц четное, то слева дописывается 10;
b) если количество единиц нечётное, слева дописывается 1, справа 0.
Полученная таким образом запись является двоичной записью искомого числа R.2. Из полученной записи убирается старшая (левая) единица.
3. Далее эта запись обрабатывается по следующему правилу:
a) если в полученной записи количество единиц четное, то слева дописывается 10;
b) если количество единиц нечётное, слева дописывается 1, справа 0.
Например, для исходного числа 4 = 1002 результатом будет являться число 8 = 10002, а для исходного числа 6 = 1102 результатом будет являться число 12 = 11002.
Укажите максимальное число R, меньшее 450, которое может являться результатом работы алгоритма. В ответе запишите это число в десятичной системе счисления.
Ответ:
444
Шаблон решения на 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