(Даня Байт) На вход алгоритма подаётся натуральное число N.
Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N чётное, то к этой записи справа и слева дописываются по две единицы;
б) если число N нечётное, то в конец двоичной записи (справа) дописываются два нуля, а в начало (слева) дописывается единица.
Полученная таким образом запись (в ней на три или четыре разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 1310 = 11012 результатом является число 11101002 = 11610, а для исходного числа 610 = 1102 это число 11110112 = 12310.
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается максимальное число R, не превышающее 1762.
В ответе запишите это число в десятичной системе счисления.
Решение
🔹 Шаг 1. Перебор чисел и двоичная запись
# перебор чисел и двоичная запись
for N in range(1, 20):
R = f'{N:b}'
print(N, '→', R)
📌 Результат: 1 → 1, 2 → 10, 3 → 11, 19 → 10011 и т.д.
🔹 Шаг 2. Проверка чётности N
# проверка чётности N
for N in range(1, 20):
R = f'{N:b}'
if N % 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 N % 2 == 0:
R = '11' + R + '11'
print(N, '→', R, '(11 слева и 11 справа)')
else:
R = '1' + R + '00'
print(N, '→', R, '(1 слева и 00 справа)')
📌 Результат: 1 → 1100 (1 слева и 00 справа), 2 → 111011 (11 слева и 11 справа), 3 → 11100 (1 слева и 00 справа), 19 → 11001100 (1 слева и 00 справа) и т.д.
🔹 Шаг 4. Поиск минимального N при максимальном R ≤ 1762
# поиск минимального N при максимальном R ≤ 1762
best_R = 0
best_N = 0
for N in range(1, 20):
R = f'{N:b}'
if N % 2 == 0:
R = '11' + R + '11'
else:
R = '1' + R + '00'
R = int(R, 2)
if R <= 1762:
if R > best_R:
best_R = R
best_N = N
elif R == best_R:
best_N = min(best_N, N)
print(best_N)
📌 Результат: 18
🔹 Шаг 5. Поиск минимального N при максимальном R ≤ 1762
Цель: собрать всё вместе и понять задачу целиком.
best_R = 0
best_N = 0
for N in range(1, 10000):
R = f'{N:b}'
if N % 2 == 0:
R = '11' + R + '11'
else:
R = '1' + R + '00'
R = int(R, 2)
if R <= 1762:
if R > best_R:
best_R = R
best_N = N
elif R == best_R:
best_N = min(best_N, N)
print(best_N)
📌 Результат: минимальное N, при котором R максимально среди значений не больше 1762. Ответ: 183.
