Разборы · ЕГЭ, задание 27

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

Что проверяет задание

Задание 27 — анализ данных: в файле точки (звёзды, частицы) с координатами и другими характеристиками. Их нужно разбить на кластеры, найти центр каждого и посчитать требуемые величины. Оценивается в 2 балла: 1 балл дают, если числа перепутаны местами или верно только одно число на своём месте. Решение, как и во всех заданиях ЕГЭ по информатике, не проверяется — важен только итоговый ответ.

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

• Кластер — группа близких объектов. Разбиение обычно видно по данным: кластеры отделены большими промежутками.
• Центр кластера — объект, у которого сумма расстояний (или модулей разностей) до остальных минимальна. Для одномерной величины это медиана.
• Евклидово расстояние — math.dist(p, q).
• Числа в файле часто записаны с десятичной запятой: перед float замените её на точку.

Как решать

1. Посмотрите на данные: постройте точечную диаграмму в электронной таблице или отсортируйте значения — кластеры станут видны.
2. Разбейте данные: по координатам, по порогу или, как в демоверсии, по самым большим промежуткам между соседними значениями.
3. Для каждого кластера найдите центр и нужные величины.
4. Проверьте условия из задания (размер, число кластеров) через assert.

Пример из демоверсии 2027

Частицы на плоскости: x, y, V_x, V_y, масса m и признак (римское число I–VII). Кинетическая энергия E = m · (V_x² + V_y²) / 2. Частицы разбиваются на K = 4 кластера так, что в каждом энергии различаются не больше чем на R = 2,0. Центр кластера — частица с минимальной суммой модулей разности энергий с остальными. Найдите Q₁ — наибольшее расстояние между частицами одного кластера с признаком II, и Q₂ — максимальную энергию центра кластера. В ответ — целые части Q₁ × 10 000 и Q₂ × 10 000.

Решение. Сортируем частицы по энергии и режем по трём самым большим промежуткам между соседними значениями. Получаются кластеры из 500, 600, 700 и 800 частиц, размах каждого меньше 2,0.

import math

parts = []
for line in open("27.txt"):
    p = line.replace(",", ".").split()
    if len(p) == 6:
        x, y, vx, vy, m = map(float, p[:5])
        parts.append((m * (vx ** 2 + vy ** 2) / 2, x, y, p[5]))
parts.sort()

# разрезаем по трём наибольшим промежуткам между соседними энергиями
gaps = sorted(range(1, len(parts)), key=lambda i: parts[i][0] - parts[i - 1][0])
cuts = [0] + sorted(gaps[-3:]) + [len(parts)]
clusters = [parts[a:b] for a, b in zip(cuts, cuts[1:])]

q1, q2_low, q2_high = 0, 0, 0
for c in clusters:
    assert c[-1][0] - c[0][0] <= 2.0
    n = len(c)
    q2_low = max(q2_low, c[(n - 1) // 2][0])     # нижняя из двух средних частиц
    q2_high = max(q2_high, c[n // 2][0])         # верхняя из двух средних частиц
    two = [t for t in c if t[3] == "II"]
    for i in range(len(two)):
        for j in range(i + 1, len(two)):
            q1 = max(q1, math.dist(two[i][1:3], two[j][1:3]))

print([len(c) for c in clusters])
print(int(q1 * 10000), int(q2_high * 10000))     # эталон: верхняя средняя частица
print(int(q1 * 10000), int(q2_low * 10000))      # нижняя средняя частица

Эталонный ответ демоверсии: 539936 100704.

Честное замечание о данных. В условии обещано, что центр каждого кластера единственный, но в файле демоверсии это не так. Во всех кластерах чётное число частиц, а у медианы чётного набора две средние частицы дают одну и ту же минимальную сумму модулей разностей. Для Q₂ важен верхний кластер: там это частицы с энергией ≈ 10,066663 и ≈ 10,070467. Эталон берёт вторую, верхнюю, — отсюда 100704. Если взять первую, получится 539936 100666: по правилам оценивания это было бы засчитано как одно верное число на своём месте, то есть 1 балл из 2. Q₁ от выбора центра не зависит.

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

Типичные ошибки

• Не заменяют десятичную запятую на точку, и float падает с ошибкой.
• Считают центр как среднее значение — это другая точка, и она может не совпадать ни с одной частицей.
• Ищут расстояние между частицами из разных кластеров, хотя спрашивают «одного кластера».
• Округляют вместо того, чтобы взять целую часть, — int(), а не round().

Потренироваться: задание 27 новые варианты с проверкой ответа