Задание № 5 ЕГЭ по информатике проверяет умение работать с алгоритмами для формальных исполнителей. Чаще всего в нём встречаются задачи с двоичной или троичной записью числа. Разберём типовые приёмы (перевод, подсчёт единиц, дописывание битов) и решим пять задач из открытого банка ФИПИ на Python. После статьи ты сможешь быстро и без ошибок находить нужные значения N или R.

Термины, которые будем использовать: алгоритм, исполнитель. [i]

Общая структура задания

Условие обычно описывает некий автомат, который:

Берёт натуральное число N.
Выполняет с его двоичной (реже — десятичной) записью некоторые действия (дописывает цифры, заменяет, удаляет, суммирует и т. д.).
Получает новое число R.
Требуется найти:
1. минимальное/максимальное N или R, удовлетворяющее условию;
2. количество таких чисел на отрезке;
3. наименьшее/наибольшее R в диапазоне и т. п.

Основные приёмы

Ниже приведены приёмы, наиболее часто встречающиеся при решении задачи № 5:

Двоичная запись числа (без ‘0b’)
n2 = bin(N)[2:]
Перевод из двоичной в десятичную
R = int(n2, 2)
Количество единиц в двоичной записи
ones = bin(n2).count(‘1’)
Проверка на чётность
if n % 2 == 0:
<…>
else:
<…>
Дописывание битов справа
R = n2 + ’11’
Дописывание битов слева
R = ’10’ + n2
Сумма десятичных цифр
digit_sum = sum(map(int, str(N)))
Сумма двоичных цифр (то же, что пункт 3)
binary_sum = bin(n2).count(‘1’)
Перебор для поиска максимального/минимального N
res = 0
for N in range(1, 10000):
if <…>:
res = N
break # для минимального
Подсчёт чисел на отрезке [a, b], дающих нужное R
count = sum(1 for N in range(a, b+1) if условие)
Проверка на палиндром (строка)
is_palindrome = str(N) == str(N)[::-1]
Битовая инверсия (0 заменяются на 1, 1 на 0)
n2 = n2.replace(‘1’, ‘*’).replace(‘0’, ‘1’).replace(‘*’, ‘0’)

Подготовка к экзаменам в 100балльном репетиторе

Практикум: решение задач

Задача 1

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:
Строится двоичная запись числа N.
Далее эта запись обрабатывается по следующему правилу:
а) если сумма цифр двоичной записи числа чётная, то первые две цифры заменяются на 10, а в конец добавляется 0;
б) если сумма цифр двоичной записи числа нечётная, то первые две цифры заменяются на 11, и в конце добавляется единица.
Полученная таким образом запись является двоичной записью искомого числа R.
Укажите максимальное число N, после обработки которого с помощью этого алгоритма получается число R, не большее 42. В ответе запишите это число в десятичной системе счисления. [i]

for n in range(1, 1001): # перебираем числа в диапазоне от 1 до 1000

s = bin(n)[2:] # переводим в 2 СС

if sum(int(i) for i in s) % 2 == 0: # проверяем условие, что сумма цифр двоичной записи числа чётная

s = ’10’ + s[2:] + ‘0’ # дописываем либо «10» слева и «0» справа

else:

s = ’11’ + s[2:] + ‘1’ # иначе дописываем либо «11» слева и «1» справа

r = int(s, 2) # переводим полученное число в 10 СС

if r <= 42: # проверяем условие и выводим ответ

print(n)

Ответ: 29.

Задача 2

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:
Строится двоичная запись числа N.
К этой записи дописываются справа ещё два разряда по следующему правилу: складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001; над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число, большее, чем 137. В ответе это число запишите в десятичной системе. [i]

Будем перебирать какие-то n с помощью цикла for. После чего, как нас и просят по условию, переводим число в двоичную систему счисления с помощью функции bin(), не забыв отрезать два первых знака (которые не влияют на наше число, это просто показатель системы счисления). Дальше проверяем, если количество единиц чётно, то к полученному числу n2 приписываем в конец 0, иначе 1. Делаем это дважды. Чтобы перевести в 10сс, воспользуемся функцией int().

Программа

for n in range(1, 1000):

n2 = bin(n)[2:] # переводим в 2 СС

if n2.count(‘1’) % 2 == 0: # дописываем либо 0, либо 1 в конец в первый раз

n2 += ‘0’

else:

n2 += ‘1’

if n2.count(‘1’) % 2 == 0: # дописываем либо 0, либо 1 в конец во второй раз

n2 += ‘0’

else:

n2 += ‘1’

r = int(n2, 2) # переводим полученное число в 10 СС

if r > 137:

print(n) # выводим именно число n, как это требует условие

break

Ответ: 35.

