ЕГЭ · ЗАДАНИЕ 27
Анализ данных и кластеризация · практика 16
Энергии частиц: 20, 21, 23, 30, 31, 33. Примените алгоритм: отсортируйте энергии, возьмите минимальную оставшуюся и включите в группу все оставшиеся частицы с энергией не более чем на 3 выше неё. Повторяйте до исчерпания частиц. Центр группы — частица с минимальной суммой модулей разностей энергий внутри группы; при равенстве выбирается меньшая энергия. Запишите число групп и максимальную энергию среди центров.
Учебная модель Академии С для проверки приёма. Не выдаётся за задание реального экзамена.
Источник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 2 31
Решение по шагам
- Границу группы отсчитываем от её минимальной энергии, а не от последнего добавленного элемента.
- Получаем группы: 20, 21, 23; 30, 31, 33. В каждой разность максимума и минимума не превышает 3.
- В группе из трёх отсортированных значений сумма модулей отклонений минимальна на среднем значении. Центры: 21, 31.
- Число групп: 2. Наибольший центр: 31. Ответ: 2 31.
| Группа | Кандидат в центр | Сумма отклонений |
|---|---|---|
| 1 | 20 | 4 |
| 1 | 21 | 3 |
| 1 | 23 | 5 |
| 2 | 30 | 4 |
| 2 | 31 | 3 |
| 2 | 33 | 5 |
Проверка на Python
energies = [20, 21, 23, 30, 31, 33]
groups = []
for value in sorted(energies):
if not groups or value - groups[-1][0] > 3:
groups.append([value])
else: groups[-1].append(value)
centers = [min(g, key=lambda x: (sum(abs(x-y) for y in g), x)) for g in groups]
print(len(groups), max(centers))