Поиогите сломать рбалденную задачу
Помогите пожалуйсто, она мне уже все мозги выпарила, а не получается. Может кто сможет её сделать помогите, а то у меня с ней не выходит вообще ни фига.
Вот условие для смелых и кто не откажет помочь:
Выбрать три разные точки заданного на плоскости множества точек, составляющие треугольник наибольшего периметра.
Вот условие для смелых и кто не откажет помочь:
Выбрать три разные точки заданного на плоскости множества точек, составляющие треугольник наибольшего периметра.
Ничего кроме перебора в голову, чесно говоря, не приходит. :)
Да у нас перепод сам не в паскале не в делфи не шарит. Он говорит что проверить легче чам составить. А у меня на счёт этой задачи вообще мысли путём не складываются. Так что она у меня не работает
салам ребяты.
вот подумал немного (может надо было больше :o )
вот такое решение, посмотри подойдёт ли . . .
я понял так: из всех заданных точек надо выбрать так, чтобы периметр был максимален.
значит надо выбрать максимально верхнюю, нижнюю,левую,правую точки. получается 4 точки, а нам надо 3, поэтому из этих точек надо убрать такую точку, при которой периметр треугольника из остальных
3-х точек будет максимально большим. Для этого думаю уже только перебор поможет. по теореме Пифагора надо найти все стороны, а потом сравнить все периметры образующихся треугольников.
(задача усложняется тем, что если максимально верхняя точка не одна, а 2,3,4...) причем насколько я это себе представляю очень сильно усложняется. там уже надо использовать кое- что другое.
если что, пиши. подробно попишу :cool:
вот подумал немного (может надо было больше :o )
вот такое решение, посмотри подойдёт ли . . .
я понял так: из всех заданных точек надо выбрать так, чтобы периметр был максимален.
значит надо выбрать максимально верхнюю, нижнюю,левую,правую точки. получается 4 точки, а нам надо 3, поэтому из этих точек надо убрать такую точку, при которой периметр треугольника из остальных
3-х точек будет максимально большим. Для этого думаю уже только перебор поможет. по теореме Пифагора надо найти все стороны, а потом сравнить все периметры образующихся треугольников.
(задача усложняется тем, что если максимально верхняя точка не одна, а 2,3,4...) причем насколько я это себе представляю очень сильно усложняется. там уже надо использовать кое- что другое.
если что, пиши. подробно попишу :cool:
Я примерно так и пробовал, но у меня какая то фигн получается.
Если что то можно по подробнее?
Если что то можно по подробнее?
Для точек, что на картинке по алгоритму KeYZeD-а будет построен зеленый треугольник, хоть желтый имеет больший периметр.
Как решал бы я подобную задачу.
Нашел бы центр масс. Это просто.
Рассчитал бы для каждой точки расстояние до центра, занес бы все в массив и упорядочил бы его по убыванию.
Теоретически, первый элемент - одна из искомых вершин.
Далее можно разбить на два множества оставшиеся точки - которые по разные стороны прямой между первым элементом и центром масс.
Ну а дальше перебор или... Или рассматривать прямоугольные треугольники, где гипотенуза есть прямая от первой точки до рассматриваемой, а третья точка - в основании прямой, опущенной из рассматриваемой точки к прямой от точки начальной до центра масс и составляющая с ней прямой угол. Данные треугольники отсортировать на предмет убывания периметра. Выборок будет две - по разные стороны от прямой - центр масс начальная точка. Найденные два треугольника и будут содержать дополнительно две искомые точки. Возможно решение не самое точное, но, при большом наборе точек должно значительно сократить время рассчетов и выдать неплохой результат. :)
Задача очень заинтересовала меня.
Нашел бы центр масс. Это просто.
Рассчитал бы для каждой точки расстояние до центра, занес бы все в массив и упорядочил бы его по убыванию.
Теоретически, первый элемент - одна из искомых вершин.
Далее можно разбить на два множества оставшиеся точки - которые по разные стороны прямой между первым элементом и центром масс.
Ну а дальше перебор или... Или рассматривать прямоугольные треугольники, где гипотенуза есть прямая от первой точки до рассматриваемой, а третья точка - в основании прямой, опущенной из рассматриваемой точки к прямой от точки начальной до центра масс и составляющая с ней прямой угол. Данные треугольники отсортировать на предмет убывания периметра. Выборок будет две - по разные стороны от прямой - центр масс начальная точка. Найденные два треугольника и будут содержать дополнительно две искомые точки. Возможно решение не самое точное, но, при большом наборе точек должно значительно сократить время рассчетов и выдать неплохой результат. :)
Задача очень заинтересовала меня.
Спасибо за подсказки, теперь должно получиться!
[QUOTE=Мerlin]Для точек, что на картинке по алгоритму KeYZeD-а будет построен зеленый треугольник, хоть желтый имеет больший периметр.[/QUOTE]
:o :o :o
действительно, роль играет расстояние до возможной окружности, а не максимальное расстояние.
:o :o :o
действительно, роль играет расстояние до возможной окружности, а не максимальное расстояние.
Мне всегда было интересным где можно применить знания по геометрии. Существует в учебнике множество задачек на вычисление разных данных, но очень редко приводится пример, где это может быть использовано. Вот решение подобной задачи где можно использовать ?
Можно
1. построить выпуклый многоугольник, с помощью крайних точек
2. удалить все точки, которые внутри многоугольника
и или полный перебор в оставшихся точках
или не исключено, что в таком многоугольнике максимальным треугольником будет, треугольник, который содержит 2 точки, расстояние между которыми максимально, плюс точка, которая находится на макс.растоянии от линии обр.этими двумя точками.
2SABROG Мне пришлешь писать прогу для генерации управляющих программ для станка с электроэризионной резьбой. Там нужно было знание геометрии, особенно построение на плоскости с помощью линейки и циркуля, так как тригонометрические ф-ии не всюду определены, поэтому они не применимы.
1. построить выпуклый многоугольник, с помощью крайних точек
2. удалить все точки, которые внутри многоугольника
и или полный перебор в оставшихся точках
или не исключено, что в таком многоугольнике максимальным треугольником будет, треугольник, который содержит 2 точки, расстояние между которыми максимально, плюс точка, которая находится на макс.растоянии от линии обр.этими двумя точками.
2SABROG Мне пришлешь писать прогу для генерации управляющих программ для станка с электроэризионной резьбой. Там нужно было знание геометрии, особенно построение на плоскости с помощью линейки и циркуля, так как тригонометрические ф-ии не всюду определены, поэтому они не применимы.
Я скоро сдохну с этой задачей, т.к. вместо того чтобы показывать наибольший треугольник, она просто берёт первые три точки и соединяет их в треугольник.
:)
Вообще с обходом всего множества с составлением выпуклого многоугольника - оптимальный вариант. Все три точки будут на вершинах - однозначно.
Настолько заинтересовала идея, что я написал на Дельфи 7 программу обхода множества по периметру. Добавить цикл перебора для 20-30 точек периметра это дело нескольких минут. Если нужно - могу поделиться :)
Вообще с обходом всего множества с составлением выпуклого многоугольника - оптимальный вариант. Все три точки будут на вершинах - однозначно.
Настолько заинтересовала идея, что я написал на Дельфи 7 программу обхода множества по периметру. Добавить цикл перебора для 20-30 точек периметра это дело нескольких минут. Если нужно - могу поделиться :)
Вариант с перебором не катит - на 10 000 точек любой комп просто остановится на час. Если с обходом периметра - доли секунды.
Вообще я не против если ты дашь мне эту задачу. Если дашь то большое спасибо, ну просто очень большое.! И если сможешь то упакуй исходники в архив.
Вот проект. Для D7.
Первая кнопель - генерит случайным образом точки, что бы в пространстве они располагались не сильно "квадратно" берется сумма от нескольких рандомов. Для удобства все точки сортируются по возростанию по X. Используется быстрая сортировка. Потом процедура обхода по периметру с записью в отдельный массив и отображение полученных результатов. Вторая кнопель - перебор из точек периметра треугольников с максимальным периметром.
Третья - полный перебор всего множества - не рекомендую делать на больших наборах (если не собираетесь жить вечно :) )
В самом начале (29 строка) задана константа MaxNum = 500 ; здесь 500 - количество точек, если не пользоваться полным перебором, то можно ставить до 10 000. Дальше нужно изменять процедуру отрисовки - перерисовывать столько точек долго.
Буду рад лестным отзывам и критике :)
Первая кнопель - генерит случайным образом точки, что бы в пространстве они располагались не сильно "квадратно" берется сумма от нескольких рандомов. Для удобства все точки сортируются по возростанию по X. Используется быстрая сортировка. Потом процедура обхода по периметру с записью в отдельный массив и отображение полученных результатов. Вторая кнопель - перебор из точек периметра треугольников с максимальным периметром.
Третья - полный перебор всего множества - не рекомендую делать на больших наборах (если не собираетесь жить вечно :) )
В самом начале (29 строка) задана константа MaxNum = 500 ; здесь 500 - количество точек, если не пользоваться полным перебором, то можно ставить до 10 000. Дальше нужно изменять процедуру отрисовки - перерисовывать столько точек долго.
Буду рад лестным отзывам и критике :)
Спасибо. Я ещё пока её не смотрел, но как посмотрю, сразу же и напишу.
Неплохо. Даже очень неплохо.
И по просьбе трудящихся, чуть-чуть критики. :)
Использование, Round() imho лишнее,
особенно, что могут быть такие входные данные,
что из-за Round, будет найден не треугольник с
макс. периметром.
Напр.
точки (ABC)
|AB| = 12.5
|AC| = 12.5
|BC| = 12.5
Периметр = 37.5
Твоя прога вычислит, что периметр = 36.
точки (DEF)
|DE| = 12.51
|DF| = 12
|EF| = 12
Периметр = 36.51
Твоя прога вычислит, что периметр = 37.
И получится, что макс. периметр у DEF.
И Round() в CalkLine тоже вносит погрешности, из-за
которого может получиться, что некоторая точка
попадет за пределы выпуклого многоугольника.
На рисунке такой случай. Получается если
1. не вызывать Randomize().
2. Вычислять точки по формуле
PointArray.X := 40 + RandomRange(0,MaxX div 5);
PointArray.Y := 40 + RandomRange(0,MaxY div 5);
3. И нажать на Сгенерировать 5 раз.
Длину можно бы вичислять по формуле,
(x1-x2)^2 + (y1-y2)^2
А точную длину с исп. sqrt(), вычислить, только один раз для
треугольника с макс. периметром.
Несовсем понятен смысл определения
XMa и Xmi в процедуре Sort.
Но все это мизер. Программа действительно хороша.
И по просьбе трудящихся, чуть-чуть критики. :)
Использование, Round() imho лишнее,
особенно, что могут быть такие входные данные,
что из-за Round, будет найден не треугольник с
макс. периметром.
Напр.
точки (ABC)
|AB| = 12.5
|AC| = 12.5
|BC| = 12.5
Периметр = 37.5
Твоя прога вычислит, что периметр = 36.
точки (DEF)
|DE| = 12.51
|DF| = 12
|EF| = 12
Периметр = 36.51
Твоя прога вычислит, что периметр = 37.
И получится, что макс. периметр у DEF.
И Round() в CalkLine тоже вносит погрешности, из-за
которого может получиться, что некоторая точка
попадет за пределы выпуклого многоугольника.
На рисунке такой случай. Получается если
1. не вызывать Randomize().
2. Вычислять точки по формуле
PointArray.X := 40 + RandomRange(0,MaxX div 5);
PointArray.Y := 40 + RandomRange(0,MaxY div 5);
3. И нажать на Сгенерировать 5 раз.
Длину можно бы вичислять по формуле,
(x1-x2)^2 + (y1-y2)^2
А точную длину с исп. sqrt(), вычислить, только один раз для
треугольника с макс. периметром.
Несовсем понятен смысл определения
XMa и Xmi в процедуре Sort.
Но все это мизер. Программа действительно хороша.
Спасибо за критику. Согласен, некоторые подобные ошибки нужно обходить на автомате. Урок мне на будущее - не спешить, дабы избегать досадные ляпы. В следующем интересном алгоритме для подобной "рбалденной задачи" (с) попробую избежать этого. :)
Да, же если так, то прога всё равно получилась классная. Я например почти всегда пользуюсь генератором, так как мне лень, что либо печатать. Ещё раз Спасибо.
[QUOTE=sevelin]Да, же если так, то прога всё равно получилась классная. Я например почти всегда пользуюсь генератором, так как мне лень, что либо печатать. Ещё раз Спасибо.[/QUOTE]
Вам спасибо - процесс реализации алгоритмов меня увлек - давно так не увлекался. :)
Вам спасибо - процесс реализации алгоритмов меня увлек - давно так не увлекался. :)