+Оглавление
Разбираем задачу №6 в ЕГЭ по информатике.
Обратите внимание, здесь будет не только пример решения, но и разбор задания по существу.
Для примера я беру демоверсию 2020 года (актуальная на момент написания статьи) с сайта fipi.ru.
Прежде чем приступать к решению этого примера, посмотрим в спецификацию к демоверсии.
Мы должны уметь исполнять алгоритм, записанный на обычном русском языке (без кодов программ), либо сами уметь составлять таковой.
В кодификаторе написано, в общем-то, то же самое: практические вычисления.
Немного об алгоритмах
У многих со словом "алгоритм" связывается только набор действий. На самом деле, в него включается ещё и исполнитель, который и будет делать эти действия. В нашем случае, исполнитель - человек, сам экзаменующийся. От него требуется чёткое последовательное исполнение всех команд.
Алгоритмы в школьной программе разделяют на три основные группы:
- линейные,
- ветвящиеся,
- циклические.
Первая группа - те алгоритмы, в которых команды выполняются одна за другой.
Во второй группе есть команда, которая иногда выполняется, а иногда нет - в зависимости от решения, которое принимает исполнитель. Это решение должно быть основано на тексте программы и имеющихся данных.
Третья группа требует от нас повторения команды нужное количество раз или "до тех пор пока".
О самой задаче №6
В какой-то степени, мы имеем обратную задачу. В том смысле, что у нас имеется алгоритм (линейный), но нет исходных данных. Однако у нас нет и результата работы алгоритма, а есть только ограничения на него ("минимальное" и "превышает 97"), поэтому подбор в нормальном виде осуществить не удастся. И всё же, работать надо именно в этом направлении. Можно построить подбор на таком принципе:
выбираем исходные данные, выполняем алгоритм, проверяем, подходит ли результат по критериям.
Именно в 6м задании ЕГЭ есть несколько существенных упрощений, без которых в общем случае решить эту задачу невозможно или крайне трудно (поэтому тут и нет чего-то типа формулы Кардано):
- Работа ведётся в целых числах, поэтому подбор можно заменить на перебор.
- Алгоритм всегда задаётся таким образом, чтобы выбирая бóльшее исходное число, мы получали бы бóльший результат (иногда наоборот - меньший).
- Алгоритм достаточно прост, чтобы можно было его выполнить быстро и/или оптимизировать для большого набора подряд идущих чисел.
Воспользуемся этим при решении.
Решение
Для начала (это лучше делать не на экзамене, а за пару месяцев до него) надо потренироваться выполнять предложенный алгоритм. Даже если у нас есть какие-то предположения или домыслы о том, какие числа хорошо бы брать, начинать стоит с таких чисел, с которыми алгоритм выполнится легко. По ходу алгоритма надо:
1. Построить двоичную запись исходного числа, поэтому берём числа, которые можно просто и без проблем перевести (читайте об экспресс-методах перевода в двоичную систему):
2. а. Складываем все цифры (1+0+0+0+0+0+1=2), вычисляем остаток от деления на 2 (2 mod 2 = 0) и дописываем его в конец: 10000010
2. б. Складываем все цифры (1+0+0+0+0+0+1+0=2), вычисляем остаток от деления на 2 (2 mod 2 = 0) и дописываем его в конец: 100000100
Полученное число переводим в десятичную:
Теперь у нас есть исходные данные, алгоритм и результат.
Осталось проверить, подходит ли по критерию результат. 260 превосходит 97... ээээ... Но является ли оно наименьшим? Попробуем получить число меньше.
Воспользуемся второй особенностью, и попробуем взять что-то, что меньше 65.
Наша задача найти границу - такое число, результат работы с которым ещё подходит под условие "превосходит 97", а если взять число на 1 меньшее - уже нет.
Как видим, есть ещё число 102, которое больше подходит по критериям: оно превосходит 97 и является меньшим, чем предыдущее. Для точного попадания нам надо взять число ещё меньше, и проверить его.
24 преобразуется в 96. Оно уже не подходит! Значит, если мы возьмём пару
25 -> 102
то это и будет наименьший результат, который превосходит 97. Задача решена. Осталось понять, что пишем в ответе - исходные данные, или результат (мы подбирали и то, и другое).
может являться результатом работы данного алгоритма.
однозначно указывает на то, что нужен результат. Это 102.
Важно, что с любым числом каждый шаг алгоритма исполнять в точности. Тут могут быть две проблемы. Первая - извечная - смысловое чтение текста. Понять, что требуется сделать без предварительной подготовки бывает трудно. Для этого я написал в конце статьи кое-что об алгоритмах такого типа. Вторая проблема - даже понявшие алгоритм ученики любят пропускать пункты, делая их даже не в уме, а вспоминая результат из аналогичной ситуации. Этого делать нельзя,
если пункт есть - изволь выполнить его в точности.
На поиск этого числа отводится 4 минуты, и если пользоваться быстрыми методами перевода в двоичную и обратно, можно за это время перебрать 5-6 чисел. Но что делать, если время уходит, а граница так и не найдена?
Хитрости и облегчение подбора.
После одного-двух проходов, у Вас может появиться свой способ оптимизировать работу - ваш личный. Им и надо пользоваться, не слушая ни кого. Быстрее способа для Вас не будет.
Анализ алгоритма
При работе алгоритма число в двоичной форме увеличивается на 2 разряда справа. Те, кто хорошо знает особенности позиционных систем счисления, понимают, что если вы к числу справа припишите 0, то оно увеличится в... 10 раз? нет. Это было в десятичной системе. Там умножение на 10 вносило новый "ноль" справа.
в системах с другим основанием увеличение будет во столько раз, сколько в этой системе записывается как "10".
В восьмеричной 8 записывается как "10", в троичной 3. А в двоичной "10" - это число 2. Во всех случаях это совпадает с основанием системы счисления. Значит, у нас число во время работы алгоритма два раза увеличивается в 2 раза.
Ремарка. При приписывании к записи числа в системе с основанием N справа не нуля, а единицы (или другой цифры) даёт увеличение не ровно в N раз, а примерно в N раз (от N до N+1 раз). Например, в десятичной 131 ≈ 13*10. Для прикидки и уменьшения поля перебора можно пользоваться и такой особенностью.
Значит, если мы возьмём число 10, то после работы алгоритма получим что-то около 10*2*2=40, может, чуть больше. Нам нужно найти число, которое при увеличении в 4(или чуть больше) раза даст нам то, что подойдёт по критерию. (А всем понятно, что дважды в два раза - это всё равно, что в четыре раза?)
Именно из этих соображений я взял 24,25 и 26. 25 подошло, 24 нет, а 26 проверять уже не было смысла.
Практическая значимость алгоритма
Если кто-то ещё не понял, что ЕГЭ полностью определяется практическими, жизненными задачами, расскажу, где применяется этот алгоритм.
При передаче информации для определения нечётных ошибок (одна, три, 5 и т д) в конец сообщения добавляют биты чётности. Один или два бита таким образом, чтобы в сообщении было чётное (или нечётное) количество единиц. Если в полученном сообщении чётность нарушена, значит, передача пошла с ошибкой, и надо запрашивать ещё раз. Это самый помой способ отловить часть ошибок передачи. На столько простой, что в некоторых системах связи реализован аппаратно (com, usart).
Если требуется обнаружить все ошибки, то используются более сложные алгоритмы расчёта контрольных сумм. В штрихкоде на товаре в супермаркете последняя цифра не несёт информации о товаре, она вычисляется из остальных. И когда товар "не бьётся", это значит, что считанная контрольная сумма не совпала с расчётной, значит, при чтении кода произошла ошибка. Аналогичная ситуация с последними цифрами номера банковских карт.
В QR кодах тоже есть избыточная информация, и она позволяет не только обнаружить ошибку, но и исправить её (коды Хэмминга)
И все это - 6 задание ЕГЭ.
Другие варианты задания
В экзамене могут дать и совершенно другой алгоритм, но в любом случае он будет использовать закономерности позиционных систем счисления, как правило, с основаниями 2 или 10.
Перечислю те, которые я замечал в заданиях:
- Приписывание цифры справа увеличивает число в N+ раз (как у нас с учётом ремарки)
- Умножение на N можно заменить на приписывание нуля справа к записи числа в системе с основанием N
- В системе с основанием N нет цифры N или больше
- Сумма двух цифр записи числа в системе с основанием N не превосходит 2N-2
На последней закономерности построено аналогичное задание из ОГЭ.
PS
Надеюсь, разбор был достаточно подобным. Ставьте лайк, подписывайтесь на канал.
