C++ プログラミングを使用して、可能な斜辺と直角三角形の面積のペアの数を求めます。

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

直角三角形を形成する斜辺と面積 ( H, A ) のすべての可能なペアの数を決定する必要があります。ここで、 H は斜辺、 A は面積です。

この例では、

x = 直角三角形の底辺

y = 直角三角形の高さ

H = 直角三角形の斜辺

直角三角形の面積はわかっています、

A = ( x * y ) / 2

または

4 * A² = ( x * y )² … ... (1)

我々も知っています

xx² y² =H ² …… (2)

解決策 (1) & (2)

4 * A² = x ² ( H ² - x² )

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

説明

このコードでは、count 変数を使用して方程式を満たすペアの数を保持します。埋め込みを使用する ループのセットにより (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

上記のコードの説明

このコードでは、まず 2 つの配列を昇順で並べ替えてから、Binary を使用します。検索では、可能な限りすべての長さをチェックして、最大の領域を見つけます。

最大面積が領域 A[ ] の配列内のインデックス 3 で見つかったと仮定すると、インデックス 3 より小さいすべての領域もこの式を満たすため、3 つの可能なペアを形成できます。

>

結論

この記事では、直角三角形を形成するために使用される斜辺と面積のペアの数を求める問題を解決しました。時間計算量が O(n²) の総当たりアプローチと、時間計算量が O(s1 log(s2)) の効率的なアプローチを適用しました。この記事がお役に立てば幸いです。

以上がC++ プログラミングを使用して、可能な斜辺と直角三角形の面積のペアの数を求めます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。