Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Алгоритмы
Перезагрузить страницу Интересная задача как создать алгоритм данных на вычисление
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
ЕкатеринаАК ЕкатеринаАК вне форума
Новичок
 
Сообщений: 6
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 04.12.2005
По умолчанию Интересная задача как создать алгоритм данных на вычисление - 04.12.2005, 01:22

Помогите разработать алгоритм решения следующей задачи
Постановка:
Дано множество точек, каждая из которых определяется двумя координатами (х,у). Необходимо найти прямую, на которой расположено максимальное количество точек из заданного множества.
Ответить с цитированием
  (#2 (permalink)) Старый
Dian Dian вне форума
Member
 
Сообщений: 5,243
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2004
По умолчанию 04.12.2005, 12:34

Простое решение "в лоб": для каждой пары точек - счетчик лежащих на ней точек. небыстрый метод: мало того, что все пары перебирать, ещё и для каждойц пары проверять все точки.
Ответить с цитированием
  (#3 (permalink)) Старый
Gorbach Gorbach вне форума
Member
 
Сообщений: 67
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 27.10.2005
По умолчанию 05.12.2005, 03:26

По-мойму, все точки у которых отношение y/x одинаковые лежат на одной прямой.
Поправте если ошибаюсь и приведите опровергающий пример.
Ответить с цитированием
  (#4 (permalink)) Старый
Gorbach Gorbach вне форума
Member
 
Сообщений: 67
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 27.10.2005
По умолчанию 05.12.2005, 04:58

Поправляю сам себя.
В случае если у двух и более точек координата x или y постоянна, то можно с увереностью говорить, что эти точки лежат на одной прямой (отношение координат в этом случае не одинаково).
Соответственно проверка на отношение y/x и постоянство одной из координат дадут нам точки лежащие на одной прямой.
Ответить с цитированием
  (#5 (permalink)) Старый
Alexiski Alexiski вне форума
Любитель давать советы
 
Сообщений: 4,274
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 05.12.2005, 09:38

Неправда ваша. Если прямая не проходит через начало координат то не так.

Условие: (X1-X2)*(Y2-Y3) == (Y1-Y2)*(X2-X3)
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Gorbach Gorbach вне форума
Member
 
Сообщений: 67
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 27.10.2005
По умолчанию 05.12.2005, 10:51

Правда Ваша, ляпнул не подумал (точнее подумал, но понедельник - думкалка не работает).
Конечно dX/dY должно быть одинаковым.
Ответить с цитированием
  (#7 (permalink)) Старый
ЕкатеринаАК ЕкатеринаАК вне форума
Новичок
 
Сообщений: 6
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 04.12.2005
По умолчанию 05.12.2005, 18:37

А есть какое-то другое решение данной задачи, более оптимальное?
Ответить с цитированием
  (#8 (permalink)) Старый
Dian Dian вне форума
Member
 
Сообщений: 5,243
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2004
По умолчанию 06.12.2005, 04:21

Цитата:
Originally posted by ЕкатеринаАК
[b]А есть какое-то другое решение данной задачи, более оптимальное?
Оно действительно нужно?
Ответить с цитированием
  (#9 (permalink)) Старый
ЕкатеринаАК ЕкатеринаАК вне форума
Новичок
 
Сообщений: 6
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 04.12.2005
По умолчанию 06.12.2005, 12:07

Я уже решила задачу выше проедложенным способом. Теперь мне необходимо оптимизировать программу, но не путем ее чистки, а перепрограммировать. Для этого и нужен более оптимальлный вариант решения данной задачи, если он существует.
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Задача Прима-Краскала (“жадный” алгоритм) Dem Prolog 13 21.03.2012 22:51
Задача на вычисление количества дней с отрицательной температурой на С++ кэп Вопросы начинающих программистов 5 29.07.2011 19:41
Задача на вычисление процентной ставки в банке и уровня инфляции Elena1026 Вопросы начинающих программистов 0 18.02.2011 08:49
интересная задача n-andriy Pascal 3 24.06.2010 12:04
Как создать алгоритм LZW Jenton Общие вопросы создания ПО 1 15.12.2009 18:26
Переборный алгоритм как его создать Y_Vetal Алгоритмы 3 28.02.2009 10:56
Задача коммивояжера где найти алгоритм 2D_UFO Алгоритмы 23 11.01.2008 09:24
Интересная задача о КОНВЕРТЕ Адиль Prolog 24 20.12.2007 21:45
Задача Прима-Крскала (жадный алгоритм) mickey Prolog 2 22.10.2007 13:19
Интересная задача!!!!! С ++ eugene С/С++ 0 23.06.2007 18:24
задача - вычисление суммы двух нечетких чисел AlexMaa Prolog 3 27.04.2006 05:28
Как создать алгоритм imported_stayer Prolog 7 11.06.2004 02:46



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов