Задание 27 ЕГЭ по информатике

Что проверяет: Обработка данных и кластеризация

Задание 27 ЕГЭ по информатике проверяет тему «обработка данных и кластеризация». Ниже вы найдёте 4 варианта с условием, ответом и разбором, а под ними теория и алгоритм решения этого номера.

4 варианта с ответами

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников. Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных его точек минимальна. Для каждого кластера гарантируется единственность его центра. Известно, что количество точек не превышает 1000. Известно, что количество точек не превышает 10000. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно. Гарантируется, что во всех кластерах количество точек различно. Возможные данные одного из файлов проиллюстрированы графиком. График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемого файла

Текст распознан с изображения задания. Формулы, таблицы и рисунки смотрите на картинке ниже.

ЕГЭ по информатике: задание 27, условие
Скачать DEMO_27_A.txtСкачать DEMO_27_B.txt
Решение
ЕГЭ по информатике: задание 27, ответ и решение

На числовой прямой отмечены точки с координатами:

3, 5, 6, 14, 15, 17, 28, 30, 41, 42, 43, 55

Точки объединяются в кластеры по правилу: две соседние по возрастанию точки попадают в один кластер, если расстояние между ними не превышает 2. Определите количество получившихся кластеров.

Ответ
5

Упорядочиваем точки и смотрим на разности соседних: 2, 1, 8, 1, 2, 11, 2, 11, 1, 1, 12.

Разрыв кластера происходит там, где разность больше 2: это четыре места. Четыре разрыва делят набор на пять кластеров: {3, 5, 6}, {14, 15, 17}, {28, 30}, {41, 42, 43} и {55}. Ответ — 5.

На числовой прямой отмечены точки с координатами:

3, 5, 6, 14, 15, 17, 28, 30, 41, 42, 43, 55

Точки объединяются в кластеры: две соседние по возрастанию точки попадают в один кластер, если расстояние между ними не превышает 10. Определите количество точек в самом большом кластере.

Ответ
6

При пороге 10 разрывы остаются только там, где разность соседних точек больше 10: между 17 и 28, между 30 и 41, между 43 и 55.

Кластеры получаются такие: {3, 5, 6, 14, 15, 17}, {28, 30}, {41, 42, 43} и {55}. Самый большой содержит шесть точек. Ответ — 6.

На числовой прямой отмечены точки с координатами:

3, 5, 6, 14, 15, 17, 28, 30, 41, 42, 43, 55

Точки объединяются в кластеры с порогом расстояния 2 (см. правило выше). Определите наибольшую сумму координат точек одного кластера.

Ответ
126

При пороге 2 кластеры такие: {3, 5, 6}, {14, 15, 17}, {28, 30}, {41, 42, 43} и {55}.

Суммы координат по кластерам: 14, 46, 58, 126 и 55. Наибольшая равна 126. Ответ — 126.

Теория к заданию 27 ЕГЭ по информатике: обработка данных и кластеризация

Самое сложное задание: нужно обработать большой набор данных и вычислить характеристики кластеров.

Что нужно знать

Что важно в самом сложном задании

Как решать задание 27

  1. Прочитайте файл и выведите точки на график, чтобы увидеть структуру кластеров.
  2. Разделите точки на кластеры по координате, вдоль которой они явно разделяются.
  3. Отбросьте указанное число аномальных точек как самые удалённые от скоплений.
  4. Для каждого кластера найдите центр перебором точек с подсчётом сумм расстояний.
  5. Вычислите требуемые величины и возьмите целую часть произведения на 10 000.

Разбор примера

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

  1. Читаем данные из файла A и проверяем на нём каждый шаг решения.
  2. Считаем остаток каждого элемента от деления на заданное число.
  3. Для каждого остатка храним два наибольших элемента с таким остатком: больше не нужно.
  4. Перебираем пары остатков r и k − r: их сумма делится на k.
  5. Для каждой подходящей пары остатков берём наибольшие элементы и считаем сумму.
  6. Выбираем максимальную сумму, проверяем ответ на файле A, затем запускаем программу на файле B.

Ответмаксимальная сумма для файла B

Частые ошибки

Задание 27 входит в ЕГЭ по информатике. Это единственная страница сайта, где собраны все варианты этого номера: текст условия, картинка задания, правильный ответ, разбор решения и теория с алгоритмом. Остальные номера открываются в списке выше, а их перечень с темами есть в списке заданий ЕГЭ по информатике.