Невырожденный треугольник

@Gh[oO]st · Регистрация: 21.11.2010

Студворк — интернет-сервис помощи студентам

Дан набор из N отрезков различной длины. Сколькими способами можно выбрать из этих отрезков три, из которых можно составить (невырожденный) треугольник?
Длины сторон невырожденного треугольника связаны следующими неравенствами:
a<b+c
b<c+a
c<a+b

Программа должна вывести одно число - искомое количество способов.

Собственно вопрос в следующем:
количество отрезков и длину ввести не проблема. Как сравнить введенные числа из массива(макс. кол-во чисел 20) так, чтобы попадали под выше указанные неравенства
Допустим введено
1 3 2 4
ответом должна быть единица(1).

Day · 01.12.2010, 20:22

C++
1
2
3
4
5
6
for(S=0, i=0; i<n-2; i++) {
  for(j=i+1; j<n-1; j++) 
    for(k=j+1; K<n; k++)
       if (a[i]+a[j] > a[k] && a[i]+a[k] > a[j] && a[j]+a[k] > a[i]) S++;
}
cout << S;

ЗЫ. Интересно было бы обобщить эту задачу для m-угольников (m >=3)

Добавлено через 1 минуту
В 3-м for буква K конечно, маленькая

@Напильнег · 01.12.2010, 22:31

А можно, кстати, нехило извратиться, записав условие во внутреннем цикле в естественной форме:

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
#include <iostream>
 
using namespace std;
 
#define a l[i]
#define b l[j]
#define c l[k]
 
void main()
{
  double l[20] = {1, 3, 2, 4};
  int n = 4;
 
  //здесь пишем ввод других n, l[0]..l[n-1]
 
  int s = 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-0; k++)
        if ((a+b > c) && (a+c > b) && (b+c > a)) s++;
  
  cout << s << endl;
 
  system("pause");
}

Day · 01.12.2010, 23:55

Напильнег, идея симпатичная.
А как все-таки по поводу m-угольников ?

@Напильнег · 02.12.2010, 01:14

Лениво...

Day · 02.12.2010, 02:26

Сообщение от Напильнег

Лениво...

А никто тебя с печки слезать не заставляет.
Я же не кричу - Помогите!, Лаба!
Мне просто любопытно стало.
Как эти m циклов заменить одним, который заставил бы их прокручиваться.
Это же выход на другую ступень. Типа - сам себе транслятор.
Чувствую - можно. Но не сейчас. Поздно . Спать пора. На печку.

@Manjak · 02.12.2010, 09:54

Вроде все точно

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
#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>
#include <vector>
 
#define MIN_INPUT_SIZE 3
 
using namespace std;
 
class Validator : public unary_function<int, bool>
{
public:
    Validator  (const int& _nFirst, const int& _nSecond)
        : m_nFirstNumber(_nFirst),
          m_nSecondNumber(_nSecond)
    {
    }
 
    bool operator() (const int& _nThird)
    {
        return (m_nFirstNumber  + m_nSecondNumber > _nThird ) &&
               (m_nFirstNumber  + _nThird  > m_nSecondNumber) &&
               (m_nSecondNumber + _nThird  > m_nFirstNumber );
    }
 
private:
    int m_nFirstNumber;
    int m_nSecondNumber;
};
 
int main( void )
{
    int                   nCount         = 0;
    vector<int>           vNumbers;
   
    copy(istream_iterator<int>(cin), istream_iterator<int>(), back_inserter(vNumbers));
    vNumbers.erase(remove(vNumbers.begin(), vNumbers.end(), 0), vNumbers.end());
 
    if (vNumbers.size() < MIN_INPUT_SIZE)
    {
        return EXIT_FAILURE;
    }
 
    sort(vNumbers.begin(), vNumbers.end());
 
    vector<int>::iterator itrFirst,
                          itrSecond,
                          itrThird,
                          itrCurNum;
                           
    
    for (itrFirst = vNumbers.begin(); itrFirst != vNumbers.end() - 1; ++itrFirst)
    {
        itrSecond = itrFirst + 1;
        itrCurNum = itrSecond + 1;
        itrThird  = find_if(itrCurNum, vNumbers.end(), 
                            bind2nd(greater_equal<int>(), *itrFirst + *itrSecond));
 
        if (!distance(itrCurNum, itrThird))
        {
            break;
        }
 
        nCount += count_if(itrCurNum, itrThird, Validator(*itrFirst, *itrSecond));       
    }
 
    cout << "Count: " << nCount << endl;
 
    system("pause");
    return EXIT_SUCCESS;
}

Добавлено через 20 минут
Небольшая неточность была:

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
#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>
#include <vector>
 
#define MIN_INPUT_SIZE 3
 
using namespace std;
 
class Validator : public unary_function<int, bool>
{
public:
    Validator  (const int& _nFirst, const int& _nSecond)
        : m_nFirstNumber(_nFirst),
          m_nSecondNumber(_nSecond)
    {
    }
 
