|
0 / 0 / 0
Регистрация: 08.03.2018
Сообщений: 2
|
|
Подсчитать количество треугольников и равнобедренных трапеций, которые можно построить из данных отрезков08.03.2018, 09:40. Показов 9601. Ответов 13
На вход программе подается n натуральных чисел, являющихся длинами отрезков. Необходимо подсчитать количество уникальных треугольников и равнобедренных трапеций, которые можно построить из данных отрезков (считать, что треугольники и трапеции различны, если различна длина хотя бы одного отрезка, участвующего в их построении). При этом предполагается, что нужно подсчитать общее количество (то есть, каждый отрезок может участвовать в построении не одного, а нескольких треугольников и трапеций). Нужно рассмотреть количество уникальных треугольников и р/б трапеций при условии, что отрезки можно "склеивать" друг с другом (например, отрезки 1 и 2 могут быть объединены в дополнительный отрезок длиной 3, дающий еще дополнительные варианты построения).
0
|
|
| 08.03.2018, 09:40 | |
|
Ответы с готовыми решениями:
13
Даны длины отрезков. Подсчитать, сколько можно построить треугольников из этих отрезков, и напечатать площади этих треугольников Ввести количество отрезков и их длины; найти, сколько треугольников можно составить из этих отрезков Определить количество остроугольных треугольников, которые можно построить на множестве случайных точек |
|
Just Do It!
|
||||||
| 08.03.2018, 10:34 | ||||||
0
|
||||||
| 08.03.2018, 10:53 | ||
|
0
|
||
|
Диссидент
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
|
||||||
| 08.03.2018, 11:10 | ||||||
|
XLAT, Ваш код решает совсем другую задачу. "Сколько треугольников можно составить из N отрезков." Но решение этой задачи можно сделать несколько покороче.
![]() Добавлено через 3 минуты ЗЫ. Но исходная задача действительно интересна, и я не вижу эффективных решений (даже для случая треугольников), кроме Брут-Форс (тупого перебора), который тоже неизвестно как организовать...
0
|
||||||
|
571 / 353 / 133
Регистрация: 15.09.2017
Сообщений: 1,239
|
||
| 08.03.2018, 13:59 | ||
![]() Добавлено через 7 минут Это что-то типа этого получается для 5 отрезков, т.е. первая степень это N-2, а дальше убавляем степень:
0
|
||
|
Диссидент
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
|
||
| 08.03.2018, 14:00 | ||
|
В общем, задача представляется непростой, интересной, и вполне достойной, чтоб над ней подумать... Только вот сегодня думать не дают, суета вокруг, сами понимаете... Всех, кто имеет отношение - с праздником! ![]() ![]()
0
|
||
|
571 / 353 / 133
Регистрация: 15.09.2017
Сообщений: 1,239
|
||||||
| 08.03.2018, 14:12 | ||||||
|
Если с формулой не ошибся, то для 10-ти отрезков порядка 10 000 комбинаций, но если больше рекурсия уже не справится, будет переполнения стека
Добавлено через 6 минут Ну для проверки треугольника, что-то типа:
0
|
||||||
|
Диссидент
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
|
||||||||
| 08.03.2018, 14:43 | ||||||||
|
Правда, если гарантировать, что при выполнении этого анализа всегда a >= b >= c тогда можно ограничится условием
Тогда проверку a[i] + a[j] > a[k] (i < j < k) делаем до тех пор, пока она выполняется. Дальше можно не смотреть и просто инкременировать j++ Дошли до конца (j == n-2) - инкременируем i++. И так до упора. Но это все опять же без учета склеек. Конечно, можно для каждого множества склеек снова составлять упорядоченную последовательность длин. Но имеет смысл рассматривать только треугольники с участием склееных отрезков. И как перебирать все возможные склейки? Они, вообще-то образуют частично-упорядоченное множество... Все вышеизложенное - не более, чем мысли вслух. Хотя неплохой алгоритм для треугольников без склеек уже вырисовывается... Добавлено через 3 минуты
0
|
||||||||
|
571 / 353 / 133
Регистрация: 15.09.2017
Сообщений: 1,239
|
||||||||
| 09.03.2018, 08:32 | ||||||||
a >= b, а вообще я имел ввиду все условия прогнать для каждой стороны, т.е. полностью функция будет выглядеть так:
triangl(a+b+c, d+e, f);Добавлено через 7 минут b в основании
0
|
||||||||
|
Диссидент
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
|
|||||
| 09.03.2018, 12:52 | |||||
|
Впрочем, если отрезки предварительно упорядочить, все это становится излишним.
0
|
|||||
|
2734 / 888 / 331
Регистрация: 10.02.2018
Сообщений: 2,097
|
||||||
| 09.03.2018, 15:55 | ||||||
|
Треугольники можно как-то так найти, но скорость перебора пугающая)
1
|
||||||
|
Диссидент
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
|
|
| 09.03.2018, 17:14 | |
|
Ygg, код ваш осмотрел по диагонали, простите. Но вот какие замечания.
1. Вы считаете треугольники разными, если они разные в смысле равенства треугольников. Я же полагал, что они разные, если для их построения используются разные наборы отрезков. Впрочем, задачу можно трактовать и так и этак.... Кстати, нет, вы правы. Перечитал внимательнее стартовый пост. 2. Вы упорядочиваете стороны для каждого потенциального треугольника (для каждой тройки отрезков). А я предлагаю упорядочить длины отрезков сразу. Тогда при i < j < k можно проверять только одно неравенство. Более того, это дает возможность прекращать перебор по k, как только lines[i] + lines[j] <= lines[k]. Кроме того , перебор по k можно вообще не проводить, если воспользоваться дихотомическим поиском. Тут, правда, некоторые сложности с исключением равных, но, имхо, они преодолимы. На этом пути можно получить вполне приемлемый по скорости алгоритм. 3. Не увидел в вашем коде анализа "склеек" (возможно, плохо смотрел). А именно здесь, как мне кажется, и сосредоточены все сложности Добавлено через 19 минут Что можно сделать с группами повторяющихся длин? Если в группе больше 3-х, все что больше, можно спокойно выкинуть Если 3 равных - эта группа дает один равносторонний треугольник, его считаем, и сокращаем группу до 2-х. С двумя можно поступить так. Подходят все отрезки, что лежат левее (я считаю упорядоченность по возрастанию) Их число равно просто j - 1. Теперь смотрим направо. Подойдут все y меньшие 2x (тут тоже можно воспользоваться дихотомией). После этих подсчетов, пары заменяем одним представителем. Конечно, перед анализом склеек всё нужно восстановить
1
|
|
|
2734 / 888 / 331
Регистрация: 10.02.2018
Сообщений: 2,097
|
|
| 09.03.2018, 17:23 | |
|
Байт, на оптимальность не претендую)
Склейка сделана рекурсивно. Есть список отрезков. Если сложить любые два отрезка, то получается новый список отрезков, в котором количество отрезков на единицу меньше исходного. Новый список отрезков опять полностью проверяется, хотя тут можно было бы оптимизировать и исключить повторные проверки.
0
|
|
|
Диссидент
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
|
|
| 09.03.2018, 18:04 | |
|
Ygg, Вот где зарыта собака. Пусть у вас исходный набор 1 2 3 4 5 6. Склеиваете 1+ 2. Получаем 3 3 4 5 6. Склеиваем 4+5: 3 3 9 6
Теперь другая ветка. 1 2 3 4 5 6 -(4+5)- 1 2 3 9 6 -(1+2)- 3 3 9 6 - получился тот же набор, который совершенно не имеет смысла считать. И таких ситуаций множество! Конечно, вы все их переберете и отвергните повторы. Но на оптимальность тут, конечно, претендовать нелепо . А хотелось бы. Просто потому что брут-форс не шибко интересен. И чувствуется, что у этой задачи должен быть хороший алгоритм.Кстати, набросанный мной в посте 12 алгоритм не требует проверок на совпадение. Все треугольники будут априори разными. Более того, лексикографически упорядоченными, если представить треугольник как тройку (a, b, c). Но это не считая равносторонних и равнобедренных, подсчитанных и выкинутых при удалении повторов. А их можно в другие списки помещать... И при анализе уникальности применять не последовательный перебор, а опять же дихотомию... В общем, задача любопытная. И лично меня она интересует не в смысле кода (который писать в любом случае будет утомительно), а в смысле алгоритма. А ТС, судя по всему, давно на нее забил... ![]() Добавлено через 14 минут С точки зрения "высокой науки" можно сказать вот что. Склейки (наборы длин) образуют естественным образом направленный граф. Нам нужно найти его остовное дерево и пройти по всем его ветвям. Каждый проход по ветви уменьшает количество длин на 1. И рассматривать надо только треугольники с новой длиной. Их оказывается уже не Cn3, а "всего лишь" Cn-12. Вопрос в том, как это дерево построить? Как отбрасывать ребра, ведущие к уже проанализированным наборам-вершинам.
0
|
|
| 09.03.2018, 18:04 | |
|
Помогаю со студенческими работами здесь
14
Количество равнобедренных треугольников Определить треугольники минимальной и максимальной площади, которые можно построить из отрезков Определить треугольники минимальной и максимальной площади, которые можно построить из отрезков
Сколько отрезков можно построить на данном множестве, которые располагаются в 3-ем координатном углу? Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
||||
|
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта
Симптом:
После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
|
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
|
Новый ноутбук
volvo 07.12.2025
Всем привет.
По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне:
Ryzen 5 7533HS
64 Gb DDR5
1Tb NVMe
16" Full HD Display
Win11 Pro
|
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
|
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
|
|
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов
На странице:
https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/
нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
|
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов.
. . .
|
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
|
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
|
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут.
В век Веб все очень привыкли к дизайну Single-Page-Application .
Быстренько разберем подход "на фреймах".
Мы делаем одну. . .
|