Разбор номера 27 — ЕГЭ Информатика

📋 Условие

В ЕГЭ по информатике 2025 года задание 27 было кардинально изменено. Теперь задания нацелены на кластеризацию данных и вычисление параметров кластеров.

🔍 Подробное решение

В ЕГЭ по информатике 2025 года задание 27 было кардинально изменено. Теперь задания нацелены на кластеризацию данных и вычисление параметров кластеров. Даются два файла с абсциссой и ординатой точек. Точки следует разделить на кластеры и вычислить заданное в условие значение.

Задание 2701: Фрагмент звёздного неба спроецирован на плоскость. Учёный решил провести кластеризацию точек, разбив их на N непересекающихся подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W. В файле A — данные о звёздах двух кластеров (H=11, W=11). В файле B — данные о звёздах трёх кластеров (H=13, W=13).

Три шага решения:

1. Прочитать и обработать данные из файла (привести к нужному типу)
2. Провести кластеризацию данных — разделить все данные на группы по схожим признакам (визуализация + построение уравнений прямых)
3. В получившихся кластерах найти медоиды и вычислить среднее арифметическое по их координатам

Метод кластеризации:
- Визуализируем данные (точечная диаграмма в Excel/LibreCalc)
- Определяем прямые, разделяющие кластеры (x = const или y = const)
- Распределяем точки по кластерам
- Для каждого кластера находим медоид (точка с минимальной суммой расстояний до остальных)
- Вычисляем среднее арифметическое координат медоид

Код Python:
```python
data = []
with open('27_A.txt') as f:
for line in f:
x, y = map(float, line.replace(',','.').split())
data.append((x, y))

clusters = [[], []]
for x, y in data:
if x < 1:
clusters[0].append((x, y))
else:
clusters[1].append((x, y))

def get_medoid(cluster):
best = None
best_sum = float('inf')
for p in cluster:
s = sum(((p[0]-q[0])2+(p[1]-q[1])2)**0.5 for q in cluster)
if s < best_sum:
best_sum = s
best = p
return best

medoids = [get_medoid(c) for c in clusters if c]
result = (sum(m[0] for m in medoids)/len(medoids)*10000,
sum(m[1] for m in medoids)/len(medoids)*10000)
print(result)
```

Ответы: Файл A: 26216 24182; Файл B: 150891 63754

📚 Теория

Кластерный анализ. Метод ближайшего соседа, центроиды.

🐍 Шаблон Python

Python

from math import dist
cl1 = []; cl2 = []
for i in open('27'):
    x, y = [float(x) for x in i.split()]
    if y < 5: cl1.append([x,y])
    if y > 5: cl2.append([x,y])

def center(cl):
    mn = []
    for p1 in cl:
        s = sum(dist(p1,p2) for p2 in cl)
        mn.append([s, p1])
    return min(mn)[1]

print(center(cl1))
print(center(cl2))

🐍 Альтернативный способ

Способ 2

# Кластеризация с N кластерами (k-means)
from math import dist
pts = []
for line in open('27'):
    x, y = map(float, line.split())
    pts.append((x, y))

# Сортируем и делим на 2 кластера
pts.sort(key=lambda p: p[1])
mid = len(pts) // 2
cl1, cl2 = pts[:mid], pts[mid:]

# Центр масс кластера
def centroid(cl):
    cx = sum(p[0] for p in cl) / len(cl)
    cy = sum(p[1] for p in cl) / len(cl)
    return (cx, cy)
print(centroid(cl1))
print(centroid(cl2))

🔗 Полезные ссылки