    bool operator() (const int& _nThird)
    {
        bool bRes = (m_nFirstNumber  + m_nSecondNumber > _nThird ) &&
                    (m_nFirstNumber  + _nThird  > m_nSecondNumber) &&
                    (m_nSecondNumber + _nThird  > m_nFirstNumber );
 
        if (bRes)
        {
            cout << '(' << m_nFirstNumber << ':' << m_nSecondNumber << ':' << _nThird << ')' << endl;
        }
 
        return bRes;
    }
 
private:
    int m_nFirstNumber;
    int m_nSecondNumber;
};
 
int main( void )
{
    int                   nCount         = 0;
    vector<int>           vNumbers;
   
    copy(istream_iterator<int>(cin), istream_iterator<int>(), back_inserter(vNumbers));
    vNumbers.erase(remove(vNumbers.begin(), vNumbers.end(), 0), vNumbers.end());
 
    if (vNumbers.size() < MIN_INPUT_SIZE)
    {
        return EXIT_FAILURE;
    }
 
    sort(vNumbers.begin(), vNumbers.end());
 
    vector<int>::iterator itrFirst,
                          itrSecond,
                          itrThird,
                          itrCurNum;
                           
    
    for (itrFirst = vNumbers.begin(); itrFirst != vNumbers.end() - 1; ++itrFirst)
    {
        for(itrSecond = itrFirst + 1; itrSecond != vNumbers.end() - 1; ++itrSecond)
        {
            itrCurNum = itrSecond + 1;
            itrThird  = find_if(itrCurNum, vNumbers.end(), 
                                bind2nd(greater_equal<int>(), *itrFirst + *itrSecond));
 
            if (!distance(itrCurNum, itrThird))
            {
                break;
            }
 
            nCount += count_if(itrCurNum, itrThird, Validator(*itrFirst, *itrSecond));       
        }
    }
 
    cout << "Count: " << nCount << endl;
 
    system("pause");
    return EXIT_SUCCESS;
}

Day · 02.12.2010, 12:48

Ну вот, кажется, получилось

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
#include <stdio.h>
#include <stdlib.h>
#include <alloc.h>
sochet(int *cc, int M)  // Генерация следующего сочетания
{ int i, j;
   for(i=M-1; i>=0; i--) {
     if (cc[i] < cc[i+1] - 1) {
       cc[i]++;
       for(j=i+1; j<M; j++) cc[j] = cc[j-1]+1;
       return(1);
     }
   }
   return(0);
}
/****************/
main(int ac, char *av[])
{ int N, M, T, T0, i, j, S;
  int *cc, *dd;
   if (ac<3) exit(1);
   N = atoi(av[1]);
   M = atoi(av[2]);
   if (N < M || M < 3) exit(1);
   cc = (int *)malloc((M+1)*sizeof(int));  // Сочетания
   dd = (int *)malloc(N*sizeof(int));  // Длины сторон
   randomize();
   for(i=0; i<N; i++) {  // Генерация длин сторон
     dd[i] = random(100) + 1;
     printf("%4d", dd[i]);
   }
   printf("\n");
   for(i=0; i<M; i++) cc[i] = i;
   cc[M] = N;
   S = 0;  // Кол-во многоугольников
   do {
     // for(j=0; j<M; j++) printf("%4d", cc[j]);  // Проверка сочетания
     // printf("\n");
     for(i=0; i<M; i++) {
       T = 0; // Сумма остальных сторон
       for(j=0; j<M; j++) {
         if (i == j) T0 = dd[cc[j]];  // i-тая сторона
         else        T += dd[cc[j]];
       }
       if (T0 >= T) break;
     }
     if (i==M) {  // Все стороны прошли тест
       for(j=0; j<M; j++) printf("%4d", dd[cc[j]]);
       printf("\n");
       S++;
     }
   }   while (sochet(cc, M));
   printf("S=%d\n", S);
}

Запуск
...exe N M
N - кол-во отрезков
M - кол-во сторон мноугольников

@Gh[oO]st · 03.12.2010, 22:13 **[ТС]**

развили идею, всем спасибо)

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	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 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

@Gh[oO]st 0 / 0 / 0 Регистрация: 21.11.2010 Сообщений: 3

	Невырожденный треугольник 30.11.2010, 20:47. Показов 20959. Ответов 8 Метки нет (Все метки) Дан набор из N отрезков различной длины. Сколькими способами можно выбрать из этих отрезков три, из которых можно составить (невырожденный) треугольник? Длины сторон невырожденного треугольника связаны следующими неравенствами: a<b+c b<c+a c<a+b Программа должна вывести одно число - искомое количество способов. Собственно вопрос в следующем: количество отрезков и длину ввести не проблема. Как сравнить введенные числа из массива(макс. кол-во чисел 20) так, чтобы попадали под выше указанные неравенства Допустим введено 1 3 2 4 ответом должна быть единица(1). 0

Day 1180 / 990 / 83 Регистрация: 29.10.2009 Сообщений: 1,385
	01.12.2010, 23:55
	Напильнег, идея симпатичная. А как все-таки по поводу m-угольников ? 0

@Напильнег 481 / 119 / 17 Регистрация: 30.09.2010 Сообщений: 473
	02.12.2010, 01:14
	Сообщение было отмечено как решение Решение Лениво... 0

@Gh[oO]st 0 / 0 / 0 Регистрация: 21.11.2010 Сообщений: 3
	03.12.2010, 22:13 [ТС]
	развили идею, всем спасибо) 0

Невырожденный треугольник

Решение