C++で作成可能な三角形の個数を数える方法

問題の概要

三角形の各辺の長さを格納した配列が与えられます。この記事の目標は、配列から任意の3つの値を選んで作ることができる三角形の個数を求めることです。

判定には、三角形の成立条件である「任意の2辺の和が、残りの1辺よりも大きい」ことを利用します。この条件を満たす3辺の組み合わせが見つかるたびに、カウントを1つずつ増やしていきます。

具体例を見ながら理解を深めましょう。

入出力例1

入力: arr[] = {1, 2, 4, 5}

出力: 作成可能な三角形の数 ― 1

説明: (2, 4, 5) の組み合わせだけが三角形を作れます。2+4>5、4+5>2、2+5>4 の3つの条件をすべて満たすためです。

入出力例2

入力: arr[] = {4, 5, 6, 3, 2}

出力: 作成可能な三角形の数 ― 7

説明: (2, 3, 4)、(2, 4, 5)、(2, 5, 6)、(3, 4, 5)、(3, 4, 6)、(3, 5, 6)、(4, 5, 6) の7通りの組み合わせが三角形を作れます。

アルゴリズムのアプローチ

• 正の整数で初期化された整数型配列 arr[] を用意します。

• 関数 countTriangles(int arr[], int n) は、配列とその長さを受け取り、作成可能な三角形の数を返します。

• 三角形のカウントを 0 で初期化します。

• 3つの辺に対応する三重の for ループを使用します。

• 最も外側のループは 0 ≤ i < n-2、中間のループは i < j < n-1、最も内側のループは j < k < n となります。

• 辺 arr[i]、arr[j]、arr[k] が三角形を構成するかどうかを判定します。

• arr[i] + arr[j] > arr[k] かつ arr[i] + arr[k] > arr[j] かつ arr[k] + arr[j] > arr[i] を満たす場合は count をインクリメントします。

• 最後に結果として count を返します。

この方法では、すべての3辺の組み合わせを網羅的にチェックするため、計算量は O(n³) となります。データ数が少ない場合にはシンプルで確実な手法です。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
int countTriangles(int arr[], int n){
    // 三角形の数
    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++){
                // 任意の2辺の和が残りの1辺より大きいか判定
                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