Задача в СИ на треугольники

[Morgan8]

Нужно написать программу ,которая будет определять по введенным данным (данные=длины отрезков),сколько из этих отрезков можно собрать треугольников .Вся сложность состоит в том,что отрезков можем ввести от 3 до 10000(я так понимаю надо список list) и как потом сделать ,чтобы программа прогоняла все отрезки между собой(вот тут я думаю for подойдет).Будьте добры напишите программу,хотя бы в краткой форме

[Romeo]

Речь идёт о переборе всех возможных троек элементов массива? Да нет ничего проще:

Код: Выделить всё

for (int i1 = 0; i1 < N-2; ++i1)
  for (int i2 = i1+1; i2 < N-1; ++i2)
     for (int i3 = i2+1; i3 < N; ++i3)
        CheckTriangle(arr[i1], arr[i2], arr[i3]);

[Romeo]

А проверка на то, что из трёх отрезков можно слепить треугольник, кстати, крайне простая. Не требудется никакой тригонометрии или сложных формул. Просто ни один из трёх отрезков не должен превышать по длинне сумму длин оставшихся двух отрезков. Если это правило выполняется для всех трёх выбранных отрезков - их них без проблем можно построить треугольник, причём только один.

[somewhere]

Сложность, наверное, как раз в том, что в конце обработки могут остаться отрезки, из которых треугольника не сложить. Хотя при других вариантах компоновки отрезков - треугольники получаются всегда и лишних не остается.

[Romeo]

Ага, видимо я недостаточно внимательно прочитал задание. Нужно не просто их перебрать, а рассмотреть все варианты сложения треугольников из имеющихся отрезков и выбрать вариант с максимальным покрытием. Сразу приходит на ум следующий алгоритм, который может оказаться не оптимальным, но всё же он будет работать:

1. Строим все тройки возможных треугольников указанным выше тройным циклом (скажем записываем их в вектор). Дополнительно в структурку к трём длинам вводим ещё один признак - возможен треугольник или нет. Изначально устанавливаем признак в true для всех треугольников.
2. Делаем рекурсивную функцию, которая в цикле пробегает по контейнеру треугольников. Внутри цикла она для i-го треугольника при условии, что у него установлен признак возможности, делается следующее:
2.1. Треугольник добавляется в конец некого глобального контейнена (скажем вектора) текущих выбранных треугольников.
2.2. Мы пробегаем ещё раз по всему исходному массиву треугольников и ставим признак возможности в false, если среди его отрезков есть отрезки из текущего выбранного треугольника.
2.3. Вызываем себя рекурсивно.
2.4. Восстановливаем признаки возможностей треугольников поставленных на шаге 2.2 обратно в true.
2.5. Удаляем треугольник с конца глобального контейнера текущих треугольников.
3. После цикла проверяем длину глобального контейнера выбранных треугольников. Если она превосходит максимально втретившуюсю длину (сохранённую в отдельной глобальной переменной), то мы обновляем максимальную длину, а также запоминаем приглянувшийся нам контейнер выбранных треугольников (отдельная глобальная переменная-контейнер).

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

Алгоритм можно оптимизировать мелкими фиксами (к примеру отдельная глобальная переменная для длины максимального найденного набора не нужна, можно использовать вместо неё size() от соответствующего глобального контейнера).

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