(Э. Носиров) На вход алгоритма подаётся натуральное число N.
Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Полученная запись обрабатывается по правилу:
а) если N делится на 3, справа дописываются две последние цифры двоичной записи N;
б) если N не делится на 3, справа дописывается двоичная запись числа, равного утроенному остатку от деления N на 3.
3. Полученная запись является двоичной записью числа R.
Значение R переводится в десятичную систему счисления.
Например, для N = 610 = 1102 результатом является число 110102 = 2610, а для N = 510 = 1012 — число 1011102 = 4610.
Укажите наименьшее число R, превышающее 240, которое может быть результатом работы алгоритма.
Ответ запишите в десятичной системе счисления.
Решение
🔹 Шаг 1. Перебор чисел и двоичная запись
# перебор чисел и двоичная запись
for N in range(1, 20):
R = f'{N:b}'
print(N, '→', R)
📌 Результат: 1 → 1, 2 → 10, 3 → 11, 19 → 10011 и т.д.
🔹 Шаг 2. Проверка делимости на 3
# проверка делимости на 3
for N in range(1, 20):
R = f'{N:b}'
if N % 3 == 0:
print(N, R, 'делится на 3')
else:
print(N, R, 'НЕ делится на 3')
📌 Результат: 1 1 НЕ делится на 3, 2 10 НЕ делится на 3, 3 11 делится на 3, 19 10011 НЕ делится на 3 и т.д.
🔹 Шаг 3. Изменение двоичной строки
# изменение двоичной строки
for N in range(1, 20):
R = f'{N:b}'
if N % 3 == 0:
R = R + R[-2:]
print(N, '→', R, '(приписали последние 2 бита)')
else:
r = (N % 3) * 3
R = R + f'{r:b}'
print(N, '→', R, f'(приписали {r:b})')
📌 Результат: 1 → 111 (приписали 11), 2 → 10110 (приписали 110), 3 → 1111 (приписали последние 2 бита), 19 → 1001111 (приписали 11) и т.д.
🔹 Шаг 4. Перевод обратно в десятичное число
# перевод обратно в десятичное число
for N in range(1, 20):
R = f'{N:b}'
if N % 3 == 0:
R = R + R[-2:]
else:
r = (N % 3) * 3
R = R + f'{r:b}'
print(N, '→', R, '→', int(R, 2))
📌 Результат: 1 → 111 → 7, 2 → 10110 → 22, 3 → 1111 → 15, 19 → 1001111 → 79 и т.д.
🔹 Шаг 5. Поиск минимального R, превышающего 240
Цель: собрать всё вместе и понять задачу целиком.
MIN_R = 10 ** 9
for N in range(1, 10000, 1):
R = f'{N:b}'
if N % 3 == 0:
R = R + R[-2:]
else:
r = (N % 3) * 3
R = R + f'{r:b}'
R = int(R, 2)
if R > 240:
MIN_R = min(R, MIN_R)
print(MIN_R)
📌 Результат: минимальное значение R, превышающее 240 (через MIN_R). Ответ: 247.