Задача 3

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:
Строится двоичная запись числа N.
К этой записи дописывается (дублируется) последняя цифра.
Затем справа дописывается 0, если в двоичном коде числа N чётное число единиц, и 1, если нечётное.
К полученному результату дописывается ещё один бит чётности так, чтобы количество единиц в двоичной записи полученного числа стало чётным.
Полученная таким образом запись (в ней на три разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число R, большее 80, которое могло получиться в результате работы автомата. В ответе это число запишите в десятичной системе. [i]

Создадим в программе сначала двоичную запись числа N, а после в новой переменной запомним эту запись с дописанной последней цифрой. Мы делаем это для того, чтобы записать в конец 1 или 0, в зависимости от изначального числа n2, а не уже видоизменённого.

Программа

res = []

for n in range(1, 101): # перебираем числа в диапазоне от 1 до 100

n2 = bin(n)[2:] # 1 шаг

n2n = n2 + n2[-1] # 2 шаг, записываем в другую переменную, чтобы запомнить изначальное число в 2 СС

n2n += str(n2.count(‘1’) % 2) # 3 шаг

if n2n.count(‘1’) % 2 == 0: # 4 шаг

n2n += ‘0’

else:

n2n += ‘1’

r = int(n2n, 2) # переводим полученное число в 10 СС

if r > 80:

res.append(r)

print(min(res))

Ответ: 95.

Задача 4

На вход алгоритма подаётся натуральное число N алгоритм строит по нему новое число R следующим образом:
Строится троичная запись числа N.
Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 3, то в конце дописывается к троичной записи две последние троичные цифры;
б) если число N на 3 не делится, то остаток от деления умножается на 5, переводится в троичную запись и дописывается в конце числа. Полученная таким образом запись является троичной записью искомого числа R.
Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа $11 = 102_{3}$ результатом является число $102101_{3} = 307$ , а для исходного числа $12 = 110_{3}$ это число $11010_{3} = 111$ .
Укажите минимальное число R, больше 111, которое может быть получено с помощью описанного алгоритма. В ответе запишите это число в десятичной системе счисления. [i]

Здесь нам впервые встречается не двоичная система счисления. К сожалению, если это не 2сс, 8сс или 16сс, Python не умеет самостоятельно переводить числа в заданные системы счисления, поэтому напишем программу, переводящую число в 3сс, самостоятельно. Она будет возвращать строку, которая является переводом в троичную систему счисления. Вспомним, как мы обычно переводили числа из 10сс в 3сс: мы делили число на три, каждый раз записывая полученный остаток в начало.

Так же сделаем это в программе:

Создаём пустую строку s, в ней ничего нет.
Пока наше число больше нуля, к строке s мы в начало приписываем остаток при делении на три, переведённый в строку с помощью str().
Не забудем уменьшить число n, найдя его целую часть при делении на 3.
Возвращаем полученную строку s.

Программа

def tr(n): # функция, которая переводит число в 3 СС

s = » # создаём пустую строку

while n > 0:

s = str(n % 3) + s # каждый раз в начало созданной строки приписываем найденный остаток

n = n // 3 # продолжаем делить число на 3

return s

res = []

for n in range(4, 201): # перебираем числа в диапазоне от 1 до 200

n3 = tr(n) # 1 шаг

if n % 3 == 0:

n3 += n3[-2:]

else:

ost5 = (n % 3) * 5 # находим число остатка, согласно условию

ost3 = tr(ost5) # переводим его в 3 СС

n3 += ost3

r = int(n3, 3) # переводим полученное число в 10 СС

if r > 111:

res.append(r)

print(min(res))

Ответ: 122.

Задача 5

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:
Строится троичная запись числа N.
Далее эта запись обрабатывается по следующему правилу:
a) если число N делится на 3, то к этой записи справа дописываются две последние троичные цифры;
б) если число N на 3 не делится, то вычисляется количество цифр полученной троичной записи, это количество умножается на 3, переводится в троичную систему счисления и дописывается в конец числа. Полученная таким образом запись является троичной записью искомого числа R.
Результат переводится в десятичную систему и выводится на экран.
Укажите минимальное нечётное число R, большее 190, которое может быть получено с помощью описанного алгоритма. В ответе запишите это число в десятичной системе счисления. [i]

def tr(n): # функция, которая переведёт число в 3сс

s = » # создаём пустую строку

while n > 0:

s = str(n % 3) + s # каждый раз в начало созданной строки приписываем найденный остаток

n = n // 3 # продолжаем делить число на 3

return s

res = []

for n in range(1, 201): # перебираем числа в диапазоне от 1 до 200

n3 = tr(n) # перевод числа в троичную СС

if n % 3 == 0: # проверяем кратность трём

n3 += n3[-2:] # дописываются две последние троичные цифры

else:

k = len(n3) * 3 # находим количество цифр и умножаем на 3

k3 = tr(k) # перевод числа в троичную СС

n3 += k3 # добавляем в конец числа

r = int(n3, 3) # переводим полученное число в 10 СС

if r > 190 and r % 2 != 0: # проверяем условия и добавляем в список

res.append(r)

print(min(res)) # выводим минимальное из подходящих

Заключение

После разбора типовых алгоритмов и их программной реализации можно уверенно сказать: задача № 5 перестаёт быть задачей со звёздочкой. Теперь ты знаешь:

как работать с двоичной и троичной записями чисел в Python;
какие приёмы помогают моделировать действия автомата (дописывание битов, подсчёт единиц, проверку чётности);
как организовать перебор для поиска минимального или максимального результата.

Главное в этой задаче — аккуратно перевести словесное описание алгоритма в код и не забыть про особенности систем счисления. Регулярно решай варианты из нашего банка заданий — и навык будет доведён до автоматизма. Успехов на экзамене!