На вход алгоритма подаётся натуральное число N.
Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 4, то к этой записи слева дописываются три последние двоичные цифры;
б) если число N на 4 не делится, то остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа.
Полученная таким образом запись является двоичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 1210 = 11002 результатом является число 10011002 = 7610, а для исходного числа 610 = 1102 — число 1101102 = 5410.
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, не меньшее 328.
В ответе запишите это число в десятичной системе счисления.
Решение
🔹 Шаг 1. Перебор чисел и двоичная запись
# перебор чисел и двоичная запись
for N in range(1, 20):
R = f'{N:b}'
print(N, '→', R)
📌 Результат: 1 → 1, 2 → 10, 3 → 11, 19 → 10011 и т.д.
🔹 Шаг 2. Проверка делимости на 4
# проверка делимости на 4
for N in range(1, 20):
R = f'{N:b}'
if N % 4 == 0:
print(N, R, 'делится на 4')
else:
print(N, R, 'НЕ делится на 4')
📌 Результат: 1 1 НЕ делится на 4, 2 10 НЕ делится на 4, 3 11 НЕ делится на 4, 19 10011 НЕ делится на 4 и т.д.
🔹 Шаг 3. Изменение двоичной строки
# изменение двоичной строки
for N in range(1, 20):
R = f'{N:b}'
if N % 4 == 0:
R = R[-3:] + R
print(N, '→', R, '(слева приписали последние 3 бита)')
else:
r = (N % 4) * 3
R = R + f'{r:b}'
print(N, '→', R, f'(справа приписали {r:b})')
📌 Результат: 1 → 111 (справа приписали 11), 2 → 10110 (справа приписали 110), 3 → 111001 (справа приписали 1001), 19 → 100111001 (справа приписали 1001) и т.д.
🔹 Шаг 4. Перевод обратно в десятичное число
# перевод обратно в десятичное число
for N in range(1, 20):
R = f'{N:b}'
if N % 4 == 0:
R = R[-3:] + R
else:
r = (N % 4) * 3
R = R + f'{r:b}'
print(N, '→', R, '→', int(R, 2))
📌 Результат: 1 → 111 → 7, 2 → 10110 → 22, 3 → 111001 → 57, 19 → 100111001 → 313 и т.д.
🔹 Шаг 5. Поиск первого N, при котором R ≥ 328
Цель: собрать всё вместе и понять задачу целиком.
for N in range(1, 1000):
R = f'{N:b}'
if N % 4 == 0:
R = R[-3:] + R
else:
r = (N % 4) * 3
R = R + f'{r:b}'
R = int(R, 2)
if R >= 328:
print(N)
break
📌 Результат: минимальное значение N, при котором R ≥ 328. Ответ: 23.
