Задание 5 ЕГЭ по информатике: алгоритм исполнителя

Правила выданы в условии словами: взять число, записать его в двоичной системе, приписать справа или слева определённые цифры в зависимости от чётности или от остатка, прочитать получившуюся запись как новое число. «Исполнителем» условие называет того, кто всё это делает, и никакой фигуры на экране нет, есть только строка из нулей и единиц, которую меняют по правилам. В прежних вариантах встречался и другой исполнитель, вычислитель с набором команд вроде «прибавь» и «умножь», и подход к нему похож: сначала понять, что происходит с числом за один шаг, а потом искать нужное.

Вопрос чаще всего обратный. Не «что получится из этого числа», а «из какого наименьшего числа получится результат больше такого-то». Прямой ход выполнить легко, а искать исходное число приходится обходным путём, и именно здесь решается, сколько вы потратите времени. Общее место этого задания среди других описано в статье первая часть ЕГЭ по информатике: карта заданий. Для самой темы пригодится статья про системы счисления, и в структуре экзамена есть общая картина.

Условие: что в нём важно прочесть до конца

Четыре места условия определяют решение, и все хочется пропустить. Первое: что именно искать, исходное число или результат. Второе: наименьшее или наибольшее. Третье: строгое ли неравенство, то есть «больше» или «не меньше». Четвёртое: в каком виде вводить ответ, в десятичной записи или в двоичной. Ошибка в любом из четырёх даёт ответ, который проходит все ваши проверки и всё равно неверен, потому что вы ответили на другой вопрос.

Дальше идёт описание правил, и к нему применимо одно требование: прочитайте его так, как будто вы его выполняете на бумаге. Что значит «дописать слева»? Куда именно встаёт новая цифра? Что такое «бит чётности»? Если для вас эти слова неочевидны, выполните правило на одном небольшом числе, прежде чем думать о чём-либо ещё. Кто пропускает это место, потом долго ищет ошибку в расчётах, которые не сходятся, хотя неверным было само понимание правила.

Разбор с придуманным правилом

Правило придумал я сам, оно не из варианта: форма та же, содержание свободное. Алгоритм получает число N, строит его двоичную запись и дважды подряд дописывает справа бит чётности. Бит чётности равен нулю, если в записи чётное число единиц, и единице, если нечётное. Полученная запись читается как двоичное число R.

Проведём алгоритм на числе пять. Двоичная запись — 101. Единиц две, это чётное число, значит, пишем справа нуль и получаем 1010. Единиц по-прежнему две, снова нуль: 10100. Это двадцать. Теперь число семь: 111, единиц три, нечётное число, пишем единицу и получаем 1111, где единиц уже четыре, чётное число, поэтому дописываем нуль: 11110. Это тридцать.

Видна закономерность, которая и делает задачу проще: каждое применение алгоритма увеличивает запись на две цифры, то есть умножает число приблизительно на четыре. Если N даёт чётное число единиц, то R равно ровно четырём N. Если нечётное, то R равно четырём N плюс два.

Теперь обратный вопрос: какое наименьшее N даёт R больше сорока? Раз R примерно в четыре раза больше N, начинать надо около десяти. Десять — это 1010, две единицы, R равно сорока, а сорок не больше сорока. Одиннадцать — это 1011, три единицы, R равно сорока шести, что больше сорока. Проверим меньшие числа: девять даёт тридцать шесть, восемь даёт тридцать четыре. Ответ одиннадцать. Весь поиск занял три шага, потому что мы догадались, где искать.

Во втором разборе правило другое, и результат ведёт себя неровнее. Если N чётное, к его двоичной записи справа дописывается 10. Если нечётное, дописывается единица и слева, и справа. Вопрос: каково наибольшее N, при котором R меньше сорока?

В обоих случаях запись удлиняется ровно на две цифры. Значит, R меньше сорока, то есть меньше шестидесяти четырёх, только если в его записи не больше шести цифр, а у N тогда не больше четырёх, то есть N не превосходит пятнадцати. Дальше смотрим числа с пятнадцати вниз: пятнадцать даёт 63, четырнадцать даёт 58, тринадцать — 59, двенадцать — 50, одиннадцать — 55, десять — 42, девять — 51, восемь — 34. Первое подходящее, считая сверху, это восемь. Обратите внимание: девять даёт 51, а десять только 42, то есть результат с ростом N не растёт ровно. Поэтому останавливаться на первом N, где условие нарушилось, нельзя: дальше могут встретиться подходящие. Рассуждение о длине записи сузило перебор до восьми проверок, а проверка стала полной.

Когда рассуждения хватает, а когда нужна программа

Рассуждением такое задание решается, пока закономерность простая, как в разборе выше. Но правила в вариантах бывают хитрее: условие на чётность разбивается на случаи, цифры дописываются и слева, и справа, и закономерность видна уже не с одного взгляда. Тогда лучше написать программу.

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

