使用C++程式找到可能的直角三角形的斜邊和麵積的配對數量

在本文中，我們將解釋如何在 C 中求解形成直角三角形的斜邊和麵積的可能對的數量。

我們需要確定 a 的所有可能對的數量斜邊和麵積 ( H, A ) 形成一個直角三角形，其中 H 為斜邊，A 為面積。

在這個範例中-

         x = 直角三角形的底

         y = 直角三角形的高度

  邊距 # 

#我們知道直角三角形的面積，

A = ( x * y ) / 2

或

4 * A

2 ^{= ( x * y )}2          ^{… ... (1)}

我們也知道

x

2 ^y2 ^=H 2 ^{… (2)}

解(1) & (2)

#4 * A

2 ^{= x}2 ^{( H} 2 ^{- 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 ).

解決方案的方法

現在我們將使用兩種不同的方法來執行給定的任務-

蠻力法

在這種簡單的方法中，我們找到所有可能的斜邊和麵積（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)，這不是一種有效的方法。讓我們來了解第二種方法。

高效的方法

在這種方法中，我們首先按升序對兩個陣列進行排序，然後找到任何斜邊長度來找到最大面積檢查

H 2 ^{> 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

2^{)，以及高效率方法，其時間複雜度為 O(s1 log(s2))。希望這篇文章對您有幫助。}

以上是使用C++程式找到可能的直角三角形的斜邊和麵積的配對數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！