使用C++编程找到可能的直角三角形的斜边和面积的配对数量

在本文中，我们将解释如何在 C++ 中求解形成直角三角形的斜边和面积的可能对的数量。

我们需要确定 a 的所有可能对的数量斜边和面积 ( H, A ) 形成一个直角三角形，其中 H 为斜边，A 为面积。

在此示例中 -

         x = 直角三角形的底

立即学习“C++免费学习笔记（深入）”；

         y = 直角三角形的高度

         H = 直角三角形的斜边

我们知道直角三角形的面积，

A = ( x * y ) / 2

或

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

我们也知道

x² + 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 ).

解决方案的方法

现在我们将使用两种不同的方法来执行给定的任务 -

蛮力法

在这种简单的方法中，我们找到所有可能的斜边和面积（H，A）的组合，检查它们是否满足条件h2 >= 4 * A，并计算满足此条件的每对组合的数量。

示例

#include 
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² > 4 * A。

示例

#include 
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))。希望这篇文章对您有所帮助。