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

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

WBOY

リリース： 2023-09-08 14:05:07

転載

1008 人が閲覧しました

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;
}

ログイン後にコピー