На вход алгоритму подаётся натуральное число N (N > 20).
Алгоритм строит по нему новое число R:
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается так:
а) если число чётное, к двоичной записи справа дописывается 0, а первые две цифры двоичной записи заменяются на 11;
б) если число нечётное, складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа).
Таким образом получается двоичная запись искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 21 результатом является число 43, а для числа 22 — число 60.
Найдите наименьшее число N, после обработки которого с помощью этого алгоритма получается число R больше 200.
В ответе укажите это число в десятичной системе счисления.
Решение
🔹 Шаг 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 = '11' + R[2:] + '0'
print(N, '→', R, '(на 11 + 0)')
else:
R = '11' + R[2:] + '1'
print(N, '→', R, '(на 11 + 1)')
📌 Результат: 1 → 111 (на 11 + 1), 2 → 111 (на 11 + 1), 3 → 110 (на 11 + 0), 19 → 110111 (на 11 + 1) и т.д.
🔹 Шаг 4. Перевод обратно в десятичное число
# перевод обратно в десятичное число
for N in range(1, 20):
R = f'{N:b}'
if R.count('1') % 2 == 0:
R = '11' + R[2:] + '0'
else:
R = '11' + R[2:] + '1'
print(N, '→', R, '→', int(R, 2))
📌 Результат: 1 → 111 → 7, 2 → 111 → 7, 3 → 110 → 6, 19 → 110111 → 55 и т.д.
🔹 Шаг 5. Поиск первого N, при котором R > 200
Цель: собрать всё вместе и понять задачу целиком.
for N in range(21, 10000):
R = f'{N:b}'
if N % 2 == 0:
R = '11' + R[2:] + '0'
else:
R = R + str(sum(int(c) for c in R) % 2)
R = int(R, 2)
if R > 200:
print(N)
break
📌 Результат: минимальное значение N, при котором R > 200. Ответ: 70.
