C++で指定した周囲長から作れる直角三角形の個数を数える方法

三角形の周囲長 P が与えられたとき、同じ周囲長を持つ直角三角形が何通り作れるかを求めるのが本記事の目的です。なお、周囲長とは三角形の3辺の長さをすべて足し合わせた合計値のことです。

三角形の辺を a、b、c とすると、求めたい直角三角形は次の2つの条件を満たす必要があります。

• 周囲長の条件: a + b + c = P
• ピタゴラスの定理: a² + b² = c²(a、b、c のいずれの組み合わせに対しても成立)

探索は、a を 1 から p/2 まで、b を a+1 から p/3 まで変化させながら行い、c = p − a − b(a + b + c = p から導かれます)として求めます。

得られた各組み合わせに対してピタゴラスの定理を適用し、直角三角形かどうかを判定します。同時に、「どの2辺を選んでもその和が必ず残りの1辺より大きくなる」という三角形の成立条件も満たしていなければなりません。

それでは、具体例で確認してみましょう。

入出力例

例1: 周囲長 P = 12 の場合

入力: 周囲長 P = 12
出力: 直角三角形の総数:1

説明: a + b + c = P かつ a² + b² = c²(さらに任意の2辺の和が第3辺より大きい)を満たす a、b、c の組み合わせは 3・4・5 のみです。

4 + 3 + 5 = 12、3×3 + 4×4 = 5×5(9 + 16 = 25)であり、3 + 4 > 5、4 + 5 > 3、3 + 5 > 4 もすべて成り立っています。

例2: 周囲長 P = 10 の場合

入力: 周囲長 P = 10
出力: 直角三角形の総数:0

説明: a + b + c = P かつ a² + b² = c² を満たす a、b、c の組み合わせは存在しないため、答えは 0 になります。

アルゴリズムの考え方

以下のプログラムでは、次の手順で直角三角形の個数を数えています。

• 与えられた周囲長の値を格納する整数変数 perimeter を用意します。
• 関数 rightTriangles(int p) が周囲長を引数として受け取り、作成可能な直角三角形の総数を返します。
• 変数 count に直角三角形の個数を記録します(初期値は 0)。
• for ループで a を 1 から p/2 まで変化させます。
• ネストした for ループで b を a+1 から p/3 まで変化させます(直角三角形において等しい2辺は存在しないため)。
• c = p − a − b を計算し、(a+b>c && b+c>a && a+c>b) という三角形の成立条件を確認します。
• さらにピタゴラスの定理 a*a + b*b == c*c が成り立てば count をインクリメントします。
• 最終的な count の値が、その周囲長で作れる直角三角形の個数となります。

注意: 重複カウントを避けるため、ピタゴラスの定理の判定は a、b、c の1通りの組み合わせに限定しています。

なお、この手法の計算量は二重ループにより O(P²) となります。P が非常に大きい場合は、ピタゴラス数のパラメータ表示を利用することで、より効率的に求めることも可能です。

コード例

#include <bits/stdc++.h>
using namespace std;
int rightTriangles(int p){
    int count = 0;
    int c=0;
    for( int a=1;a<p/2;a++){
        for(int b=1;b<p/3;b++){
            c=p-a-b;
            if( a+b>c && b+c>a && a+c>b) //三角形の成立条件{
                if( (a*a+b*b)==c*c ) //直角三角形のピタゴラスの定理
                    { ++count; }
            }
        }
    }
    return count;
}
int main(){
    int perimeter= 12;
    cout << "Total number of right triangles that can be formed: "<<rightTriangles(perimeter);
    return 0;
}

出力結果

上記のコードを実行すると、次の出力が得られます。

Total number of right triangles that can be formed: 1