Статья Автор: Лебедев Дмитрий

(The Last Inch) КЕГЭ- 27. Модель решения - Копия

Приведем стандартную схему решения в виде программы с подпрограммами

from turtle import * # импорт модуля Черепашки
def pokraska(Kl, icol):
# раскраска списка точек Kl в цвет с номером icol
pass
def fA(pos) :
# определение для pos номера Кластера (файл A)
return 0
def fB(pos) :
# определение для pos номера Кластера (файл B)
return 0
def centroid(Kl):
# программа поиска центроида/антицентроида Кластера Kl
return Kl[0], 0 # возврат двух переменных - точки и значения для неёl

# ОСНОВНАЯ ПРОГРАММА
dk = {i:[] for i in range(5)} # создание словаря Кластеров (5 штук или более)
#fname = 'fz_27A_trV01.txt' # выбираем необходимое
fname = 'fz_27B_trV01.txt'

for s in open(fname): # чтение данных и разбиение на класстеры
s = s.replace(',','.') # замена запятой на точку
x,y = map(float,s.split()) # выделение координат
#i = fA((x,y)) # определяем номер Кластера (если файл A)
i = fB((x,y)) # определяем номер Кластера (если файл B)
dk[i].append((x,y)) # добавляем точку в выбранный Кластер

n, sx,sy = 0, 0 , 0 # инициализация ответов и числа Кластеров
for k in dk : # пробег по номерам Кластеров
if len(dk[k]) == 0 : continue # пропуск пустых
Kl = dk[k] # список точек Кластера
pokraska(Kl,k) # раскраска Кластера
ans, rans = centroid(Kl) # получение ответа для Кластера
n,sx,sy = n+1, sx + ans[0], sy +ans[1] # вычисление итогов
print(k, len(Kl), ans, rans) # печать характеристик

print((sx/n)*10000,(sy/n)*10000) # вывод результатов

Это шаблон программы, подходящий под любую формулировку.
Далее дописываем программу pokraska (делаем запуск)
Открыв файл в EXCEL дописываем программы fA/fB (делаем запуск для просмотра раскраски)
Дописываем программу centroid, для чего создаем подпрограммы dist и sumdist и делаем окончательный запуск

Программа pokraska может быть следующей:

from turtle import * # импорт модуля Черепашки
def pokraska(Kl, icol):
# раскраска списка точек Kl в цвет icol
m = 10 # масштаб - нужно подобрать удобный
r = 3 # размер точки - тоже можно подобрать удобный
colors = ['red','green','blue','orange','black'] # список цветов
clr = colors[icol] # выбор цвета
tracer(0) # отключаем прорисовку (для ускорения)
up() # поднимаем перо
for pos in Kl : # перебираем точки списка
goto(pos[0]*m, pos[1]*m) # переход в точку с учетом масштаба
dot(r,clr) # рисуем точку заданным цветом и радиусом
update() # обновляем рисунок
pass

При необходимости легко можно организовать сдвиг рисунка переносом центра координат

Посмотрев на рисунок и диаграмму в EXCEL можно определить правила для разбиения на кластеры и написать программу fB:

def fB(pos) :
# определение для pos номера Кластера (файл B)
if pos[1] < 10 : # отбор в кластер № 1 по линии y = 10
return 1
if pos[0] < 17 : # отбор в кластер № 2 по линии x = 17 (формально по условию x<17 and y >= 10)
return 2
return 0 # оставшееся в кластер № 0

Просмотрев результат запуска увидим, что все сделано верно.
Можно сразу проверить и разбиение для файла A.

def fA(pos) :
# определение для pos номера Кластера (файл B)
if pos[1] < 9 : # отбор в кластер № 1 по линии y = 9
return 1
return 0 # оставшееся в кластер № 0

Для программы centroid разумно добавить программы вычисления расстояния dist и суммы расстояний sumdist
(хотя программа определения расстояния и есть в библиотеке math, рекомендуем написать её самостоятельно - это несложно)

def dist(d1,d2):
# вычисление расстояния между точками по первым двух параметрам
r = (d1[0]-d2[0])**2 + (d1[1]-d2[1])**2
return r**0.5
def sumdist(pos,Kl):
# вычисление суммы расстояний от точки pos до всех точек списка Kl
r = 0
for d in Kl :
r += dist(pos,d)
return r
def centroid(Kl):
# программа поиска центроида/антицентроида Кластера Kl
ans, rans = Kl[0], sumdist(Kl[0], Kl) # инициализация ответа начальной точкой
for pos in Kl : # перебор точек кластера
r = sumdist(pos, Kl)
if r < rans : # условие для поиска центроида
#if r > rans : # условие для поиска антицентроида
ans, rans = pos, r # фиксация лучшего результата
return ans, rans # возврат результатов

Финальный запуск для файлов A, B и заполнение результатов.
Ниже текст программы без комментариев и только для файла B.

Из-за технических проблем реализации Черепашки в тетради, блок работы с Черепашкой и её вызов убраны в комментарий

'''
from turtle import * 
def pokraska(Kl, icol):
    m, r = 10, 3
    colors = ['red','green','blue','orange','black'] 
    clr = colors[icol] 
    tracer(0); up()
    for pos in Kl : 
        goto(pos[0]*m, pos[1]*m) 
        dot(r,clr) 
    update() 
'''
def fB(pos) :
    if pos[1] < 10 : return 1
    if pos[0] < 17 : return 2
    return 0
def dist(d1,d2):
    return ((d1[0]-d2[0])**2 + (d1[1]-d2[1])**2) ** 0.5
def sumdist(pos,Kl):
    return sum(dist(pos, d) for d in Kl)
def centroid(Kl):
    ans, rans = Kl[0], sumdist(Kl[0], Kl)
    for pos in Kl :
        r = sumdist(pos, Kl)
        if r < rans : 
            ans, rans = pos, r 
    return ans, rans
dk = {i:[] for i in range(5)} 
fname = 'fz_27B_trV01.txt'
for s in open(fname): 
    s = s.replace(',','.') 
    x,y = map(float,s.split()) 
    i = fB((x,y))
    dk[i].append((x,y)) 
n, sx,sy = 0, 0 , 0 
for k in dk : 
    if len(dk[k]) == 0 : continue 
    Kl = dk[k] 
    #pokraska(Kl,k) 
    ans, rans = centroid(Kl)
    n,sx,sy = n+1, sx + ans[0], sy +ans[1] 
    print(k, len(Kl), ans, rans) 
print((sx/n)*10000,(sy/n)*10000)

Прикрепленные файлы
27B.txt

Печать