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