ЕГЭ по информатике 2021 - Задание 5 (Алгоритмы, Автоматы)

Привет! Сегодня исследуем интересное 5 задание из ЕГЭ по информатике нового формата 2021.

Пятое задание ЕГЭ по информатике в основном связано с алгоритмами и автоматами.

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

1. Строится двоичная запись числа N.

2. К этой записи дописываются справа ещё два разряда по следующему правилу:

а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 10000 преобразуется в запись 100001;
б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр на 2.

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




Решение:

У нас на вход поступает натуральное (обычное, не дробное, положительное) число N.

Рассмотрим первое правило формирование выходного числа. На выходе получается двоичная запись числа N. Нарисуем схематично первое правило формирования выходного числа.

Рассмотрим теперь второе правило формирования числа. Сказано, что дописываются два разряда справа к тому двоичному числу, которое получили в первом пункте.

Про первый дополнительный разряд написано в пункте a второго правила: "складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 10000 преобразуется в запись 100001".

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

Про второй дополнительный разряд сказано в пункте б второго правила. Автомат сделает тоже самое, что и в предыдущем пункте, только теперь подсчёт единиц будет происходить не только в двоичной записи числа N, но и в первом дополнительном разряде.

В вопросе просят указать входящее наименьшее число N, чтобы автомат выдал число R больше 97.

Т.к. число R должно быть больше 97, то переведём число 98 (97 + 1) в двоичный вид, чтобы можно было оценить входящее число N.

Получилось число 1100010. Будем рассматривать (начиная с 1100010) числа на выполнение правил, которые заданы для автомата. Если все правила будут выполнены, значит, мы получили то число, по которому вычислим изначальное N. Нам нужно получить именно минимальное число, поэтому мы и начали с минимального возможного претендента для числа R (98).

Видим, что подходит число 1100110. В части числа, которая является двоичным представлением N, количество единиц равно 3. Число 3 нечётное, значит, в первом дополнительном разряде должна стоять 1 (единица).

Проверим второй дополнительный разряд. Теперь считаем единицы не только в двоичном представлении числа N, но так же и в первом дополнительном разряде! Количество единиц равно 4. Число 4 чётное. Значит, во втором дополнительном разряде должен стоять 0 (ноль). Все правила работы автомата выполняются в числе 1100110.

Чтобы найти искомое число N, отбросим два дополнительных разряда от найденного 1100110.

Правило: Если от двоичного числа отбросить младший разряд, то оно разделится на 2 целочисленным образом (т.е. делим на 2, если есть остаток, убираем его).

Найдём полученное минимальное число R 1100110 в десятичном представлении. Число 1100010 - 98, 1100011 - 99, 1100100 - 100, 1100101 - 101, 1100110 - 102.

Уберём второй дополнительный разряд у числа 1100110, получается 102 / 2 = 51 (110011). Уберём ещё и первый дополнительный разряд , получается 51 / 2 = 25 (11001).

Значит двоичное представление искомого числа N равно 11001, а десятичное 25.

Ответ: 25.

Изучим ещё одну классическую задачу задания 5 из ЕГЭ по информатике.

Задача (классическая, Автомат)
Автомат получает на вход пятизначное число. По этому числу строится новое число по следующим правилам.
1. Складываются отдельно первая, третья и пятая цифры, а также вторая и четвёртая цифры.
2. Полученные два числа записываются друг за другом в порядке неубывания без разделителей.
Пример. Исходное число: 63 179. Суммы: 6 + 1 + 9 = 16; 3 + 7 = 10. Результат: 1016.
Укажите наименьшее число, при обработке которого автомат выдаёт результат 723.

Решение:

В подобных задачах из ЕГЭ по информатике нумерация происходит начиная со старшего разряда.

Составим краткую запись для первого правила:

Второе правило заключается в том, что мы "соединяем" два числа, полученных в первом пункте, причём, сначала идёт меньшее число, а затем большее.

Рассмотрим число 723.

Разбить на числа 72 и 3 нельзя, т.к. вначале пишется меньшее число. Значит, разбиваем на 7 и 23.

Первое число (сумма 1, 3, 5 разрядов) будет 23, т.к. только сумма трёх цифр может дать число 23. Сумма двух цифр максимум может быть 9+9=18. Тогда 7 - это второе число (сумма 2 и 4 разряда.)

Нам нужно указать наименьшее пятизначное входящее число, поэтому стремимся более старшие разряды сделать как можно меньше! Пусть самый старший разряд (1 разряд) равен 1 (минимальное значение для старшего разряда). Тогда нужно с помощью суммы 3-его и 5-ого разряда набрать 22. Но это не возможно, т.к. максимум с двух разрядов получается 9+9=18. Поэтому приходим к выводу, что самое маленькое значение для 1-ого разряда будет 23-18=5, а третий и пятый разряд будут по 9.

Т.к. 7 - это сумма второго и четвёртого разряда, то сделаем второй разряд 0(нулём), а четвёртый 7, чтобы пятизначное число было минимальным.

Получаем окончательный результат 50979.

Ответ: 50979

Следующая задача иногда встречается в тренировочных вариантах ЕГЭ по информатике.

Задача (Кузнечик)
Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 0. Система команд Кузнечика:
Вперед 7 – Кузнечик прыгает вперёд на 7 единиц,
Назад 5 – Кузнечик прыгает назад на 5 единиц.
Какое наименьшее количество раз должна встретиться в программе команда «Назад 5», чтобы Кузнечик оказался в точке 19?

Решение:

В данной задаче у нас есть числовая ось на которой живёт кузнечик.

