C ++を使用して、直角三角形を形成する斜辺と面積の可能なペアの数を見つけます

この記事では、C++で直角三角形を形成する斜辺と面積の可能なペアの数を解決する方法を説明します。

斜辺と面積（H、A）のすべての可能なペアの数を決定して、Hを斜辺、Aを面積とする直角三角形を形成する必要があります。

この例では-

x=直角三角形の底

y=直角三角形の高さ

H=直角三角形の斜辺

直角三角形の面積を知っています

A =（x * y）/ 2

または

4 * A ² =（x * y） ² ……（1）

また、私たちは知っています

x ² + y ² =H ² ……（2）

（1）と（2）を解く

4 * A ² =x ² （H ² -x ² ）

2次方程式をx2で解き、D（判別式）> =0（xが存在する場合）

H2> =4 * A （直角三角形が存在するための条件）

これが例です-

Input : array H[ ] = { 3, 6, 8 } : A[ ] = { 2, 31, 12 }
Output : 4
Explanation : possible pairs of Hypotenuse and Area ( H, A ) are ( 3, 2 ), ( 6, 2 ), ( 8, 2 ) and ( 8, 12 ).

Input : array H[ ] = { 2, 5, 9 } : A[ ] = { 3, 11, 7 }
Output : 4
Explanation : possible pairs of Hypotenuse and Area ( H, A ) are possible pairs of Hypotenuse and Area ( H, A ) are ( 5, 3 ), ( 9, 3 ), ( 9, 11 ) and ( 9, 7 ).

解決策を見つけるためのアプローチ

次に、2つの異なる方法を使用して、特定のタスクを実行します-

ブルートフォースアプローチ

この単純なアプローチでは、斜辺と面積（H、A）の可能なすべてのペアを見つけ、それらが条件 h2> =4 * Aを満たしているかどうかを確認します。 かどうか、そしてこの条件を満たすすべてのペアが見つかったとカウントします。

例

#include <iostream>
using namespace std;
int main(){
    int H[ ] = { 2,5,9}; // array of hypotenuse
    int s1 = sizeof(H)/sizeof(H[0]);
    int A[ ] = { 3, 11, 7};// array of area
    int s2 = sizeof(A)/sizeof(A[0]);
    int count = 0;// initialising count to 0
    // finding all possible pairs
    for (int i = 0; i < s1; i++) {
        for (int j = 0; j < s2; j++) {
            // checking whether current pair satisfies the condition
            if (H[i] * H[i] >= 4 * A[j]){
                count++;

            }
        }
    }
    cout << "Number of possible pairs of ( H, A ): " << count ;
    return 0;
}

出力

Number of possible pairs of ( H, A ): 4

説明

このコードでは、カウント変数を使用して方程式を満たすペアのカウントを維持し、ネストされたループを使用して（H、A）ペアを生成します。このコードの時間計算量はO（n2）であり、効率的なアプローチではありません。 2番目のアプローチを理解しましょう。

効率的なアプローチ

このアプローチでは、最初に両方の配列を昇順で並べ替え、次に斜辺の長さを見つけて、 H ² をチェックする際の最大領域を見つけます。> 4 * A 。

例

#include <bits/stdc++.h>
using namespace std;
int main (){
    int H[] = { 2, 5, 9 };
    int s1 = sizeof (H) / sizeof (H[0]);
    int A[] = {  3, 11, 7 };
    int s2 = sizeof (A) / sizeof (A[0]);
    int count = 0;
    // Sorting both the arrays
    sort (H, H + s1);
    sort (A, A + s2);
    int temp = -1;
    for (int i = 0; i < s1; i++){
        // Applying binary search for
        // every Hypotenuse Length
        int flag1 = 0;
        int flag2 = s2 - 1;
        while (flag1 <= flag2){
            int mid = flag1 + (flag2 - flag1) / 2;
            if ((H[i] * H[i]) >= (4 * A[mid])){
                temp = mid;
                flag1 = mid + 1;
            }
            else{
                flag2 = mid - 1;
            }
        }
        if (temp != -1){// Check if we get any possible area
            count += temp + 1;
        }
    }
    cout << "Number of possible pairs of (H, A): " << count;
    return 0;
}

出力

Number of possible pairs of ( H, A ): 4

上記のコードの説明

このコードでは、最初に両方の配列を昇順で並べ替えてから、最大面積を見つけるためにバイナリ検索を使用して可能なすべての長さをチェックしています。

最大面積が面積A[]の配列のインデックス3にあるとすると、インデックス3未満のすべての面積も方程式を満たし、3つの可能なペアを形成できます。

結論

この記事では、問題を解決して、直角三角形を作成するために使用される斜辺と面積のペアの数を見つけました。時間計算量がO（n ² であるブルートフォースアプローチを適用しました ）、および時間計算量がO（s1 log（s2））である効率的なアプローチ。この記事がお役に立てば幸いです。