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

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

WBOY

發布： 2023-09-08 14:05:07

轉載

1053 人瀏覽過

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

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

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

在這個範例中-

x = 直角三角形的底

y = 直角三角形的高度

邊距 #

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

A = ( x * y ) / 2

或

4 * A

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

我們也知道

2^y2^=H2^{… (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;
}

登入後複製

輸出