Прежде чем запускать перебор, проверьте функцию на двух-трёх числах, результат которых вы уже получили руками. Если в условии приведён пример выполнения алгоритма, он служит готовым тестом: подставьте его число в функцию и сверьте. Эта проверка стоит меньше минуты, а ошибка в самой функции, оставшаяся незамеченной, исказит весь перебор и никак себя не покажет: программа честно выдаст число, только не то. Так же полезно напечатать результаты для первых десяти значений N и пробежать их глазами: скачки и странности видны сразу, и закономерность, о которой шла речь выше, проверяется заодно.

Есть одна подсказка по записи на Python: функция bin возвращает строку с приставкой в начале, и приставку нужно отрезать срезом, иначе она окажется среди цифр. Обратный перевод из двоичной записи в число делается встроенной функцией преобразования строки с указанием основания два. Но это дело языка, а не задания, и каждый язык делает это по-своему. Проверьте свой способ дома на трёх-четырёх числах, чтобы не отлаживать его в зале.

Мой выбор такой: сначала руками на двух-трёх числах, чтобы убедиться, что правило понято верно, и сразу после этого программа. По-моему, тот, кто решает такое задание целиком руками, тратит время, которое можно потратить на задания, где программа не поможет. Хотя оговорка нужна: если правило простое и вы видите ответ в два шага, программа лишняя.

Где путаются

Первая группа ошибок связана с двоичной записью. Приписать цифру слева и приписать справа — разные действия: справа цифра сдвигает все прежние на разряд и сама становится младшей, а слева становится старшей и не меняет остальные. Кто не уверен, пусть выпишет число в двоичной записи и дорисует цифру руками, не делая этого в уме.

Вторая группа связана с границами. Условия «больше сорока» и «не меньше сорока» дают разные ответы ровно в одной точке. В нашем разборе это десятка: она даёт сорок, и вопрос решается одним словом в условии.

Третья — с границами перебора. Цикл от единицы вверх годится для поиска наименьшего. Для наибольшего нужно сначала понять, где перебор можно закончить, и чаще всего ломается именно это: цикл останавливают слишком рано или, наоборот, гоняют до такого числа, что проверка занимает вечность.

Четвёртая — перенос ответа: программа печатает число, а в поле ввода его набирают руками. Одна переставленная цифра обнуляет задание. Копируйте вывод программы, если среда позволяет.

Проверка у задания есть, и она дешёвая: найденное N подставьте в правило руками и убедитесь, что результат удовлетворяет условию, а соседнее число, которое должно не подойти, действительно не подходит. Две проверки, две минуты. Если сходится, вводите ответ.

Откуда тема и что делать, если не идёт

Двоичная запись и перевод между системами проходятся в основной школе, а закрепляются в старших классах отдельными задачами. К одиннадцатому классу перевод помнят как процедуру, но привычки думать о числе как о записи цифр часто нет. Подробнее о том, что и когда проходится по курсу, есть в статье информатика в школе.

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

В паре с этим заданием идут базы данных и исполнитель Черепаха: у всех трёх общее то, что условие нужно перевести в последовательность простых действий, прежде чем искать ответ.

Где найти разбор с репетитором

Платформа не записывает занятия и не показывает экран, поэтому свою программу и вывод присылайте в чат (он открывается после того, как репетитор получил ваш контакт), а на занятии разбирайте вместе, где закралась ошибка.

Начать поиск:

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

Вопросы и ответы

Что делать, если в правиле написан остаток от деления? Переведите его на язык двоичной записи, это почти всегда упрощает дело. Остаток от деления на два равен последней цифре записи, остаток от деления на четыре — двум последним цифрам, остаток от деления на восемь — трём последним. Поэтому условие «если остаток от деления на четыре равен единице» означает, что запись заканчивается на 01, и считать ничего не нужно. Привычка смотреть на концовку записи экономит время сильнее, чем любые вычисления: достаточно один раз выписать несколько чисел и увидеть, как остаток отражается в конце их записи.

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

Почему перебор нельзя начинать с большого числа? Потому что наименьшее подходящее число можно проскочить: если начало перебора выше ответа, программа выдаст верное по форме, но неверное по сути число. Время тут не причина, компьютер перебирает миллион значений быстро. Начинайте с единицы либо оценивайте начало по границе, как в разборе.

Что делать, если программа выдаёт ответ, а рассуждение даёт другой? Сначала проверьте программу на числе, для которого вы вручную знаете результат: чаще расхождение живёт в записи правила, чем в переборе. Потом проверьте границы, строгое ли неравенство. И только если оба шага ничего не нашли, возвращайтесь к рассуждению, потому что закономерность, которую вы заметили, могла быть верна лишь для первых чисел.