Задание 27 ЕГЭ по информатике
Что проверяет: Обработка данных и кластеризация
Задание 27 ЕГЭ по информатике проверяет тему «обработка данных и кластеризация». Ниже вы найдёте 1 вариант с условием, ответом и разбором, а под ними теория и алгоритм решения этого номера.
Теория к заданию 27 ЕГЭ по информатике: обработка данных и кластеризация
Самое сложное задание: нужно обработать большой набор данных и вычислить характеристики кластеров.
Что нужно знать
- Кластеризация по условию задана геометрически: точки кластера умещаются в прямоугольник заданных размеров.
- Разделение на кластеры чаще всего видно по одной из координат, поэтому полезно сначала отсортировать точки.
- Центр кластера по условию определяется как точка самого кластера с минимальной суммой расстояний до остальных.
- Прямой поиск центра требует перебора всех пар; это допустимо при количестве точек порядка тысяч.
- Аномальные точки отбрасывают по удалённости от основной массы, а не по абсолютным координатам.
- Ответ требует именно целой части произведения на 10 000: округлять нельзя.
Что важно в самом сложном задании
- В условии всегда даны два файла: маленький A с известным ответом и большой B. Программу отлаживают на A.
- Решение должно работать за один или два прохода: алгоритмы со вложенными циклами по всем данным не успеют.
- Частый приём: префиксные суммы. Заранее посчитанные накопленные суммы дают сумму любого отрезка за одно действие.
- Другой частый приём: словарь остатков. Для условий вида «сумма делится на k» храните, сколько раз встречался каждый остаток.
- Для задач про кластеры считайте расстояния между соседними элементами после сортировки, а не между всеми парами.
- Храните только то, что нужно: весь массив в памяти держать не обязательно, если данные обрабатываются потоком.
- Обязательно проверьте ответ на файле A: если он не совпал с указанным в условии, ошибка в логике, а не в объёме данных.
- В ответ записывают результат для файла B; за верный ответ только по файлу A ставится часть баллов.
Как решать задание 27
- Прочитайте файл и выведите точки на график, чтобы увидеть структуру кластеров.
- Разделите точки на кластеры по координате, вдоль которой они явно разделяются.
- Отбросьте указанное число аномальных точек как самые удалённые от скоплений.
- Для каждого кластера найдите центр перебором точек с подсчётом сумм расстояний.
- Вычислите требуемые величины и возьмите целую часть произведения на 10 000.
Разбор примера
Общая схема: найти пару элементов, сумма которых делится на заданное число и максимальна.
- Читаем данные из файла A и проверяем на нём каждый шаг решения.
- Считаем остаток каждого элемента от деления на заданное число.
- Для каждого остатка храним два наибольших элемента с таким остатком: больше не нужно.
- Перебираем пары остатков r и k − r: их сумма делится на k.
- Для каждой подходящей пары остатков берём наибольшие элементы и считаем сумму.
- Выбираем максимальную сумму, проверяем ответ на файле A, затем запускаем программу на файле B.
Ответмаксимальная сумма для файла B
Частые ошибки
- Берут центром среднее арифметическое координат, а не точку кластера.
- Округляют результат вместо взятия целой части.
- Не исключают аномальные точки и смещают центры.
Задание 27 входит в ЕГЭ по информатике. На этой странице собраны все варианты этого номера, которые разобраны на сайте: условие, правильный ответ и разбор решения. Остальные номера открываются в списке выше, а целиком все задания ЕГЭ по информатике с ответами собраны на странице предмета.