Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.71/48: Рейтинг темы: голосов - 48, средняя оценка - 4.71
0 / 0 / 0
Регистрация: 08.03.2018
Сообщений: 2

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

08.03.2018, 09:40. Показов 9601. Ответов 13

Студворк — интернет-сервис помощи студентам
На вход программе подается n натуральных чисел, являющихся длинами отрезков. Необходимо подсчитать количество уникальных треугольников и равнобедренных трапеций, которые можно построить из данных отрезков (считать, что треугольники и трапеции различны, если различна длина хотя бы одного отрезка, участвующего в их построении). При этом предполагается, что нужно подсчитать общее количество (то есть, каждый отрезок может участвовать в построении не одного, а нескольких треугольников и трапеций). Нужно рассмотреть количество уникальных треугольников и р/б трапеций при условии, что отрезки можно "склеивать" друг с другом (например, отрезки 1 и 2 могут быть объединены в дополнительный отрезок длиной 3, дающий еще дополнительные варианты построения).
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
08.03.2018, 09:40
Ответы с готовыми решениями:

Даны длины отрезков. Подсчитать, сколько можно построить треугольников из этих отрезков, и напечатать площади этих треугольников
Даны длины отрезков a,b,c,d. Подсчитать, сколько можно построить треугольников из этих отрезков, и напечатать площади этих треугольников....

Ввести количество отрезков и их длины; найти, сколько треугольников можно составить из этих отрезков
надо написать такую программу: пользователь вводит количество отрезков и их длины, и надо найти сколько треугольников можно составить из...

Определить количество остроугольных треугольников, которые можно построить на множестве случайных точек
Определить количество остроугольных треугольников, которые можно построить на множестве случайных точек. Паскаль никак не хочет...

13
Just Do It!
 Аватар для XLAT
4197 / 2652 / 654
Регистрация: 23.09.2014
Сообщений: 8,946
Записей в блоге: 3
08.03.2018, 10:34
C++
1
2
3
4
5
6
7
8
9
10
11
12
int m[N];
int count_triangle = 0;
 
// Для треугольников:
for(int i = 0; i < N; i++)
{   for(int j = 0; j < N; j++)
    {   for(int k = 0; k < N; k++)
        {   if((i == j) || (i == k) || (j == k)) continue;
            if((m[i]>abs(m[j]-m[k]))&&(m[i]<[j]+m[k])) count_triangle++;
        }
    }
}
0
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
08.03.2018, 10:53
Цитата Сообщение от XLAT Посмотреть сообщение
// Для треугольников:
Здесь не учтено, что отрезки могут склеиваться. От ТС хотелось бы видеть пример входного файла, т.к. если отрезков десятки/сотни, задача становится слишком тяжелой для вычислений.
0
Диссидент
Эксперт C
 Аватар для Байт
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
08.03.2018, 11:10
XLAT, Ваш код решает совсем другую задачу. "Сколько треугольников можно составить из N отрезков." Но решение этой задачи можно сделать несколько покороче.
C++
1
2
3
4
5
6
7
8
9
10
11
12
int m[N];
int count_triangle = 0;
 
// Для треугольников:
for(int i = 0; i < N-2; i++)
{   for(int j = i+1; j < N-1; j++)
    {   for(int k = j+1; k < N; k++)
        { 
            if((m[i]>abs(m[j]-m[k]))&&(m[i]<m[j]+m[k])) count_triangle++; // тут была мелкая описка
        }
    }
}
Так как, наверное, можно считать треугольники a b c, b a c ... За один. Если же это треугольники разные (следует уточнить постановку задачи), достаточно результат умножить на 6

Добавлено через 3 минуты
ЗЫ. Но исходная задача действительно интересна, и я не вижу эффективных решений (даже для случая треугольников), кроме Брут-Форс (тупого перебора), который тоже неизвестно как организовать...
0
 Аватар для Avaddon74
