Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Общие вопросы по программированию, компьютерный форум
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 18.02.2022, 21:20   #1
timaslov
Новичок
Джуниор
 
Регистрация: 18.02.2022
Сообщений: 1
По умолчанию Найти треугольники с максимальной площадью

Задача: Дано 3n точек на плоскости, причем никакие три из них не лежат на одной прямой. Построить множество n треугольников с вершинами в этих точках так, чтобы никакие два треугольника не пересекались и не содержали друг друга, а суммарная площадь этих треугольников была максимальной.
Пытаюсь найти правильный подход к задачке.
Я начал решать в лоб: сначала прохожусь по всем точкам и записываю в двумерный массив все возможные треугольники.
То есть если дано 6 точек, то начало массива будет выглядеть так: [[0,1,2], [0,1,3], [0,1,4], [0,1,5], [0,2,3], [0,2,4], и т.д., где цифры в массиве - это индексы известных нам точек. Для 6 точек получается 20 разных треугольников. Для 9 точек - 84 треугольника и т.д.
Далее нужно, насколько я понимаю, сравнить каждый треугольник с каждым, чтобы выявить, какие 2 треугольника (в случае 6 точек) имеют наибольшую площадь и при этом не пересекаются. (в случае 9и точек нужно сравнить все тройки треугольников и т.д.) Я это реализую с помощью рекурсивной функции и получается, что для 20 треугольников будет 190 итераций (комбинаторика, сочетания из двадцати по два).
Но проблема в том, что если точек будет 9, то будет 84 возможных треугольника и уже 95284 итераций (84 по 3) и для 12 точек будет 220 треугольников и 94.966.795 итераций (220 по 4). А 15 точек программа уже вовсе не посчитает за адекватное время.
И вот проблема в том, что программа не должна крашиться уже на 15ти точках.
Я понимаю, что такой подход, по всей видимости, неправильный, но иного решения пока в голову не пришло
Не кидаю код, потому что прошу подсказать именно подход к задаче
timaslov вне форума Ответить с цитированием
Старый 19.02.2022, 00:06   #2
сфинкс
Форумчанин
 
Аватар для сфинкс
 
Регистрация: 17.06.2012
Сообщений: 954
По умолчанию

Программа рассчитывает площади N 3-угольников
причём в автокад autocad совместимой программе проверил: правильно

Код:
N = 5: DIM x(N,4),y(N,4),d(N,4),s(N): RANDOMIZE TIMER '3ki.bas
FOR i = 1 TO N: FOR j = 1 TO 3
        x(i,j) = INT(RND * 9)+1: y(i,j) = INT(RND * 9)+1
NEXT: x(i,4) = x(i,1): y(i,4) = y(i,1): NEXT

FOR i = 1 TO N: FOR j = 1 TO 3: ' PRINT i,j
        d(i,j) = SQR((x(i,j+1)-x(i,j))^2+(y(i,j+1)-y(i,j))^2) ': PRINT d(i,j)
NEXT: NEXT

FOR i = 1 TO N
    p = (d(i,1)+d(i,2)+d(i,3))/2
    s(i) = SQR(p*(p-d(i,1))*(p-d(i,2))*(p-d(i,3)))
    PRINT x(i,1); y(i,1),x(i,2); y(i,2),x(i,3); y(i,3),s(i)
NEXT
из qb64 qbasic на другие языки переводим сами

чтобы перейти от N 3-угольников ко всем 3-кам из N точек
видимо нужно поменять циклы наверняка оставив принцип
x(т.1,т.2,т.3), y(т.1,т.2,т.3) d(т.1,т.2,т.3) и массив площадей

формула подсчёта 3-ков из N точек: K=N*(N-1)*(N-2)/(3*2*1)
Значит для 15: K=15*(15-1)*(15-2)/(3*2*1) =455 вариантов
Изображения
Тип файла: png 3ki.PNG (2.0 Кб, 32 просмотров)
Случайные и Массивы https://programmersforum.ru/showthread.php?t=344371 Учим C# & basic & excel & python https://programmersforum.ru/showthre...=327446&page=5 ничего нерекомендую

Последний раз редактировалось сфинкс; 19.02.2022 в 00:18.
сфинкс вне форума Ответить с цитированием
Старый 19.02.2022, 04:32   #3
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,285
По умолчанию

Выскажу свои мысли (правильного решения не знаю). Предположу, что треугольники не могут иметь общих вершин, иначе они считаются пересекающимися. Также предлагаю сразу строить список из N треугольников, при этом каждый следующий треугольник строится только из еще незадействованных вершин (рекурсивно брать вершину с наименьшим номером и еще две других в порядке возрастания). Тогда (если верно посчитал):
Код:
N - кол-во вариантов наборов треугольников
2 - 10
3 - 280
4 - 15400
5 - 1401400

Например, для N = 2:
(0, 1, 2), (3, 4, 5)
(0, 1, 3), (2, 4, 5)
(0, 1, 4), (2, 3, 5)
(0, 1, 5), (2, 3, 4)
(0, 2, 3), (1, 4, 5)
(0, 2, 4), (1, 3, 5)
(0, 2, 5), (1, 3, 4)
(0, 3, 4), (1, 2, 5)
(0, 3, 5), (1, 2, 4)
(0, 4, 5), (1, 2, 3)
Для сокращения вариантов можно попробовать сразу после построения треугольника проверять, что ни одна из оставшихся вершин не лежит в данном треугольнике. Если лежит, то вся рекурсивная ветвь дальше не даст подходящего набора треугольников. Останется считать площади только для тех случаев, когда треугольники не пересекаются.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA на форуме Ответить с цитированием
Старый 19.02.2022, 10:00   #4
сфинкс
Форумчанин
 
Аватар для сфинкс
 
Регистрация: 17.06.2012
Сообщений: 954
По умолчанию

3-угольники визуально из здешней моей темы 3-летней давности



найти 3-угольник наибольший за 1 проход:
сравнивать с отрицательной площадью

пересечение 3-ков небось из пересечения рёбер линий
у меня бэйсик qb64 qbasic код давно есть
на основе интернет подсказок но лучше ищите на форуме
ведь внизу похожие темы
Случайные и Массивы https://programmersforum.ru/showthread.php?t=344371 Учим C# & basic & excel & python https://programmersforum.ru/showthre...=327446&page=5 ничего нерекомендую
сфинкс вне форума Ответить с цитированием
Старый 19.02.2022, 14:43   #5
ViktorR
Старожил
 
Регистрация: 23.10.2010
Сообщений: 2,304
По умолчанию

Цитата:
... Построить множество n треугольников с вершинами в этих точках так, чтобы никакие два треугольника не пересекались и не содержали друг друга, ...
У меня возник вопрос к определению понятия "Пересечение".
С одной стороны поиск говорит о том, что фигуры пересекаются, если у них есть одна или более общих точек. С другой стороны утверждается, что фигуры могут соприкасаться, т.е. могут иметь одну и более общих точек, но не пересекаться.
В моём понимании, пересекающиеся фигуры должны иметь хота бы одну общую "внутреннюю" точку.
Иначе: два треугольника с общей вершиной или два треугольника с общей стороной. Это соприкасающиеся или пересекающиеся фигуры?
Принадлежать ли точки границы самой фигуре?
Во многих случаях это оговаривается отдельно или используются разные слова, например, круг и окружность.

К теме. Если считать треугольники с общей стороной соприкасающимися, то алгоритм решения мог бы выглядеть так:
Найти многоугольник с максимальной площадью и выбрать любую точку внутри. Из этой точки к вершинам многоугольника проводим стороны и получаем множество треугольников с максимальной суммой площадей.

PS: Осталось разобраться в том, насколько независимыми должны быть треугольники.
Как-то так, ...
ViktorR на форуме Ответить с цитированием
Старый 19.02.2022, 15:02   #6
сфинкс
Форумчанин
 
Аватар для сфинкс
 
Регистрация: 17.06.2012
Сообщений: 954
По умолчанию

3-угольник 1-й: 3 стороны
3-угольник 2-й: 3 стороны
Проверить массивами пересечение всех сторон между собою =3*3 =9-жды

Подняв алгоритм пересечения прямых: там 3 результата

отрезки: пересекаются \ непересекаются \ совпадают
и когда точка на отрезке или в вершине другого отрезка: пересекаются

Однако возникнет новая головоломка: 3-ки вложенные 1 внутри другого
Случайные и Массивы https://programmersforum.ru/showthread.php?t=344371 Учим C# & basic & excel & python https://programmersforum.ru/showthre...=327446&page=5 ничего нерекомендую
сфинкс вне форума Ответить с цитированием
Старый 03.03.2022, 00:01   #7
ViktorR
Старожил
 
Регистрация: 23.10.2010
Сообщений: 2,304
По умолчанию

ViktorR
Цитата:
PS: Осталось разобраться в том, насколько независимыми должны быть треугольники.
Так понимаю, что ТС дал дёру.
Вопрос о том что треугольники могут соприкасаться по границе остался.
Можно ли считать пересечением соприкосновение?
Цитата:
чтобы никакие два треугольника не пересекались и не содержали друг друга
Что-то Сеть мне не помогла. Есть ли тот, кто может определить понятие "пересечение треугольников"?
Для себя понимаю так, что соприкасающиеся, т.е. имеющие общую границу или точку (вершину) объекты не пересекаются.
Пересечение, на мой взгляд, когда есть общие внутренние точки. Как довод - окрасьте треугольники.
Точки, принадлежащие границам треугольника не входят в его площадь.
Как-то так, ...
ViktorR на форуме Ответить с цитированием
Старый 03.03.2022, 01:05   #8
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,285
По умолчанию

ViktorR, не готов вести рассуждения о терминологии. Но если смотреть только на эту задачу, то при разрешённых соприкосновениях не было бы смысла давать 3N точек для построения N треугольников.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA на форуме Ответить с цитированием
Старый 03.03.2022, 09:34   #9
evg_m
Старожил
 
Регистрация: 20.04.2008
Сообщений: 5,515
По умолчанию

1. не пересекались => не имеют НИ одной общей точки; ни общей вершины, ни единой точки(вершины) на стороне.
1.1. 3N точек --> N треугольников
1.2. никакие три точки не лежат на одной прямой => общих сторон (хотя бы частично) быть не может. и НИКАКАЯ вершина другого треугольника не лежит на стороне другого)

