Задание 27. Анализ данных – ЕГЭ по информатике

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

Задание 27 – файл с точками (частицами, звёздами), которые надо разбить на кластеры, найти в каждом центр и посчитать по кластерам два числа.

2 балла, норматив 36 минут.

Что нужно знать заранее:

чтение файла построчно и замена десятичной запятой: line.replace(',', '.');
список списков: кластеров четыре – значит, clusters = [[], [], [], []], и частица кладётся в свой по append;
поиск минимума в цикле: заводим «лучшее» значение и обновляем его, когда нашлось меньше;
вложенный цикл по парам – перебор всех пар внутри кластера;
точечная диаграмма в Calc – показана ниже по шагам.

Типовой пример

Задание 27 демонстрационного варианта ЕГЭ-2027 (ФИПИ).

Файл с данными: demo_27.txt – текстовый файл, 2600 строк по шесть значений: координаты, проекции скорости, масса и признак. Положите его рядом со скриптом, не переименовывая: код ниже открывает demo_27.txt – то самое имя, под которым файл скачивается.

Рассматриваются частицы на плоскости, обладающие следующими характеристиками: декартовы координаты, вектор скорости, масса, а также признак, характеризующий внутреннее строение частицы, обозначаемый числами от I до VII (в римской системе счисления).

Учёный решил провести кластеризацию частиц по значениям их кинетической энергии, то есть разбить их множество на K непересекающихся непустых подмножеств (кластеров), таких, что модуль разности кинетических энергий любых двух частиц каждого подмножества не превосходит значения R. Гарантируется, что такое разбиение существует и единственно для заданного R.

Будем называть центром кластера такую его частицу, для которой сумма модулей разности кинетических энергий со всеми остальными частицами этого кластера минимальна. Для каждого кластера гарантируется единственность его центра.

В каждой строке текстового файла хранится информация об одной частице: координаты $x$ и $y$, проекции вектора скорости $V_x$ и $V_y$, масса $m$ и признак. Значения даны в одинаковых для всех частиц единицах измерения, обозначения единиц измерения в файле не приводятся.

Значения в строке разделяются одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 10 000. Абсолютная величина каждого числового значения не превышает 100,0.

Известно, что все описанные в файле частицы подразделяются ровно на 4 кластера (K = 4) с R = 2,0 для каждого.

Для каждого кластера определите его центр, затем найдите два числа: $Q_1$ – наибольшее евклидово расстояние между частицами одного кластера, имеющими признак II, и $Q_2$ – максимальное значение кинетической энергии для центра кластера.

В ответе запишите два числа: сначала целую часть произведения $Q_1 \times 10000$, затем целую часть произведения $Q_2 \times 10000$.

