|
Компьютерный форум OSzone.net » Программирование, базы данных и автоматизация действий » Программирование и базы данных » Разное - Помогите алгоритм составить |
|
Разное - Помогите алгоритм составить
|
Новый участник Сообщения: 2 |
Выбрать три различные точки из заданного множества точек на плоскости так, чтобы была минимальной разность между
колличествами точек, лежащих внутри и вне треугольника с вершинами в выбранных точках помогите выложите алгоритм а то яне шарю в этом |
|
Отправлено: 21:48, 23-12-2008 |
![]() Ветеран Сообщения: 1180
|
Профиль | Отправить PM | Цитировать Полным перебором очень долго будет. Предлагаю так: Пусть есть N точек, тогда найти такие треугольники, внутри которых abs(количество_точек - (N-3)/2) -> min. Дальше можно уменьшить количество переборов следующим образом:
1. Есть множество точек point[i]. Перебираем точки №1 и №2 чтоб были неодинаковые point[i]!=point[j], а вот точку №3 - чтобы съэкономить время выбираем хитрым образом. 2. Держим 2 сортированных списка - по тангенсу угла A при точке №1 и тангенсу угла B при точке №2. 2.1. Берём минимальный тангенс A, делаем во втором списке (N-3)/2 шагов (если столько возможно), так чтобы угол A был не меньше начального. Запомнили точку, посчитали сколько осталось шагов (K1 = количество_точек - (N-3)/2). 2.2. Двигаемся по первому списку, если K1>0, тогда уменьшаем A при не меньшем B, иначе увеличиваем. Потом по списку B так же, и так далее, пока не проползём все списки. 2.3. По пути запоминаем наилучшый достигнутый результат. Таким образом, мы пройдём все "лучшие" варианты с точкой №3. Причём путь будет всегда близко к дуге, на которой количество точек внутри примерно (на сколько это возможно) равно (N -3)/2 |
Отправлено: 10:05, 24-12-2008 | #2 |
Для отключения данного рекламного блока вам необходимо зарегистрироваться или войти с учетной записью социальной сети. Если же вы забыли свой пароль на форуме, то воспользуйтесь данной ссылкой для восстановления пароля. |
Новый участник Сообщения: 2
|
Профиль | Отправить PM | Цитировать Мне надо схему структурного программирования
|
Отправлено: 10:26, 28-12-2008 | #3 |
![]() Ветеран Сообщения: 1180
|
Профиль | Отправить PM | Цитировать блок-схему чтоль? а алгоритм попроще можно выбрать? (будет работать долго на больших данных)
|
Отправлено: 22:00, 28-12-2008 | #4 |
![]() |
Участник сейчас на форуме |
![]() |
Участник вне форума |
![]() |
Автор темы |
![]() |
Сообщение прикреплено |
| |||||
Название темы | Автор | Информация о форуме | Ответов | Последнее сообщение | |
CMD/BAT - Составить скрипт с условием | Firebolt | Скриптовые языки администрирования Windows | 27 | 14-07-2011 23:59 | |
C/C++ - помогите откомпилировать либо найти рабочий код! (алгоритм LZW) | stas_newar | Программирование и базы данных | 6 | 14-11-2009 15:37 | |
Составить Классификацию уязвимостей СУБД. | Morsel | Хочу все знать | 1 | 04-06-2009 16:22 | |
Прочие БД - Составить Классификацию уязвимостей СУБД. | Morsel | Программирование и базы данных | 1 | 04-06-2009 16:20 | |
Алгоритм | pauluss | Программирование и базы данных | 1 | 06-10-2006 10:53 |
|