C++で可能な三角形の数を数えます

三角形の辺の長さを含む配列が与えられます。目標は、その配列から任意の3つの辺をとることによって作成できる三角形の数を見つけることです。

これを行うには、任意の2つの合計が常に>3番目の側であるかどうかを確認します。はいの場合、これらの3つの辺は三角形を作ることができます。作成できる三角形の数を増やします。

例を挙げて理解しましょう。

入力 − 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つ取ります。

• 最も外側のループ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