На вход алгоритма подаётся натуральное число N.
Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 0, а затем два левых разряда заменяются на 10;
б) если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается 11, а затем два левых разряда заменяются на 11.
Полученная таким образом запись является двоичной записью искомого числа R.
Укажите наибольшее число N, после обработки которого с помощью этого алгоритма получается число R, меньшее 99.
В ответе это число запишите в десятичной системе счисления.
Решение
🔹 Шаг 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 = '10' + R[2:] + '0'
print(N, '→', R, '(на 10 + 0)')
else:
R = '11' + R[2:] + '11'
print(N, '→', R, '(на 11 + 11)')
📌 Результат: 1 → 1111 (на 11 + 11), 2 → 1111 (на 11 + 11), 3 → 100 (на 10 + 0), 19 → 1101111 (на 11 + 11) и т.д.
🔹 Шаг 4. Перевод обратно в десятичное число
# перевод обратно в десятичное число
for N in range(1, 20):
R = f'{N:b}'
if R.count('1') % 2 == 0:
R = '10' + R[2:] + '0'
else:
R = '11' + R[2:] + '11'
print(N, '→', R, '→', int(R, 2))
📌 Результат: 1 → 1111 → 15, 2 → 1111 → 15, 3 → 100 → 4, 19 → 1101111 → 111 и т.д.
🔹 Шаг 5. Поиск максимального N, при котором R < 99
Цель: собрать всё вместе и понять задачу целиком.
max_n = 0
for N in range(1, 1000):
R = f'{N:b}'
if R.count('1') % 2 == 0:
R = '10' + R[2:] + '0'
else:
R = '11' + R[2:] + '11'
R = int(R, 2)
if R < 99:
max_n = N
print(max_n)
📌 Результат: максимальное значение N, при котором R < 99. Ответ: 63.