=> возможно только пересечение НЕ параллельных отрезков (сторон).
программа — запись алгоритма на языке понятном транслятору
evg_m вне форума Ответить с цитированием
Старый 03.03.2022, 09:47   #10
digitalis
Старожил
 
Аватар для digitalis
 
Регистрация: 04.02.2011
Сообщений: 4,536
По умолчанию

Вообще задача, несмотря на простоту постановки, не проста. Хоть ТС и испарился, но вопрос заинтересовал и бывалых форумцев. Я так толкового алгоритма, кроме полного перебора, не вижу.
digitalis вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
В матрице найти подматрицу с наибольшей площадью Armageddets Общие вопросы Delphi 2 11.05.2017 00:16
Найти треугольник с наибольшей площадью с вершинами в точках заданных координатами (подправить код) C++ GrShOot Помощь студентам 0 28.05.2013 01:47
Найти количество диагоналей, разбивающие многоугольник на треугольники Pasha_Sh Паскаль, Turbo Pascal, PascalABC.NET 1 23.11.2012 20:41
В квадратной матрице найти столбец с максимальной суммой и строку с максимальной суммой (Pascal) Alexey355 Помощь студентам 1 26.03.2011 14:06
Определение параллелограмма с максимальной площадью, Delphi Absentik Помощь студентам 10 21.11.2009 11:34