Привет, будущие IT-гении! 👋
До ЕГЭ остаются считанные недели, и сейчас самое время прокачать свои навыки на максимум. Знаете, какое задание вызывает больше всего трепета? Конечно, это №27 — самое сложное и каверзное! 🤯
В этом году составители ЕГЭ подкинули нам новый тип 27 задания, и многие ребята просто не знают, как к нему подступиться😥 Но не паникуйте! Я подготовила для вас методичку, которая станет вашим личным пошаговым гидом по решению этих задач.
Забрать методичку вы можете здесь, а пока изучайте разбор задачи👇
Условие задачи
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров) так, что они будут лежать внутри сектора окружности радиуса R = 50 с центральным углом 20°. Гарантируется, что такое разбиение существует и единственно.
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра.
Расстояние между двумя точками на плоскости A(x1,y1) и B(x2,y2) вычисляется по формуле:
В файле А хранятся данные о звёздах трёх кластеров, для которых центром окружности является точка C (5, –9). В каждой строке записана информация о расположении на карте одной звезды: сначала координата х, затем координата у. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле Б хранятся данные о звёздах шести кластеров, для которых центром окружности является точка C (–10, –7). Известно, что количество звёзд не превышает 100 Структура хранения информации о звёздах в файле Б аналогична файлу А.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px – среднее арифметическое абсцисс центров кластеров, и Py – среднее арифметическое ординат центров кластеров.
В ответе запишите четыре числа: в первой строке сначала абсолютное значение целой части произведения Px×10000, затем абсолютное значение целой части произведения Py×10000 для файла А, во второй строке – аналогичные данные для файла B.
Возможные данные одного из файлов иллюстрированы графиком.
Ответ:
178755 2896
37392 50998
Алгоритм решения. Лучи .Файл А:
1. Откроем файл Excel и построим точечный график:
Три кластера. Все точки, игреки которых меньше -5 (оранжевая линия), принадлежат одному кластеру. Среди оставшихся двух кластеров разделение провести сложнее – делим по наклонной линии (зелёная).
Определим уравнение функции y = kx+b. Для этого возьмём две точки, через которые эта линия точно проходит: в условии сказано, что (5; -9) – центр. Вторая точка (20;15) – визуально определить не трудно. Значит, уравнение функции выглядит так: y = 1,6x -17.
Те точки, для которых выполняется неравенство y < 1,6x -17 располагаются ниже зелёной линии и принадлежат одному кластеру. Те точки, для которых выполняется неравенство y > 1,6x -17 располагаются выше зелёной линии и принадлежат другому кластеру.
2. Переходим в python. Подключаем математический модуль и функцию для нахождения расстояния между точками.
3. Связываем переменную F с файлом 27_А1.
4. Создаём массив Clasters[ [ ] , [ ] , [ ] ], в котором будут храниться координаты звёзд для каждого кластера.
5. Считываем координаты звёзд из файла и помещаем в нужную ячейку кластера Clasters. Используем алгоритм каскадного условия if-elif-else.
6. В этой задаче нужно найти центр кластера.
Создаём функцию Centr, которая получает на вход кластер. Пробегает по каждой звезде полученного кластера (стр. 18) и находит сумму расстояний от этой звезды для всех остальных звёзд кластера (стр.19). Полученную сумму, а также координаты проверяемой звезды заносит в массив min_ (стр. 20).
В результате функция Centr возвращает (стр.21) в основную программу сумму расстояний и координаты той звезды, которая является центром кластера (центр кластера - точка этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна.)
Обратите внимание на 21 строку – в основную программу я возвращаю только координаты центроида. Нас будут интересовать только координаты, сумма расстояний нам уже не интересна.
Сумма расстояний нам нужна была лишь для функции min() - поиска элемента с минимальным значением.
7. Выводим на экран среднее значение абсцисс(стр.23) и ординат (стр.24) центров двух кластеров.
Полностью программа выглядит так:
Алгоритм решения. Лучи . Файл В:
1. Откроем файл Excel и построим точечный график:
Определяем уравнение функций y = kx+b через тангенс угла наклона и точку пересечения с осью Оу.
Напоминаю курс математики 9-класса на примере наиболее сложной наклонной.
K = -2,4; b = -30; y = -2,4x – 30
2. Переходим в python. Подключаем математический модуль и функцию для нахождения расстояния между точками.
3. Связываем переменную F с файлом 27_В1.
4. Создаём массив Clasters[ [ ] , [ ] , [ ] , [ ] , [ ] , [ ] ], в котором будут храниться координаты звёзд для каждого кластера.
5. Считываем координаты звёзд из файла и помещаем в нужную ячейку кластера Clasters. Используем алгоритм каскадного условия.
6. В этой задаче нужно найти центр кластера – алгоритм нахождения описан в задаче №1. Здесь размещу лишь код. Обратите внимание на 21 строку – в основную программу я возвращаю только координаты центроида. Нас будут интересовать только координаты, сумма расстояний нам уже не интересна.
7. Выводим на экран среднее значение абсцисс(стр.31) и ординат (стр.32) центров двух кластеров.
Полностью программа выглядит так:
--------------------------------------------
Появились вопросы? Спрашивайте в комментариях.
Понравилась статья? Тогда ставьте лайк👍 и переходите к следующей статье!
Ваш репетитор по информатике, Елена Синягова
--------------------------------------------
Читай и другие мои статьи
Когда начинать готовиться к ЕГЭ по информатике
Как выбрать направление в IT
Как разобраться в IT-специальностях при поступлении в вуз
IT профессии: чем отличаются, в чем специфика, что перспективнее?
Топ-10 лучших IT-вузов России
Решаем 26 задания