Димитрий85,

Преобразуйте в полярные координаты, делов-то. Дальше берем пары ("дуга", "число фрагментов, образуемых дополнительными точками"), на каждом шаге находим пару с максимальной результирующей дугой и добавляем точку.

Димитрий85,

Вот тянет написать свое предыдущее сообщение еще раз, ей-же-ей.
Соображение номер раз: если между двумя заданными точками поставлено несколько "наших", их расстановка с равными интервалами даст результат не менее равномерный в указанном смысле.
Соображение номер два: тогда у нас есть множество интервалов, по которым надо распределить N точек; если на интервал длины d _i выставлено a _i точек, результирующие дуги на этом интервале равны d _i /a _i .
Соображение номер три: жадный алгоритм в нашем случае подходит достаточно хорошо. Дает ли он всегда аналитически оптимальное решение, предлагаю выяснить самостоятельно - это же Ваша задача, в конце концов.

Димитрий85 Abstraction,
спасибо за ваши выкладки. Соображения понятны и очевидны.
Однако у меня в стартовом сообщении был ключевой вопрос ,вызвавший у меня затруднения, - как пройти по циклу, как перебрать именно комбинации "каждое расположение наших точек" с "каждым расположением опорных".Первый ответ: этого следует избегать, так как там С _N+n-1 ^N вариантов, причем уйма заведомо неоптимальных.
Второй ответ: для построения цикла достаточно проанализировать, как была получена формула в первом ответе.

Димитрий85,

Да. Именно в этом предположении и были даны ответы.

Димитрий85AbstractionДимитрий85,

Да. Именно в этом предположении и были даны ответы.

Так перебрать-то как )Это Вам надо или мне?

ПрограмёрДимитрий85Спасибо всем ответившим.
просто стало интересно)) представим что в задаче дано 2 точки, которые делят нашу окружность на 2 равные полуокружности....
нам надо добавить ещё 3 точки )) какой из вариантов распределения более равномерный?(в соотношениях длин дуг между точками):
1) 1:1:1:1,5:1,5
2) 1:1:1:1:2
3) 0,1 1,4 1,5 1,5 1,5

подскажите как вы считаете :)По данному в первом посте описанию (и принимая окружность за 6), "неравномерность":
1) 1.2
2) 1.6
3) 2.2

ПрограмёрmiksoftПродолжаю мысль - тогда "подвижные" точки есть смысл размещать только равномерно на каждом отрезке дуги между "неподвижными". Тогда задача сводится к решению вопроса "сколько напихать точек в тот или иной интервал". Другими словами - найти способ разделения N точек на K групп.

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

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

ПрограмёрДимитрий85пропущено...


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

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