На вход алгоритма подаётся натуральное число N.
Алгоритм строит по нему новое число R следующим образом.
- Строится двоичная запись числа N.
- К этой записи дописываются справа ещё два разряда по следующему правилу:
- а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
- б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
- Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 1210 = 11002 результат является число 1100002 = 4810, а для исходного числа 710 = 1112 — число 111102 = 3010.
Укажите такое наименьшее число N, для которого результат работы алгоритма больше числа 253.
В ответе запишите это число в десятичной системе счисления.
Решение
🔹 Шаг 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. Перевод обратно в десятичное число
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'
print(N, '→', R, '→', int(R, 2))
📌 Результат: 1 → 111 → 7, 2 → 111 → 7, 3 → 100 → 4, 19 → 110111 → 55 и т.д.
🔹 Шаг 5. Сборка полной программы и получение ответа
Цель: собрать всё вместе и понять задачу целиком.
for N in range(1, 1000):
R = f'{N:b}'
R = R + str(R.count('1') % 2)
R = R + str(R.count('1') % 2)
R = int(R, 2)
if R > 253:
print(N)
break
📌 Результат: итоговый ответ программы. Ответ: 64.
