C++ 프로그래밍을 사용하여 빗변과 직각삼각형의 가능한 쌍 수 찾기

이 글에서는 C++에서 직각삼각형의 빗변과 넓이를 이루는 가능한 쌍의 개수를 구하는 방법을 설명하겠습니다.

H는 빗변이고 A는 넓이인 직각 삼각형을 형성하는 빗변과 넓이(H, A)의 가능한 모든 쌍의 수를 결정해야 합니다.

이 예에서는 -

                                                                                                             's'를 통해

의 사용은

-- / 2

또는

4 * A

2

= ( x * y )

2

… … (1 )우리는 또한 x

2

+ y

2

=H² … (2)(1) & (2)4 * A

2

= x

2

( H ² - x² ) x2에서 2차 방정식을 풀고 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 ).

해결 방법

이제 우리는 주어진 작업을 수행하는 데 두 가지 다른 방법이 사용됩니다 -

무차별 대입 방법

이 간단한 방법에서 우리는 빗변과 빗변의 가능한 모든 조합을 찾습니다. Area (H,A)에서

h2 >= 4 * A

조건을 만족하는지 확인하고, 이 조건을 만족하는 각 조합 쌍의 개수를 셉니다.

Example

#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

Explanation

이 코드에서는 count 변수를 사용하여 방정식을 만족하는 쌍의 수를 유지하고 중첩 루프를 사용하여 (H, A ) 쌍을 생성합니다. 이 코드의 시간 복잡도는 O(n2)이며 이는 효율적인 접근 방식이 아닙니다. 두 번째 방법을 이해해 봅시다.

효율적인 방법

이 방법에서는 먼저 두 배열을 모두 오름차순으로 정렬한 다음 빗변 길이 검사(

H

2

> 4 * A

)를 찾아 최대 면적을 찾습니다. ^Example

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

Output

Number of possible pairs of ( H, A ): 4

위 코드 설명

이 코드에서는 먼저 두 배열을 오름차순으로 정렬한 다음 이진 검색을 사용하여 가능한 모든 길이를 확인하여 최대 영역을 찾습니다.

최대 면적이 영역 A[ ] 배열의 인덱스 3에서 발견된다고 가정하면 인덱스 3보다 작은 모든 영역도 이 방정식을 만족하므로 3개의 가능한 쌍을 형성할 수 있습니다.

>

결론

이 글에서는 직각삼각형을 이루는 데 사용되는 빗변과 넓이의 쌍 수를 구하는 문제를 해결했습니다. 우리는 O(n

2

)의 시간 복잡도를 갖는 무차별 접근 방식과 O(s1 log(s2))의 시간 복잡도를 갖는 효율적인 접근 방식을 적용했습니다. 이 기사가 도움이 되기를 바랍니다.

위 내용은 C++ 프로그래밍을 사용하여 빗변과 직각삼각형의 가능한 쌍 수 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!