571 / 353 / 133
Регистрация: 15.09.2017
Сообщений: 1,239
08.03.2018, 13:59
Цитата Сообщение от Oribi Посмотреть сообщение
при условии, что отрезки можно "склеивать" друг с другом (например, отрезки 1 и 2 могут быть объединены в дополнительный отрезок длиной 3, дающий еще дополнительные варианты построения).
Я что-то даже количество вариантов не могу прикинуть, попытался найти количество для 5 отрезков, так у меня 37 комбинаций получилось, если не просчитался. Это же сколько комбинаций треугольников только будет для 10 отрезков?

Добавлено через 7 минут
Это что-то типа этого получается для 5 отрезков, т.е. первая степень это N-2, а дальше убавляем степень: https://www.cyberforum.ru/cgi-bin/latex.cgi?{3}^{3} + {3}^{2} + 1 ?
0
Диссидент
Эксперт C
 Аватар для Байт
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
08.03.2018, 14:00
Цитата Сообщение от Avaddon74 Посмотреть сообщение
Я что-то даже количество вариантов не могу прикинуть,
Так видимо, в том-то и фишка, чтобы организовать правильный перебор с отсечением явно неподходящих ветвей...
В общем, задача представляется непростой, интересной, и вполне достойной, чтоб над ней подумать...
Только вот сегодня думать не дают, суета вокруг, сами понимаете...
Всех, кто имеет отношение - с праздником!
0
 Аватар для Avaddon74
571 / 353 / 133
Регистрация: 15.09.2017
Сообщений: 1,239
08.03.2018, 14:12
Если с формулой не ошибся, то для 10-ти отрезков порядка 10 000 комбинаций, но если больше рекурсия уже не справится, будет переполнения стека

Добавлено через 6 минут
Ну для проверки треугольника, что-то типа:
C++
1
2
3
4
bool triangl(int a, int b, int c){
   if(a < b + c && a >= b && a >= c) return true;
   return false;
}
0
Диссидент
Эксперт C
 Аватар для Байт
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
08.03.2018, 14:43
Цитата Сообщение от Avaddon74 Посмотреть сообщение
Ну для проверки треугольника, что-то типа:
Не пойдет. a = 5, b = 6, c = 3
Правда, если гарантировать, что при выполнении этого анализа всегда a >= b >= c тогда можно ограничится условием
C++
1
if (a < b + c)
Отсюда идея (в общем-то лежащая на поверхности) - упорядочить длины отрезков. Скажем, по возрастанию.
Тогда проверку a[i] + a[j] > a[k] (i < j < k) делаем до тех пор, пока она выполняется. Дальше можно не смотреть и просто инкременировать j++ Дошли до конца (j == n-2) - инкременируем i++. И так до упора.
Но это все опять же без учета склеек.
Конечно, можно для каждого множества склеек снова составлять упорядоченную последовательность длин. Но имеет смысл рассматривать только треугольники с участием склееных отрезков.
И как перебирать все возможные склейки? Они, вообще-то образуют частично-упорядоченное множество...
Все вышеизложенное - не более, чем мысли вслух.
Хотя неплохой алгоритм для треугольников без склеек уже вырисовывается...

Добавлено через 3 минуты
Цитата Сообщение от Байт Посмотреть сообщение
Хотя неплохой алгоритм для треугольников без склеек уже вырисовывается...
Этот алгоритм можно слегка улучшить. Ведь что нам нужно? Найти точку k где a[i] + a[j] > a[k], а a[i] + a[j] <= a[k+1]. А это можно сделать дихотомией (делением пополам)
0
 Аватар для Avaddon74
571 / 353 / 133
Регистрация: 15.09.2017
Сообщений: 1,239
09.03.2018, 08:32
Цитата Сообщение от Байт Посмотреть сообщение
Не пойдет. a = 5, b = 6, c = 3
Почему не пойдет, у меня же условие a >= b, а вообще я имел ввиду все условия прогнать для каждой стороны, т.е. полностью функция будет выглядеть так:
C++
1
2
3
4
5
6
bool triangl(int a, int b, int c){
   if(a < b + c && a >= b && a >= c) return true;
   if(b < a + c && b >= a && b >= c) return true;
   if(c < a + b && c >= a && c >= b) return true;
   return false;
}
А дальше в рекурсии перебирать отрезки и их комбинации, типа: triangl(a+b+c, d+e, f);

