Cari bilangan pasangan hipotenus yang mungkin dan luas segi tiga tepat menggunakan pengaturcaraan C++

Dalam artikel ini, kami akan menerangkan cara mencari bilangan pasangan yang mungkin yang membentuk hipotenus dan luas segi tiga tepat dalam C++.

Kita perlu menentukan bilangan semua pasangan hipotenus yang mungkin dan luas ( H, A ) membentuk segi tiga tepat di mana H ialah hipotenus dan A ialah luas.

Dalam contoh ini -

                                                                                                                                                                                                                                                                                                             melalui 's 's ke

-- / 2

atau

4 * A

2

= ( x * y )

… (1)

…

x² + y² =H

2

… (2)

Selesaikan (1) & (2)4 * A² = x² - x

2

2

)Selesaikan persamaan kuadratik dalam x2 dan biarkan D (diskriminan) >= 0 (x wujud) Kita dapat, ^{H2 >= 4 * A} (Syarat untuk segi tiga tepat wujud) contoh-

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 ).

Kaedah penyelesaian

Sekarang kita akan Dua kaedah berbeza digunakan untuk melaksanakan tugasan yang diberikan - Kaedah brute force

Dalam kaedah mudah ini kita dapati semua kemungkinan kombinasi hipotenus dan luas (H,A) , semak sama ada mereka memenuhi syarat

h2 >= 4 * A

, dan kira bilangan setiap pasangan gabungan yang memenuhi syarat ini.

Contoh

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

Output

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

PenjelasanDalam kod ini, kami menggunakan pembolehubah kiraan untuk menahan bilangan pasangan yang memenuhi persamaan dan menggunakan gelung bersarang untuk menjana pasangan ( H, A). Kerumitan masa kod ini ialah O(n2), yang bukan pendekatan yang cekap. Mari kita fahami kaedah kedua.

Kaedah yang cekap

Dalam kaedah ini kita mula-mula menyusun kedua-dua tatasusunan dalam tertib menaik dan kemudian mencari kawasan maksimum dengan mencari sebarang semakan panjang hipotenus

H

2

> 4 * A

.

Contoh

#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

^{Penjelasan kod di atas}Dalam kod ini, kami mula-mula mengisih dua tatasusunan dalam tertib menaik dan kemudian menyemak setiap panjang yang mungkin menggunakan carian binari untuk mencari rantau maksimum.

Andaikan luas maksimum ditemui pada indeks 3 dalam tatasusunan wilayah A[ ], maka semua wilayah yang lebih kecil daripada indeks 3 juga memenuhi persamaan ini, jadi kita boleh membentuk 3 pasangan yang mungkin.

>

Kesimpulan

Dalam artikel ini, kami menyelesaikan masalah mencari bilangan pasangan hipotenus dan luas yang digunakan untuk membentuk segi tiga tepat. Kami menggunakan pendekatan kekerasan, yang mempunyai kerumitan masa O(n

2

), dan pendekatan yang cekap, yang mempunyai kerumitan masa O(s1 log(s2)). Semoga artikel ini bermanfaat kepada anda.

Atas ialah kandungan terperinci Cari bilangan pasangan hipotenus yang mungkin dan luas segi tiga tepat menggunakan pengaturcaraan C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!