+Оглавление
Разбираем задачу №3 в ЕГЭ по информатике.
Обратите внимание, здесь будет не только пример решения, но и разбор задания по существу.
Для примера я беру демоверсию 2020 года (актуальная на момент написания статьи) с сайта fipi.ru.
Прежде чем приступать к решению этого примера, посмотрим в спецификацию к демоверсии.
В третьей строке указано умение представлять и считывать данные со схем, карт, таблиц, графиков и т.д.
По кодам примерно то же самое: читать схемы и графики. По-хорошему, чтобы научиться читать схемы, надо сначала научиться их строить. Знакомая ситуация?
Графы и таблицы (подготовка)
Чаще всего в этих заданиях требуется одну и ту же информацию видеть в разных формах. Что такое граф? Это рисунок, состоящий из точек, которые соединены линиями. Точка - объект, линия - связь. Самый простой пример графа - схема дорог, точки - города, линии - дороги. Примерно с этим мы сталкиваемся в задании.
Каждый граф может быть не только нарисован, но и записан в виде таблицы. Такая таблица по-умному называется матрица смежности графа.
Таблица в нашем случае довольно необычная - в ней одинаковые подписи строк и столбцов. Кто посмотрел по-внимательнее, заметил, что она ещё и симметричная. Пользоваться ей тоже надо уметь: чтобы узнать, как далеко ехать из Самары в Нижний Новгород, мы должны найти такую таблицу и в строке "Самара" искать пересечение со столбцом "Нижний Новгород". Там будет расстояние между этими городами. У нас вместо названий - номера. Это немного неудобно, но так тоже можно работать.
На графе информация представлена наглядно для человека, а в таблице с ней может работать и компьютер.
Самый простой способ научиться связывать эти две вещи - граф и таблицу - попробовать строить по одной другую.
Тогда Вы найдёте закономерности, близкие именно Вам. Многим этого будет достаточно для решения задания в ЕГЭ, а кому-то потребуется более детальная тренировка.
Возьмите для начала таблицу (это проще), на бумаге расставьте в кружочек точки. Каждую точку подпишите так же, как подписаны столбцы таблицы. (У Вас должно получиться точек столько же, сколько столбцов.)
Дальше работаем с таблицей следующим образом: Берём первый столбец и ищем непустые клетки в нём. Это 4я и 7я строки. Нам нужно соединить первую точку с каждой из них:
Соединяем так все. Дважды одну и ту же линию не проводим - ленимся по максимуму. В результате у нас получится картинка.
На что надо обращать внимание:
Кратность вершин. Это количество связей, которые выходят из вершин. Например, в нашей задаче из вершины A выходит только одна связь. Кратность (A) = 1. Наибольшая кратность у пункта Д (6)
Длины связей могут быть любыми, очень очень далёкими от табличных значений. На нашей картинке связь "4"-"7" средненькой длины, а по таблице - она самая длинная. Можно, если хотите, перерисовать картинку, улучшив эту ситуацию, но надо бы научиться делать это и без точного соответствия. Про топологические и точные чертежи я уже писал, но тут нам достаточно топологического чертежа, ибо числа такие, что прямыми линиями нужной длины точки соединить невозможно. (Если кому интересно доказательство сего факта, попробуйте нарисовать треугольник "4"-"5"-"7".)
Пересечение связей желательно исключить. Я, когда рисовал картинку, одну связь перерисовывал ("4"-"6"), потому что она давала пересечение. С первого раза нарисовать хороший граф практически невозможно, поэтому не отчаивайтесь, если не получается. В конце концов, они могут пересекаться, но не задевать "чужие" точки.
Кто с кем в контакте. Например, на нашем графе видно, что пункты А и Б связаны, значит, между ними есть дорога, есть число в таблице на пересечении А и Б, а В и Е - нет, там числа быть не может.
Судоку
Вы играли в эту игру? Выглядит она примерно так:
Правила игры простые: надо заполнить квадрат числами от 1 до 9 (с повторами) таким образом, чтобы в каждой строке были все 9 чисел, в каждом столбце, и в каждой выделенной ячейке 3*3 тоже.
СПОЙЛЕР
Есть универсальный способ решения судоку: в каждую пустую ячейку надо записать все цифры, которые там могут быть, потом шаг за шагом по циклу выполнять следующие действия:
Если в строке/столбце/ячейке такая цифра одна ЛИБО в клетке осталась одна цифра - она ставится в клетку, а её "дубликаты" стираются из остальных клеток строки/столбца/ячейки.
Примерно такой принцип можно применять и к третьему заданию в ЕГЭ по информатике: расставим возле каждого столбца все возможные варианты названий населённых пунктов:
И будем вычёркивать по одной "невозможные" комбинации. Сначала третья строка. Там всего одно число, значит из пункта с номером "3" выходит только одна дорога. На графе у нас есть вершина с кратностью 1 - это пункт А. Вот Вам однозначное соответствие А и "3". Вычёркиваем всё, что стало теперь невозможным: из третьей строки всё, кроме "А", из остальных "А"
Аналогичная ситуация с кратностями = 5 (у п. 4 и точки Д) и 4 (у пункта 6 и Б)
У пунктов "В" и "Е" кратность = 2, значит, они могут быть только под номерами 1 и 2. А у "Г" и "К" кратность = 3, значит, только п. 5 и 7. Вычеркнем лишнее (я перепишу полностью)
После такого вычёркивания одной только кратностью не обойтись. Нам потребуется проследить связи на 1 пункт вглубь. п "Е" (или 1, или 2 строка) связан с пунктами "Д" и "К", но не "А" "Б" "В" "Г". Приглядитесь, во второй строке есть связь с пунктом Б, значит, она не может быт пунктом "Е"! Вычёркиваем. Кстати, теперь во второй строке только одна буква "В":
В этом задании нам несказанно повезло: таблицу удалось восстановить полностью, используя всего две вещи: кратность и ближайших соседей. Кроме того, потребовалось очень мало итераций (3 для кратностей и 3 для соседства), чтобы это сделать. Каждым ходом мы либо исключали из строки буквы, либо утверждали одну букву. Теперь установить ответ на любой вопрос в задаче можно. Можно, например, нанести на граф длины дорог, чтобы проследить кратчайший маршрут. Нас спрашивают длину дороги Д-Е. Это 9 километров. Задача решена.
Отметим, что последний шаг (третье использование ближайшего соседства) для определения пунктов Г и К я не стал описывать, ибо задача к тому моменту уже была решена. Иногда какую-то неопределённость разрешить остаётся невозможно. Такое бывает и в судоку. В отличие от числового кроссворда ("кросснума"), на ЕГЭ Ваша задача - не восстановить таблицу, а выудить из неё ответ на конкретный вопрос. Это возможно ВСЕГДА (так устроено ЕГЭ) даже если невозможно однозначно восстановить таблицу или граф.
Аналогичная задача может быть по восстановлению графа по неполной таблице, тогда вместо чисел Вы заметите звёздочки (*) в ячейках таблицы. Это и значит, что нам нужно считать заполненные ячейки и смотреть ближайших соседей.
Заключение
Такой алгоритм решения судоку (ой, простите, ЕГЭ, конечно же, ЕГЭ) положен в основу компьютерных алгоритмов, разрешающих эту головоломку. Я рекомендую потратить пару вечеров, решая судоку самого простого уровня именно таким образом (долго не играйте, надо готовиться), чтобы хотя бы ознакомиться с таким вариантом подбора.
PS
Подписывайтесь на канал, чтобы в первых рядах узнать, когда я разберу остальные задания. Ставьте лайк, чтобы я знал, что моя работа небесполезна.