C++에서 가능한 삼각형의 수 세기

삼각형의 변의 길이를 포함하는 배열이 주어집니다. 목표는 해당 배열에서 세 변을 취하여 만들 수 있는 삼각형의 수를 찾는 것입니다.

두 개의 합이 항상> 세 번째 변인지 확인하여 이를 수행합니다. 그렇다면 이 세 변은 삼각형을 만들 수 있습니다. 만들 수 있는 삼각형의 수를 늘립니다.

예를 들어 이해합시다.

입력 - arr[]={1,2,4,5}

출력 − 가능한 삼각형의 개수 − 1

설명 − 변(2,4,5)은 2+4>5 &4+5>2 &2+5>4

입력 - arr[]={4,5,6,3,2}

출력 − 가능한 삼각형의 수 − 7

설명 - 측면 (4,5,6), (4,5,2),(4,5,3),(4,3,2),(5,6,3),(5,6,2) 삼각형을 만드세요.

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

• 임의의 양수로 초기화된 정수 배열 arr[]을 사용합니다.

• countTriangles(int arr[], int n) 함수는 배열과 배열의 길이를 가져와서 만들 수 있는 삼각형을 반환합니다.

• 삼각형의 초기 개수를 0으로 간주합니다.

• 3면에 대해 3개의 for 루프를 사용합니다.

• 가장 바깥쪽 루프 0<=i

• 변의 경우 arr[i],arr[j],arr[k] 삼각형의 변을 형성하는지 확인하십시오.

• arr[i] + arr[j]> arr[k] &&arr[i] + arr[k]> arr[j] &&arr[k] + arr[j]> arr[i]를 확인하십시오.

• 결과로 카운트를 반환합니다.

예

#include <bits/stdc++.h>
using namespace std;
int countTriangles(int arr[], int n){
   // Count of triangles
   int count = 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++){
            //any two sides have sum > third
            if ( arr[i] + arr[j] > arr[k] && arr[i] + arr[k] > arr[j] && arr[k] + arr[j] > arr[i])
               { count++; }
         }
      }
   }
   return count;
}
int main(){
   int Arr[] = { 1,2,5,3,6,8,10 };
   int len = sizeof(Arr) / sizeof(Arr[0]);
   cout << "count of Triangles possible : "<< countTriangles(Arr, len);
   return 0;
}

출력

위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -

count of Triangles possible : 8