Для справки. Кинетическая энергия $E$ частицы массы $m$, обладающей скоростью $\vec{V} = (V_x; V_y)$, вычисляется по формуле $E = \frac{1}{2} m (V_x^2 + V_y^2)$. Евклидово расстояние между двумя точками на плоскости $A(x_1, y_1)$ и $B(x_2, y_2)$ вычисляется по формуле $d(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$.

Типовой пример организации данных во входном файле. Три строки файла для трёх частиц:

0,67 -2,14 3,0 -4,0 0,2 V
3,14 7,22 3,2 4,3 0,7 II
1,33 5,56 0,00 5,22 0,456 IV

Для частицы из первой строки примера кинетическая энергия равна 2,5.

Как рассуждать

Условие длинное, но спрашивают в нём два числа, и прежде чем писать код, стоит понять, что для каждого из них нужно.

Оба ответа – «по кластерам». $Q_1$ – расстояние между частицами одного кластера, $Q_2$ – энергия центра кластера. Значит, прежде всего надо знать, в каком кластере лежит каждая частица. Это и есть главная трудность задачи; остальное – подсчёт.
Как найти кластеры. Кластеризация ведётся по энергии, то есть у каждой частицы одно число. Условие говорит, что кластеров 4 и что в кластере энергии различаются не больше чем на R = 2, но где проходят границы – не говорит. Напрашивается правило «отсортировать энергии и начинать новый кластер там, где разрыв больше R» – на файле демоверсии оно собирает все частицы в один кластер: промежутки между кластерами 0,8–1,3, меньше R. Условие про R описывает ширину кластера, а не расстояние между ними. Чтобы подобрать порог достаточно посмотреть на энергии на графике – группы видны сразу.
Что делать в таблице, а что – в Python. Таблица удобна, чтобы посчитать энергию и увидеть картинку. А $Q_1$ и $Q_2$ – это перебор пар частиц внутри кластера и в таблице это неудобно, а в Python – два вложенных цикла. Поэтому границы берём с графика, а считаем программой.

Отсюда план, по пункту на шаг ниже:

В Calc посчитать энергии и снять с графика границы кластеров.
Прочитать файл в Python и разложить частицы по кластерам.
Найти $Q_1$.
Найти центры кластеров и $Q_2$.

Шаг 2. Читаем файл и раскладываем по кластерам

Теперь те же частицы читаем в Python. Каждая строка файла – одна частица: split() режет строку по пробелам на шесть кусков-строк. Перед этим запятые меняем на точки – в файле десятичная запятая, а float понимает только точку.

Что хранить о частице? Смотрим, что понадобится дальше: координаты $x$ и $y$ – для расстояний в $Q_1$, признак – чтобы отобрать частицы II, энергия – для кластера и для $Q_2$. Скорости и масса нужны только для того, чтобы посчитать энергию, поэтому частицу запоминаем списком из четырёх значений: [x, y, e, признак]. Дальше в коде p[0] – это $x$, p[1] – $y$, p[2] – энергия, p[3] – признак.

Кластеров четыре – значит, заводим четыре пустых списка и каждую частицу кладём в свой по append. Какой именно – решает цепочка if/elif с границами из шага 1. Границы идут по возрастанию, поэтому сравнивать надо только с верхней: до второго elif дело доходит, лишь когда первое условие не выполнилось, то есть энергия уже не меньше 3,7.

Первая частица файла: энергия 6,897 – та же, что в G1. Она не меньше 3,7 и не меньше 6,1, но меньше 8,7 – и попадает в clusters[2], третий кластер: списки нумеруются с нуля.

# Кластеров 4 – заводим 4 пустых списка
clusters = [[], [], [], []]

for line in open('demo_27.txt'):
    s = line.replace(',', '.').split()   # в файле десятичная запятая
    x = float(s[0])
    y = float(s[1])
    vx = float(s[2])
    vy = float(s[3])
    m = float(s[4])
    e = m * (vx ** 2 + vy ** 2) / 2
    p = [x, y, e, s[5]]                  # частица: x, y, энергия, признак

    # Границы сняты с графика в Calc – середины промежутков
    if e < 3.7:
        clusters[0].append(p)
    elif e < 6.1:
        clusters[1].append(p)
    elif e < 8.7:
        clusters[2].append(p)
    else:
        clusters[3].append(p)

Шаг 3. Q1 – самые далёкие частицы II в одном кластере

Переводим условие на язык циклов: «наибольшее евклидово расстояние между частицами одного кластера, имеющими признак II».

«одного кластера» – внешний цикл по кластерам, и пары составляем только внутри текущего;
«между частицами» – два вложенных цикла: a и b пробегают кластер, и так перебираются все пары;
«имеющими признак II» – у обеих частиц пары p[3] == 'II';
«наибольшее» – поиск максимума: q1 начинается с нуля и растёт, когда нашлась пара дальше.

Расстояние считаем по формуле из справки к условию, корень – это степень 0.5. Каждая пара встретится дважды, (a, b) и (b, a), а частица – ещё и в паре сама с собой, с расстоянием 0. На максимум это не влияет, так что отдельно исключать такие пары не нужно. В самом большом кластере 800 частиц, вложенный цикл сделает 640 000 шагов – это пара секунд.

# Q1: наибольшее расстояние между частицами II одного кластера
q1 = 0
for c in clusters:
    for a in c:
        for b in c:
            if a[3] == 'II' and b[3] == 'II':
                d = ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5
                q1 = max(q1, d)

Шаг 4. Центры кластеров и Q2

Центр кластера – та частица, у которой сумма модулей разностей энергий со всеми остальными наименьшая. Формулы для центра нет, поэтому пробуем в роли центра каждую частицу по очереди:

для частицы a внутренним циклом складываем abs(a[2] - b[2]) по всем частицам b кластера – это total;
если total меньше лучшей суммы best, найденной до сих пор, запоминаем и сумму, и саму частицу – center = a: нужна её энергия, а не сумма.

Это поиск минимума – зеркало поиска максимума из шага 3, но начальное значение – заведомо большое число 10 ** 9: первая же частица его побьёт. Пару частицы с самой собой исключать снова не нужно – она добавляет к сумме ноль.

$Q_2$ – наибольшая энергия среди четырёх центров, то есть поиск максимума по кластерам, как в шаге 3.

Осталось напечатать ответ. Просят целую часть произведения, поэтому int(q1 * 10000).

# Q2: центр – частица с наименьшей суммой |E - E_i| по своему кластеру
q2 = 0
for c in clusters:
    best = 10 ** 9
    for a in c:
        total = 0
        for b in c:
            total += abs(a[2] - b[2])
        if total < best:
            best = total
            center = a
    q2 = max(q2, center[2])

print(int(q1 * 10000), int(q2 * 10000))   # 539936 100704

Программа целиком

Три фрагмента подряд – это и есть решение. Программа печатает одну строку – ответ: 539936 100704.

Решение

# Кластеров 4 – заводим 4 пустых списка
clusters = [[], [], [], []]

for line in open('demo_27.txt'):
    s = line.replace(',', '.').split()   # в файле десятичная запятая
    x = float(s[0])
    y = float(s[1])
    vx = float(s[2])
    vy = float(s[3])
    m = float(s[4])
    e = m * (vx ** 2 + vy ** 2) / 2
    p = [x, y, e, s[5]]                  # частица: x, y, энергия, признак

    # Границы сняты с графика в Calc – середины промежутков
    if e < 3.7:
        clusters[0].append(p)
    elif e < 6.1:
        clusters[1].append(p)
    elif e < 8.7:
        clusters[2].append(p)
    else:
        clusters[3].append(p)

# Q1: наибольшее расстояние между частицами II одного кластера
q1 = 0
for c in clusters:
    for a in c:
        for b in c:
            if a[3] == 'II' and b[3] == 'II':
                d = ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5
                q1 = max(q1, d)

# Q2: центр – частица с наименьшей суммой |E - E_i| по своему кластеру
q2 = 0
for c in clusters:
    best = 10 ** 9
    for a in c:
        total = 0
        for b in c:
            total += abs(a[2] - b[2])
        if total < best:
            best = total
            center = a
    q2 = max(q2, center[2])

print(int(q1 * 10000), int(q2 * 10000))   # 539936 100704

Если условие другое

Каркас тот же: график, границы, раскладка частиц по кластерам и подсчёт по кластерам. Меняется то, по чему строить график, и то, что считать.

Что в условии	Что править
«кластеры – группы точек на плоскости»	график строится по столбцам A и B: выделить оба → диаграмма XY; кластеры – облака точек, граница – прямая вида `x < 3` или `y > x + 2`, раскладка – та же цепочка `if/elif`
«найдите среднее арифметическое абсцисс центров»	складывать `center[0]` в цикле по кластерам и в конце разделить на 4
«два файла, A и B»	для каждого файла свой график и свои границы, код тот же – меняются имя файла и числа в `if/elif`

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

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

Q1 по всему файлу. Пары с признаком II искали в разных кластерах, а в условии нужно «между частицами одного кластера».
Не заменили запятую. float('2,861191') падает с ValueError – десятичный разделитель в файле запятая.
Округлили вместо целой части. Просят целую часть произведения – это int(q * 10000); round может дать на единицу больше.