Разбор номера 5589 ЕГЭ по информатике #5

Условие: № 5589 (Уровень: Средний)

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:

а) если количество разрядов в числе чётное, тогда в центр записи числа дописывается 111.
б) если количество разрядов в числе нечётное, тогда к этой записи справа дописывается 1, а затем два левых разряда заменяются на 11.

Полученная таким образом запись является двоичной записью искомого числа R.
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, большее 4000. В ответе запишите это  число в десятичной системе счисления.

for n in range(1, 1000):
s = bin(n)[2:]
if len(s) % 2 == 0:
s = s[:len(s)//2] + '111' + s[len(s)//2:]
else:
s = '11' + s[2:] + '1'
r = int(s, 2)
if r > 4000:
print(n)
break

Комментарии к решению задачи:

1. for n in range(1, 1000): - Мы создаем цикл for, который перебирает все значения от 1 до 999 (не включая 1000), хранящиеся в переменной n (можно смело брать больший диапазон, никто не гарантирует, что результат найдется быстро).
2. s = bin(n)[2:] - Присваиваем переменной s бинарное представление значения переменной n, которое мы получаем с помощью функции bin(). Мы также обрезаем первые два символа, так как они представляют префикс 0b, который используется в Python для обозначения бинарных чисел (числа двоичной системы счисления).
3. if len(s) % 2 == 0: - Проверяем условие на чётное количество разрядов len(s) в числе с помощью оператора %.
4. s = s[:len(s)//2] + '111' + s[len(s)//2:] - Если длина строки s четная, мы вставляем три символа 111 в середине строки s.
5. else: - Если длина строки s нечетная, то
6. s = '11' + s[2:] + '1' - Добавляем два символа 11 в начало и конец строки s.
7. r = int(s, 2) - Преобразуем измененную строку s обратно в целое число, используя функцию int(). Второй аргумент этой функции - 2 - указывает, что строка s интерпретируется как бинарное число.
8. if r > 4000: - Если значение r больше 4000, то
9. print(n) - Мы выводим значение переменной n с помощью функции print().
10. break - И выходим из цикла for с помощью оператора break. Если же мы не нашли значение n, для которого r было бы больше 4000, то имеет смысл увеличить диапазон for n in range(1, 1000) или проверить алгоритм на наличие ошибок.

Еще один вариант решения задачи, - через списки. Будем считать его более универсальным, так как сюда можно подставить любую систему счисления, не только 2-ную.

for n in range(1, 1000):
x = n
M = []
while x > 0:
M.append(x % 2)
x //= 2
M.reverse()

if len(M) % 2 == 0:
M = M[:len(M)//2] + [1, 1, 1] + M[len(M)//2:]
else:
M = [1, 1] + M[2:] + [1]

r = 0
M.reverse()
for i in range(0, len(M)):
r += M[i] * 2 ** i

if r > 4000:
print(n)
break

Комментарии к решению задачи:

1. for n in range(1, 1000): - Мы создаем цикл for, который перебирает все значения от 1 до 999 (не включая 1000), хранящиеся в переменной n.
2. x = n - Создаем переменную x, которой мы присваиваем значение переменной n (дабы сохранить значения переменной n).
3. M = [] - Создаем пустой список M для хранения остатков от деления на 2
4. while x > 0: - Используем цикл while, чтобы перевести значение переменной x в бинарное представление.
5. M.append(x % 2) - Добавляем каждый остаток от деления на 2 в список M.
6. x //= 2 - Делим значение переменной x на 2 и перезаписываем это значение в переменную x (иначе цикл получится бесконечным).
7. M.reverse() - Обязательно разворачиваем список M, чтобы правильно сопоставить значениям по алгоритму.
8. if len(M) % 2 == 0: - Проверяем, является ли длина списка M четной с помощью оператора %.
9. M = M[:len(M)//2] + [1, 1, 1] + M[len(M)//2:] - Если это так, мы добавляем три символа 1 в середину списка M.
10. else: - Если длина списка M нечетная, то
11. M = [1, 1] + M[2:] + [1] - Мы добавляем два символа 1 в начало и конец списка M.
12. r = 0 - Создаем переменную r, которой мы присваиваем значение 0 (сюда будем считать десятичную запись числа).
13. M.reverse() - Разворачиваем список M, чтобы индексы списка сопоставились с порядковыми номерами из алгоритма перевода.
14. for i in range(0, len(M)): - Используем цикл for, чтобы перебрать каждый элемент списка M.
15. r += M[i] * 2 ** i - Мы добавляем к изначение, равное квадрату 2, возведенному в степень i, умноженное на значение элемента списка M на позиции i (четко действуем по алгоритму).
16. if r > 4000: - Если значение r больше 4000, то
17. print(n) - Мы выводим значение переменной n.
18. break - Прерываем цикл, так как по условию нужно наименьшее число.

Ответ: 512

Информатика ЕГЭ | itpy 👨‍💻

Присоединяйтесь и готовьтесь вместе с нами: https://t.me/+SIliQTddHE8xNTk6