Добавлено через 7 минут
Цитата Сообщение от Байт Посмотреть сообщение
Не пойдет. a = 5, b = 6, c = 3
Кстати, с такими параметрами треугольник получится, если b в основании
0
Диссидент
Эксперт C
 Аватар для Байт
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
09.03.2018, 12:52
Цитата Сообщение от Avaddon74 Посмотреть сообщение
Почему не пойдет, у меня же условие a >= b,
А вы подставьте указанные значения в функцию из поста 7... И не будем больше на эту тему спорить, чтобы людей не смешить...
Цитата Сообщение от Avaddon74 Посмотреть сообщение
вообще я имел ввиду все условия прогнать для каждой стороны, т.е. полностью функция будет выглядеть так:
Ну, дык, это совсем другое дело... Но по коду из поста 7 мне, честное слово, было трудно догадаться, что вы имеете в виду.
Впрочем, если отрезки предварительно упорядочить, все это становится излишним.
Цитата Сообщение от Avaddon74 Посмотреть сообщение
если b в основании
Повернуть треугольник можно как угодно, от этого его треугольная суть не изменится.
Цитата Сообщение от Avaddon74 Посмотреть сообщение
А дальше в рекурсии перебирать отрезки и их комбинации, типа: triangl(a+b+c, d+e, f);
Вот именно как организовать этот перебор, я и не могу пока понять.
0
2734 / 888 / 331
Регистрация: 10.02.2018
Сообщений: 2,097
09.03.2018, 15:55
Треугольники можно как-то так найти, но скорость перебора пугающая)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
#include <iostream>
#include <vector>
 
class CTriangle
{
public:
    int m_a, m_b, m_c;
 
public:
    CTriangle(int a, int b, int c) // располагает стороны по возрастанию
    {
        if ((a <= b) && (a <= c))
        {
            m_a = a;
            m_b = (b <= c) ? b : c;
            m_c = (b <= c) ? c : b;
        }
        else if ((b <= a) && (b <= c))
        {
            m_a = b;
            m_b = (a <= c) ? a : c;
            m_c = (a <= c) ? c : a;
        }
        else// if ((c <= a) && (c <= b))
        {
            m_a = c;
            m_b = (a <= b) ? a : b;
            m_c = (a <= b) ? b : a;
        }
    }
 
    bool IsValid() // можно ли это считать треугольником
    {
        return (m_a + m_b) > m_c;
    }
 
    bool IsEqual(CTriangle& t) // равны ли треугольники
    {
        return (m_a == t.m_a) && (m_b == t.m_b) && (m_c == t.m_c);
    }
 
    void Show() // вывести стороны треуголькника в консоль
    {
        std::cout << m_a << ", " << m_b << ", " << m_c << std::endl;
    }
};
 
class CTriangleMap
{
public:
    std::vector<CTriangle> m_array;
 
public:
    void Reset() // очистить
    {
        m_array.clear();
    }
 
    int GetCount() // узнать количество треугольников
    {
        return (int)m_array.size();
    }
 
    bool Append(int a, int b, int c) // добавить треугольник, если он уникальный
    {
        CTriangle t(a, b, c);
        
        if (!t.IsValid())
            return false;
 
        for (size_t i=0; i<m_array.size(); i++)
        {
            if (m_array[i].IsEqual(t))
                return false;
        }
 
        m_array.push_back(t);
        return true;
    }
    
    void Show(bool full) // вывести в консоль количество (и все треугольники)
    {
        std::cout << "count=" << m_array.size() << std::endl;
        
        if (full)
        {
            for (size_t i=0; i<m_array.size(); i++)
            {
                std::cout << (i + 1) << ") ";
                m_array[i].Show();
            }
        }
    }
};
 
