หาจำนวนคู่ Hypotenuse และ Area ที่สร้างสามเหลี่ยมมุมฉากได้ด้วย C++

ในบทความนี้ เราจะอธิบายวิธีแก้ปัญหาการหาจำนวนคู่ของ Hypotenuse (ด้านตรงข้ามมุมฉาก) และ Area (พื้นที่) ที่สร้างสามเหลี่ยมมุมฉากได้ใน C++

เราต้องหาจำนวนคู่ที่เป็นไปได้ทั้งหมดของ Hypotenuse และ Area (H, A) เพื่อสร้างสามเหลี่ยมมุมฉากที่มี H เป็น Hypotenuse และ A เป็น Area

ในตัวอย่างนี้:

x = ฐานของสามเหลี่ยมมุมฉาก

y = สูงของสามเหลี่ยมมุมฉาก

H = Hypotenuse ของสามเหลี่ยมมุมฉาก

เรารู้พื้นที่ของสามเหลี่ยมมุมฉาก:

A = (x × y) / 2

หรือ

4 × A² = (x × y)² ...... (1)

และเรายังรู้ว่า

x² + y² = H² ...... (2)

แก้สมการ (1) และ (2)

4 × A² = x² (H² - x²)

แก้สมการกำลังสองใน x² และตั้ง D (Discriminant) ≥ 0 (เพื่อให้ x มีอยู่)

เราได้ H² ≥ 4 × A (เงื่อนไขสำหรับสามเหลี่ยมมุมฉากจะมีอยู่)

ตัวอย่าง:

Input : array H[ ] = { 3, 6, 8 } : A[ ] = { 2, 31, 12 } Output : 4 Explanation : คู่ (H, A) ที่เป็นไปได้คือ (3, 2), (6, 2), (8, 2) และ (8, 12)
Input : array H[ ] = { 2, 5, 9 } : A[ ] = { 3, 11, 7 } Output : 4 Explanation : คู่ (H, A) ที่เป็นไปได้คือ (5, 3), (9, 3), (9, 11) และ (9, 7)

วิธีการหาคำตอบ

ตอนนี้เราจะใช้สองวิธีที่แตกต่างกันในการทำงานที่กำหนด:

1. วิธี Brute Force

ในวิธีง่ายๆ นี้ เราหาคู่ที่เป็นไปได้ทั้งหมดของ Hypotenuse และ Area (H, A) ตรวจสอบว่าตอบโจทย์เงื่อนไข H² ≥ 4 × A หรือไม่ และนับทุกคู่ที่พบซึ่งตอบโจทย์เงื่อนไขนี้

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

int main() {
    int H[] = { 2, 5, 9 }; // อาร์เรย์ของ Hypotenuse
    int s1 = sizeof(H) / sizeof(H[0]);
    int A[] = { 3, 11, 7 }; // อาร์เรย์ของ Area
    int s2 = sizeof(A) / sizeof(A[0]);
    int count = 0; // เริ่มต้น count เป็น 0
    
    // หาคู่ที่เป็นไปได้ทั้งหมด
    for (int i = 0; i < s1; i++) {
        for (int j = 0; j < s2; j++) {
            // ตรวจสอบว่าคู่ปัจจุบันตอบโจทย์เงื่อนไขหรือไม่
            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

คำอธิบาย

ในโค้ดนี้ เราใช้ตัวแปร count เพื่อนับจำนวนคู่ที่ตอบโจทย์สมการ และใช้ nested loops เพื่อสร้างคู่ (H, A) ความซับซ้อนด้านเวลาของโค้ดนี้คือ O(n²) ซึ่งไม่ใช่วิธีที่มีประสิทธิภาพ มาเข้าใจวิธีที่สอง

2. วิธีที่มีประสิทธิภาพ (Efficient Approach)

ในวิธีนี้ เราจัดเรียง (sort) ทั้งสองอาร์เรย์ในลำดับน้อยไปมาก (ascending) แล้วเราหาความยาว Hypotenuse ใดๆ เพื่อหาพื้นที่สูงสุด (maximum area) โดยตรวจสอบ H² > 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;
    
    // จัดเรียงทั้งสองอาร์เรย์
    sort(H, H + s1);
    sort(A, A + s2);
    
    int temp = -1;
    for (int i = 0; i < s1; i++) {
        // ใช้ Binary Search สำหรับ
        // ทุกความยาว Hypotenuse
        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) { // ตรวจสอบว่ามีพื้นที่ที่เป็นไปได้หรือไม่
            count += temp + 1;
        }
    }
    cout << "Number of possible pairs of (H, A): " << count;
    return 0;
}

ผลลัพธ์

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

คำอธิบายโค้ด

ในโค้ดนี้ เราจัดเรียงทั้งสองอาร์เรย์ในลำดับน้อยไปมาก ก่อน แล้วเราตรวจสอบสำหรับความยาวที่เป็นไปได้ทุกค่าโดยใช้ Binary Search เพื่อหาพื้นที่สูงสุด

สมมติว่าพื้นที่สูงสุดพบที่ดัชนี 3 ในอาร์เรย์ของพื้นที่ A[] แล้วพื้นที่ทั้งหมดที่น้อยกว่าดัชนี 3 ก็จะตอบโจทย์สมการเช่นกัน ดังนั้นเราสามารถสร้างคู่ได้ 3 คู่

สรุป

ในบทความนี้ เราแก้ปัญหาการหาจำนวนคู่ของ Hypotenuse และ Area ที่จะนำไปสร้างสามเหลี่ยมมุมฉาก เราใช้วิธี Brute Force ที่ความซับซ้อนด้านเวลาคือ O(n²) และวิธีที่มีประสิทธิภาพที่ความซับซ้อนด้านเวลาคือ O(s1 log(s2)) หวังว่าบทความนี้จะเป็นประโยชน์