ในบทความนี้ เราจะอธิบายวิธีแก้จำนวนคู่ของด้านตรงข้ามมุมฉากและพื้นที่ที่เป็นไปได้จากสามเหลี่ยมมุมฉากใน 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 (discriminant)>=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 * ก .
ตัวอย่าง
#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
คำอธิบายของโค้ดด้านบน
ในโค้ดนี้ ขั้นแรกเราจะจัดเรียงอาร์เรย์ทั้งสองตามลำดับจากน้อยไปมาก จากนั้นเราจะตรวจสอบความยาวที่เป็นไปได้ทั้งหมดโดยใช้การค้นหาแบบไบนารีเพื่อหาพื้นที่สูงสุด
สมมติว่าพบพื้นที่สูงสุดที่ดัชนี 3 ในอาร์เรย์ของพื้นที่ A[ ] จากนั้นพื้นที่ทั้งหมดที่น้อยกว่าดัชนี 3 จะเป็นไปตามสมการด้วย เพื่อให้เราสร้างคู่ที่เป็นไปได้ 3 คู่
บทสรุป
ในบทความนี้ เราแก้ไขปัญหาเพื่อค้นหาจำนวนคู่ด้านตรงข้ามมุมฉากและคู่พื้นที่ที่จะใช้สร้างสามเหลี่ยมมุมฉาก เราใช้แนวทาง Brute force ซึ่งความซับซ้อนของเวลาคือ O(n 2 ) และแนวทางที่มีประสิทธิภาพ ซึ่งความซับซ้อนของเวลาคือ O(s1 log(s2)) หวังว่าบทความนี้จะเป็นประโยชน์