void collect_triangle(CTriangleMap & tm, std::vector<int> & lines); // посчитать количество уникальных треугольников
void collect_triangle_combo(CTriangleMap & tm, std::vector<int> & lines);  // посчитать количество уникальных треугольников с учётом объединения сторон
void collect_triangle_combo_lines(CTriangleMap & tm, std::vector<int> & lines, int line1, int line2); // (вспомогательная функция) рекурсивное объединение сторон и подсчёт треугольников
 
int _test[] = { 1, 2, 3, 4, 5, 6, 7};//, 8, 9, 10 }; // тест (больше 7 начинаются тормоза)
 
int main()
{
    std::vector<int> test;
    for (size_t i=0; i<(sizeof(_test) / sizeof(_test[0])); i++)
        test.push_back(_test[i]);
 
    CTriangleMap tmap;
    collect_triangle(tmap, test);
    tmap.Show(false);
 
    tmap.Reset();
    collect_triangle_combo(tmap, test);
    tmap.Show(false);
 
    system("pause");
    return 0;
}
 
void collect_triangle(CTriangleMap & tm, std::vector<int> & lines)
{
    int cnt = (int)lines.size();
 
    for (int i=0; i<cnt-2; i++)
    {
        for (int j=i+1; j<cnt-1; j++)
        {
            for (int k=j+1; k<cnt; k++)
            {
                tm.Append(lines[i], lines[j], lines[k]);
            }
        }
    }
}
 
void collect_triangle_combo(CTriangleMap & tm, std::vector<int> & lines)
{
    collect_triangle(tm, lines);
 
    int cnt = (int)lines.size();
    if (cnt <= 3)
        return;
 
    for (int i=0; i<cnt-1; i++)
    {
        for (int j=i+1; j<cnt; j++)
        {
            collect_triangle_combo_lines(tm, lines, i, j);
        }
    }
}
 
void collect_triangle_combo_lines(CTriangleMap & tm, std::vector<int> & lines, int line1, int line2)
{
    int cnt = (int)lines.size();
    if (cnt <= 3)
        return;
 
    std::vector<int> temp;
    temp.push_back(lines[line1] + lines[line2]);
 
    for (int i=0; i<cnt; i++)
    {
        if ((i != line1) && (i != line2))
            temp.push_back(lines[i]);
    }
    
    collect_triangle(tm, temp);
 
    cnt--;
 
    for (int i=0; i<cnt-1; i++)
    {
        for (int j=i+1; j<cnt; j++)
        {
            collect_triangle_combo_lines(tm, temp, i, j);
        }
    }
}
1
Диссидент
Эксперт C
 Аватар для Байт
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
Диссидент
Эксперт C
 Аватар для Байт
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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
09.03.2018, 18:04
Помогаю со студенческими работами здесь

Количество равнобедренных треугольников
Помогите пожалуйста решить такую задачу: Подсчитать количество равнобедренных треугольников с вершинами в заданном множестве точек на...

Определить треугольники минимальной и максимальной площади, которые можно построить из отрезков
13. Известны длины отрезков a, b, c и d. Определить треугольники минимальной и максимальной площади, которые можно построить из этих...

Определить треугольники минимальной и максимальной площади, которые можно построить из отрезков
Известны длины отрезков a, b, c и d. Определить треугольники минимальной и максимальной площади, которые можно построить из этих...

Определить треугольники минимальной и максимальной площади, которые можно построить из отрезков
Известны длины отрезков a. b. с и d. определить треугольники минимальной и максимальной площади, которые можно построить из этих отрезков. ...

Сколько отрезков можно построить на данном множестве, которые располагаются в 3-ем координатном углу?
Дано множество точек на плоскости. Сколько отрезков можно построить на данном множестве, которые располагаются в 3-ем координатном углу?...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Новые блоги и статьи
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 . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru