Имя пользователя:
Пароль:  
Помощь | Регистрация | Забыли пароль?  | Правила  

Компьютерный форум OSzone.net » Программирование, базы данных и автоматизация действий » Программирование и базы данных » Разное - Помогите алгоритм составить

Ответить
Настройки темы
Разное - Помогите алгоритм составить

Новый участник


Сообщения: 2
Благодарности: 0

Профиль | Отправить PM | Цитировать


Выбрать три различные точки из заданного множества точек на плоскости так, чтобы была минимальной разность между
колличествами точек, лежащих внутри и вне треугольника с вершинами в выбранных точках

помогите выложите алгоритм а то яне шарю в этом

Отправлено: 21:48, 23-12-2008

 
pva pva вне форума

Аватара для pva

Ветеран


Сообщения: 1180
Благодарности: 279

Профиль | Отправить 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
Благодарности: 0

Профиль | Отправить PM | Цитировать


Мне надо схему структурного программирования

Отправлено: 10:26, 28-12-2008 | #3

pva pva вне форума

Аватара для pva

Ветеран


Сообщения: 1180
Благодарности: 279

Профиль | Отправить PM | Цитировать


блок-схему чтоль? а алгоритм попроще можно выбрать? (будет работать долго на больших данных)

Отправлено: 22:00, 28-12-2008 | #4



Компьютерный форум OSzone.net » Программирование, базы данных и автоматизация действий » Программирование и базы данных » Разное - Помогите алгоритм составить

Участник сейчас на форуме Участник сейчас на форуме Участник вне форума Участник вне форума Автор темы Автор темы Шапка темы Сообщение прикреплено

Похожие темы
Название темы Автор Информация о форуме Ответов Последнее сообщение
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




 
Переход