이 기사에서는 C++에서 직각삼각형을 형성하는 빗변과 넓이의 가능한 쌍의 수를 푸는 방법을 설명합니다.
H를 빗변으로, A를 면적으로 하는 직각 삼각형을 형성하려면 빗변과 면적( H, A )의 가능한 모든 쌍의 수를 결정해야 합니다.
이 예에서 -
x =직각 삼각형의 밑변
y =직각 삼각형의 높이
H =직각 삼각형의 빗변
우리는 직각 삼각형의 넓이를 알고 있습니다.
A =( x * y ) / 2
또는
4 * A 2 =( x * y ) 2 …… (1)
또한 우리는 알고 있습니다
x 2 + y 2 =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))인 효율적인 접근 방식입니다. 이 기사가 도움이 되기를 바랍니다.