Задание 5. Информатика. ЕГЭ. Шастин. 18.10.2024
- Просмотры: 266
- Изменено: 24 ноября 2024
(Д. Бахтиев) На вход алгоритма подаётся натуральное число \(N\). Алгоритм строит по нему новое число \(R\) следующим образом.
- Строится троичная запись числа \(N\).
- Далее эта запись обрабатывается по следующему правилу:
- если количество цифр двоичной записи числа чётное, то к этой записи справа дописывается \(1\);
- если количество цифр двоичной записи нечётное, то к этой записи слева дописывается \(1\), а справа \(0\);
- Полученная таким образом запись является двоичной записью искомого числа \(R\).
- Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа \(3 = 11_2\) результатом является число \(111_2 = 7\).
Укажите минимальное число \(R\), большее \(666\), которое могло получиться в результате работы данного алгоритма.
В ответе запишите это число в десятичной системе счисления.
Решение:
Решение через строки.
Python
def R2(n):
bn = bin(n)[2:]
if len(bn) % 2:
ans = '1' + bn + '0'
else:
ans = bn + '1'
return int(ans, 2)
ans = []
for n in range(4, 1000):
x = R2(n)
if x > 666:
ans.append(x)
print(min(ans))
Решение через побитовые операции
Python
def q_dig(n):
q = 0
while n:
q += 1
n >>= 1
return q
def R(n):
nums = q_dig(n)
if nums % 2:
return (1 << (nums + 1)) + (n << 1)
else:
return (n << 1) + 1
ans = []
for n in range(4, 1000):
x = R(n)
if x > 666:
ans.append(x)
print(min(ans))
Ответ: \(1025\)