AbstractionПрограмёрпропущено...


может не оптимально, но просто.... делим окружность на k дуг опорными точками..., а далее в цикле (пока не закончатся точки) по принипу:
1. Ищем дугу, которая делится нашими (не опорными) точками на самые длинные промежутки (дуги)
2. Добавляем к числу точек на этой дуге ещё одну

В итоге получим k чисел, каждое соответствует числу точек на данной дуге... распределяем их равномерно по дуге (как и было сказано ранее) и ... готово :)И Вам пирожок с верхней полки.
12861765
сорри... не заметил...

Димитрий85Програмёрможет не оптимально, но просто.... делим окружность на k дуг опорными точками..., а далее в цикле (пока не закончатся точки) по принипу:
1. Ищем дугу, которая делится нашими (не опорными) точками на самые длинные промежутки (дуги)
2. Добавляем к числу точек на этой дуге ещё одну

В итоге получим k чисел, каждое соответствует числу точек на данной дуге... распределяем их равномерно по дуге (как и было сказано ранее) и ... готово :)

Не получится ли, что все наши точки напихаются в один интервал между двумя опорными, а другие интервалы окажутся не заполненными подвижными точками?

если один из интервалов будет в разы (десятки раз) больше других - то так и получится. НО... размещение точек в любом случае будет оптимальным

AbstractionПрограмёрпропущено...


если один из интервалов будет в разы (десятки раз) больше других - то так и получится. НО... размещение точек в любом случае будет оптимальнымНе всегда оптимальным. Пусть есть две точки, интервалы 1 и 1.8, мы можем добавить две точки.
Жадный алгоритм дает 0.5, 0.5, 0.9, 0.9 ("неидеальность" 0.8);
Возможен вариант 1, 0.6, 0.6, 0.6 ("неидеальность" 0.6);
Но отклонение жадного алгоритма от идеального решения легко оценивается сверху.

да... согласен))) надо проверять на 1 шаг вперёд... то есть, мы стараемся добавить 1 к каждому интервалу, и там где промежутки между точками окажутся больше (при уже добавленной точке) - туда её и добавляем... и т.д. ))) при таком алгоритме и получим именно то, что надо :)