Задача 27 ЕГЭ по информатике — кластеризация частиц
Рассматриваются частицы на плоскости, обладающие следующими характеристиками: декартовы координаты, вектор скорости, масса, а также признак, характеризующий внутреннее строение частицы, обозначаемый числами отI доVII (в римской системе счисления).
Учёный решил провести кластеризацию частиц по значениям их кинетической энергии, то есть разбить их множество на K непересекающихся непустых подмножеств (кластеров), таких, что модуль разности кинетических энергий любых двух частиц каждого подмножества не превосходит значения R. Гарантируется, что такое разбиение существует и единственно для заданного R.
Будем называть центром кластера такую его частицу, для которой сумма модулей разности кинетических энергий со всеми остальными частицами этого кластера минимальна. Для каждого кластера гарантируется единственность его центра.
В каждой строке текстового файла хранится информация об одной частице: координаты x и y, проекции вектора скорости Vx и Vy, масса m и признак.
Сортировка и кластеризация
Логика
Сортируем все частицы по энергии (по первому элементу списка).
Идём по отсортированному списку и добавляем частицы в текущий кластер, пока разница между энергией текущей частицы и первой частицей кластера ≤ 2.0.
Если разница больше 2.0 — закрываем текущий кластер и начинаем новый.
В конце добавляем последний кластер.
При отсортированном списке условие «разность энергий любых двух частиц в кластере ≤ 2.0» эквивалентно «разность между первой и последней частицей кластера ≤ 2.0».
#ЕГЭИнформатика #Задача27 #PythonДляЕГЭ #РазборЗадач #ПодготовкаКЕГЭ #КластеризацияВЕГЭ
Рассматриваются частицы на плоскости, обладающие следующими характеристиками: декартовы координаты, вектор скорости, масса, а также признак, характеризующий внутреннее строение частицы, обозначаемый числами отI доVII (в римской системе счисления).
Учёный решил провести кластеризацию частиц по значениям их кинетической энергии, то есть разбить их множество на K непересекающихся непустых подмножеств (кластеров), таких, что модуль разности кинетических энергий любых двух частиц каждого подмножества не превосходит значения R. Гарантируется, что такое разбиение существует и единственно для заданного R.
Будем называть центром кластера такую его частицу, для которой сумма модулей разности кинетических энергий со всеми остальными частицами этого кластера минимальна. Для каждого кластера гарантируется единственность его центра.
В каждой строке текстового файла хранится информация об одной частице: координаты x и y, проекции вектора скорости Vx и Vy, масса m и признак.
Сортировка и кластеризация
Логика
Сортируем все частицы по энергии (по первому элементу списка).
Идём по отсортированному списку и добавляем частицы в текущий кластер, пока разница между энергией текущей частицы и первой частицей кластера ≤ 2.0.
Если разница больше 2.0 — закрываем текущий кластер и начинаем новый.
В конце добавляем последний кластер.
При отсортированном списке условие «разность энергий любых двух частиц в кластере ≤ 2.0» эквивалентно «разность между первой и последней частицей кластера ≤ 2.0».
#ЕГЭИнформатика #Задача27 #PythonДляЕГЭ #РазборЗадач #ПодготовкаКЕГЭ #КластеризацияВЕГЭ