Trong bài viết này, chúng tôi sẽ giải thích cách giải số cặp cạnh huyền và diện tích có thể có của một tam giác vuông trong C ++.
Chúng ta cần xác định tất cả các cặp cạnh huyền và diện tích (H, A) có thể có để tạo thành một tam giác vuông với H là cạnh huyền và A là diện tích.
Trong ví dụ này -
x =Cơ sở của Tam giác Góc phải
y =Chiều cao của Tam giác Góc phải
H =cạnh huyền của Tam giác vuông góc
Chúng ta biết Diện tích tam giác vuông,
A =(x * y) / 2
Hoặc
4 * A 2 =(x * y) 2 …… (1)
Ngoài ra, chúng tôi biết
x 2 + y 2 =H 2 …… (2)
Giải quyết (1) &(2)
4 * A 2 =x 2 (H 2 - x 2 )
Giải phương trình bậc hai trong x2 và đặt D (phân biệt)> =0 (tồn tại x)
Chúng tôi nhận được, H2> =4 * A (điều kiện để tồn tại tam giác vuông)
Đây là ví dụ -
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 ). Phương pháp tiếp cận để tìm giải pháp
Bây giờ chúng ta sẽ sử dụng hai phương pháp khác nhau để thực hiện tác vụ đã cho -
Phương pháp tiếp cận vũ phu
Trong cách tiếp cận đơn giản này, chúng tôi tìm tất cả các cặp cạnh huyền và diện tích (H, A) có thể có, kiểm tra xem chúng có thỏa mãn điều kiện hay không, h2> =4 * A hoặc không, và đếm cho mọi cặp được tìm thấy thỏa mãn điều kiện này.
Ví dụ
#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;
} Đầu ra
Number of possible pairs of ( H, A ): 4
Giải thích
Trong đoạn mã này, chúng tôi sử dụng các biến đếm để giữ số lượng các cặp thỏa mãn phương trình và sử dụng các vòng lặp lồng nhau để tạo ra các cặp (H, A). Độ phức tạp về thời gian của mã này là O (n2), đây không phải là một cách tiếp cận hiệu quả. Hãy hiểu cách tiếp cận thứ hai.
Cách tiếp cận hiệu quả
Trong cách tiếp cận này, trước tiên chúng tôi sắp xếp cả hai mảng theo thứ tự tăng dần, sau đó chúng tôi tìm bất kỳ độ dài cạnh huyền nào để tìm diện tích tối đa khi kiểm tra H 2 > 4 * Đ .
Ví dụ
#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;
} Đầu ra
Number of possible pairs of ( H, A ): 4
Giải thích về Quy tắc trên
Trong đoạn mã này, trước tiên chúng tôi sắp xếp cả hai mảng theo thứ tự tăng dần, sau đó chúng tôi sẽ kiểm tra mọi độ dài có thể bằng cách sử dụng tìm kiếm nhị phân để tìm diện tích tối đa.
Giả sử khu vực lớn nhất được tìm thấy ở chỉ số 3 trong mảng của khu vực A [], thì tất cả các khu vực nhỏ hơn chỉ số ba cũng sẽ thỏa mãn phương trình để chúng ta có thể tạo thành 3 cặp có thể có.
Kết luận
Trong bài này, chúng tôi đã giải một bài toán để tìm số lượng các cặp Điểm huyền ảo và Diện tích sẽ được sử dụng để tạo một tam giác vuông. Chúng tôi đã áp dụng phương pháp Brute force, có độ phức tạp về Thời gian là O (n 2 ), và phương pháp Hiệu quả, có Độ phức tạp về thời gian là O (s1 log (s2)). Hy vọng bạn thấy bài viết này hữu ích.