Кузнечик может прыгать либо на 7 шагов вперёд, либо на 5 шагов назад. На другое количество шагов Кузнечик прыгать не может!

Обозначим за x - количество прыжков на 7 шагов вперёд, а за y - количество прыжков на 5 шагов назад. x и у - должны быть целые неотрицательные числа.

Составим уравнение:

7x - 5y = 19

Если бы Кузнечик начинал не с нулевой отметки, мы бы прибавили начальную координату к левой части уравнения.

Перегруппируем:

7x - 19 = 5y

Выражение в правой части 5y - делиться на 5, значит и 7x - 19 должно делиться на 5. Чтобы выражение в левой части делилось на 5, нужно чтобы 7x оканчивалось либо на 4, либо на 9 (Тогда и выражение 7x - 19 будет оканчиваться либо на 5, либо на 0).

Вспомним таблицу умножения:

Нам не подходит 14, т.к. 14-19 < 0. А вот 49 - будет минимальное число, которое удовлетворяет нашему условию.

Тогда

5y = 49 - 19 = 30.
y = 6
Ответ: 6.

Задача из ЕГЭ по информатике на побитовый сдвиг:

Задача(редкая, сдвиг влево)
У исполнителя, который работает с положительными однобайтовыми двоичными числами, две команды, которым присвоены номера:
1. сдвинь влево
2. вычти 1
Выполняя первую из них, исполнитель сдвигает число на один двоичный разряд влево, причём на место освободившегося бита ставится 0. Выполняя вторую команду исполнитель вычитает из числа 1. Исполнитель начал вычисления с числа 91 и выполнил цепочку команд 112112. Запишите результат в десятичной системе.

Решение:

Здесь есть всего две команды у исполнителя: сдвинуть биты влево и вычесть 1.

Правило: Если к двоичному числу приписать справа ноль, то это число увеличится в два раза.

Сдвиг влево: Возьмём число 150 (1001 0110). После сдвига влево к двоичному числу приписывается справа ноль (т.е. число умножается на 2) 300(1 0010 1100), а левый бит, если общее количество битов больше 8, отбрасывается (т.к. у нас однобайтовое число). Получается 44 (0010 1100) - нули в начале числа тоже отбрасываются. А 44 - остаток от деления 300/256

В нашей задаче число однобайтовое, значит число не превышает 255. Если при умножении на 2, получаем число большее, чем 255, то мы должны взять остаток от деления на 256

осталось проделать цепочку команд 112112.

91 * 2 = 182 (182 < 255)
182 * 2 = 364 (364 / 256 - остаток 108)
108 - 1 = 107
107 * 2 = 214 (214 < 255)
214 * 2 = 428 (428 / 256 - остаток 172)
172 - 1 = 171

Если была бы команда сдвиг вправо, то тогда у числа просто убирался бы правый бит (т.е. происходило бы целочисленное деление на 2)

Ответ: 171

В задании 5 ЕГЭ по информатике может встретится задача на исполнителя чертёжника.

Задача (Исполнитель Чертежник)
Исполнитель Чертежник имеет перо, которое можно поднимать, опускать и перемещать. При перемещении опущенного пера за ним остается след в виде прямой линии. У исполнителя существуют следующие команды:
Сместиться на вектор (а, Ь) – исполнитель перемещается в точку, в которую можно попасть из данной, пройдя а единиц по горизонтали и b – по вертикали.
Запись: Повторить 5[ Команда 1 Команда 2] означает, что последовательность команд в квадратных скобках повторяется 5 раз.

Чертежник находится в начале координат. Чертежнику дан для исполнения следующий алгоритм:
Сместиться на вектор (5,2)
Сместиться на вектор (-3, 3)
Повторить 3[Сместиться на вектор (1,0)]
Сместиться на вектор (3, 1)
На каком расстоянии от начала координат будет находиться исполнитель Чертежник в результате выполнения данного алгоритма?

Решение:

После первой команды Сместиться на вектор (5,2) Исполнитель чертёжник окажется:

После второй команды Сместиться на вектор (-3, 3)

Следующая команда Повторить 3[Сместиться на вектор (1,0)]

Следующая команда Сместиться на вектор (3, 1)

Расстояние от начала координат находит по теореме Пифагора:

6² + 8² = 100

Значит, расстояние равно 10.

Ответ: 10.

Последняя задача довольно часто печатается в тренировочных заданиях по ЕГЭ по информатике.

Задача (Исполнитель)
У исполнителя УТРОИТЕЛЬ две команды, которым присвоены номера:
1. вычти 1
2. умножь на 3
Первая из них уменьшает число на экране на 1, вторая – увеличивает его в три раза.
Запишите порядок команд в программе получения из числа 3 числа 16, содержащей не более 5 команд, указывая лишь номера команд.

(Например, программа 21211 это программа

умножь на 3
вычти 1
умножь на 3
вычти 1
вычти 1

которая преобразует число 1 в 4.)

Решение:

У нас есть две команды: вычитание 1 и умножить число на 3. Другие действия мы производить не можем!

Нужно получить из 3 -> 16.

В похожих задачах ЕГЭ по информатике лучше всего начать с конца. Шестнадцать умножением на 3 мы никак не получим. Значит, последний командой будет вычитание. Семнадцать (16 + 1) тоже умножением на 3 не получить. Значит, предпоследней командой тоже будет вычитание. Восемнадцать (17 + 1), скорее всего получили умножением на 3! Шесть (18 / 3), получили умножением 2 на 3. Два - это 3 - 1.

Таким образом, получается цепочка команд 1 -> 2 -> 2 -> 1 -> 1

Ответ: 12211