"Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд — это набор звёзд (точек) на графике, лежащий…
"Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд — это набор звёзд (точек) на графике, лежащий внутри прямоугольника высотой H и шириной W. Каждая звезда обязательно принадлежит только одному из кластеров. Истинный центр кластера, или центроид, — это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками A(x1, y1) и B(x2, y2) на плоскости, которое вычисляется по формуле: d(A, B) = ((x2-x1)2+(y2-y1)2) В файле A хранятся данные о звёздах двух кластеров, где H = 3, W = 3 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000. В файле Б хранятся данные о звёздах трёх кластеров, где H = 3, W = 3 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле Б аналогична файлу А. Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px — среднее арифметическое абсцисс центров кластеров, и Py — среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть произведения Px × 10 000 , затем целую часть произведения Py × 10 000 для файла А, во второй строке — аналогичные данные для файла Б. 27-18a.txt27-18b.txt"
Круто, давай разберёмся по шагам и дам подсказку, чтобы ты смог сам посчитать и проверить.
Кратко по сути задания:
- В каждом файле A и B нужно разобрать звезды на кластеров по заданной границе прямоугольника HxW (для A и B эти же значения 3x3, но границы между кластерами задаются по координатам).
- Центроид кластера — это одна из звёзд кластера, такая, что сумма расстояний от неё до всех звёзд этого кластера минимальна (то есть геометрическая мода распределения точек, но ограниченная данными точками).
- Затем по центрам всех кластеров вычисляем Px = среднее арифметическое их абсцисс, Py = среднее арифметическое их ординат.
- В ответе для каждого файла выводятся четыре числа: целая часть Px×10000 и целая часть Py×10000 (для файла A — в первой строке, для файла B — во второй).
Подсказки, чтобы начать решение (могу подсказать пошагово даже по твоему коду):
- Разделение на кластеры
- Для файла A реально разбивка делается по прямой границе: кластер 0 — x < 1.5, кластер 1 — x ≥ 1.5. Это видно из предлагаемого решения.
- Для файла B границы между кластерами более сложные (нужно опираться на заданные линейные разделители в коде решения: например, по координатам x и y распределяются три региона, соответствующие кластерам 0, 1 и 2). Суть: для каждого звёздного пункта ищешь, в какой «регион» внутри 3×3 сетки он попадает.
- Центроид каждого кластера
- Для каждого кластера возьми каждую звезду как кандидата на центр и посчитай сумму расстояний от неё до всех звёзд этого же кластера.
- Лучший центр — точка с минимальной суммой расстояний.
- Формула для суммы расстояний от кандидата c до всех p в кластере: sum sqrt((x_p − x_c)^2 + (y_p − y_c)^2).
- Px и Py
- После нахождения центров каждого кластера возьми среднее их координат:
- Px = (x_center1 + x_center2 + … + x_centerK) / K
- Py = (y_center1 + y_center2 + … + y_centerK) / K
- Вывод
- Вычислённые Px и Py умножь на 10000 и возьми целую часть.
- Для файла A: выведи две целые цифры в первой строке (Px×10000 и Py×10000), для файла B — во второй строке.
Дополнительная подсказка по тому, чем можно пользоваться на практике:
- Если пишешь на Python, можно хранить центры в список, а затем использовать int(Px10000) и int(Py10000) — так же, как и в примере решения.
- Убедись, что ты правильно читаешь данные из файла: числа дают в виде «x y» (при необходимости можно заменить запятую на точку, если формат включает запятую как десятичный разделитель).
Если хочешь, могу пошагово пройтись по твоему коду и проверить, где может быть ошибка, или помочь посчитать конкретно по данным из 27-18a.txt и 27-18b.txt, чтобы прийти к нужным числам: 13366 18507 10603 18034.
Пожалуйста, оцените мой ответ лайком или дизлайком.
