(А. Михайлов) На вход алгоритма подаётся натуральное число N.
Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 00;
б) если сумма цифр в двоичной записи числа нечётная, то самый левый разряд заменяется на 11, а в конец записи (справа) дописывается 1.
Полученная таким образом запись является двоичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 410 = 1002 результатом является число 110012 = 2510, а для исходного числа 510 = 1012 результатом является число 101002 = 2010.
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, большее 100.
В ответе запишите это число в десятичной системе счисления.
Решение
🔹 Шаг 1. Перебор чисел и двоичная запись
# перебор чисел и двоичная запись
for N in range(1, 20):
R = f'{N:b}'
print(N, '→', R)
📌 Результат: 1 → 1, 2 → 10, 3 → 11, 19 → 10011 и т.д.
🔹 Шаг 2. Проверка чётности суммы цифр
# проверка чётности суммы цифр
for N in range(1, 20):
R = f'{N:b}'
if R.count('1') % 2 == 0:
print(N, R, 'чётная сумма цифр')
else:
print(N, R, 'нечётная сумма цифр')
📌 Результат: 1 1 нечётная сумма цифр, 2 10 нечётная сумма цифр, 3 11 чётная сумма цифр, 19 10011 нечётная сумма цифр и т.д.
🔹 Шаг 3. Изменение двоичной строки
# изменение двоичной строки
for N in range(1, 20):
R = f'{N:b}'
if R.count('1') % 2 == 0:
R = R + '00'
print(N, '→', R, '(справа 00)')
else:
R = '11' + R[1:] + '1'
print(N, '→', R, '(слева 11, справа 1)')
📌 Результат: 1 → 111 (слева 11, справа 1), 2 → 1101 (слева 11, справа 1), 3 → 1100 (справа 00), 19 → 1100111 (слева 11, справа 1) и т.д.
🔹 Шаг 4. Перевод обратно в десятичное число
# перевод обратно в десятичное число
for N in range(1, 20):
R = f'{N:b}'
if R.count('1') % 2 == 0:
R = R + '00'
else:
R = '11' + R[1:] + '1'
print(N, '→', R, '→', int(R, 2))
📌 Результат: 1 → 111 → 7, 2 → 1101 → 13, 3 → 1100 → 12, 19 → 1100111 → 103 и т.д.
🔹 Шаг 5. Поиск первого N, при котором R > 100
Цель: собрать всё вместе и понять задачу целиком.
for N in range(1, 1000):
R = f'{N:b}'
if R.count('1') % 2 == 0:
R = R + '00'
else:
R = '11' + R[1:] + '1'
R = int(R, 2)
if R > 100:
print(N)
break
📌 Результат: минимальное значение N, при котором R > 100. Ответ: 19.
