На вход алгоритма подаётся натуральное число N.
Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 3, то к этой записи дописываются её три последние двоичные цифры;
б) если число N на 3 не делится, то остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа.
Полученная таким образом запись является двоичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 1210 = 11002 результатом является число 11001002 = 10010, а для исходного числа 410 = 1002 это число 100112 = 1910.
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, не меньшее 200
Решение
🔹 Шаг 1. Перебор чисел и двоичная запись
for N in range(1, 20):
s = f'{N:b}'
print(N, '→', s)
📌 Результат: 1 → 1, 2 → 10, 3 → 11, 19 → 10011 и т.д.
🔹 Шаг 2. Проверка делимости на 3
for N in range(1, 20):
s = f'{N:b}'
if N % 3 == 0:
print(N, s, 'делится на 3')
else:
print(N, s, 'НЕ делится на 3')
📌 Результат: 1 1 НЕ делится на 3, 2 10 НЕ делится на 3, 3 11 делится на 3, 19 10011 НЕ делится на 3 и т.д.
🔹 Шаг 3. Изменение двоичной строки
for N in range(1, 20):
s = f'{N:b}'
if N % 3 == 0:
s_new = s + s[-3:]
print(N, s, '→', s_new, '(приписали последние 3 бита)')
else:
r = (N % 3) * 3
s_new = s + f'{r:b}'
print(N, s, '→', s_new, f'(приписали {r:b})')
📌 Результат: 1 1 → 111 (приписали 11), 2 10 → 10110 (приписали 110), 3 11 → 1111 (приписали последние 3 бита), 19 10011 → 1001111 (приписали 11) и т.д.
🔹 Шаг 4. Перевод обратно в десятичное число
for N in range(1, 20):
s = f'{N:b}'
if N % 3 == 0:
s = s + s[-3:]
else:
r = (N % 3) * 3
s = s + f'{r:b}'
R = int(s, 2)
print(N, '→', s, '→', R)
📌 Результат: 1 → 111 → 7, 2 → 10110 → 22, 3 → 1111 → 15, 19 → 1001111 → 79 и т.д.
🔹 Шаг 5. Поиск первого N, при котором R ≥ 200
Цель: собрать всё вместе и понять задачу целиком.
for N in range(1, 1000):
s = f'{N:b}'
if N % 3 == 0:
s = s + s[-3:]
else:
r = (N % 3) * 3
s = s + bin(r)[2:]
R = int(s, 2)
if R >= 200:
print(N)
break
📌 Результат: минимальное значение N, при котором R ≥ 200. Ответ: 26.