Trouver le nombre de paires possibles d'hypoténuses et d'aires d'un triangle rectangle en utilisant la programmation C++

Dans cet article, nous expliquerons comment trouver le nombre de paires possibles qui forment l'hypoténuse et l'aire d'un triangle rectangle en C++.

Nous devons déterminer le nombre de toutes les paires possibles d'une hypoténuse et d'une aire ( H, A ) formant un triangle rectangle où H est l'hypoténuse et A est l'aire.

Dans cet exemple -

                                                                                                    à travers les ' s à l'utilisation de

à

-- / 2

ou

4 * A

2

= ( x * y )

2

… … (1 )Nous savons aussi x

2

+ y

2

=H² … (2)Résoudre (1) & (2)4 * A

2

= x

2

( H ² - x² )Résolvez l'équation quadratique en x2 et laissez D (discriminant) >= 0 (x existe) On obtient,

H2 >= 4 * A

(Condition pour qu'un triangle rectangle soit existent)

Voici l'exemple-

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

Méthode de solution

Maintenant, nous allons utiliser deux méthodes différentes pour effectuer la tâche donnée -

Méthode de la force brute

Dans cette méthode simple, nous trouvons toutes les combinaisons possibles d'hypoténuse et zone (H,A), vérifiez s'ils satisfont à la condition

h2 >= 4 * A

, et comptez le nombre de chaque paire de combinaisons qui satisfont cette condition.

Exemple

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

Sortie

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

Explication

Dans ce code, nous utilisons une variable de comptage pour contenir le nombre de paires qui satisfont l'équation et utilisons une boucle imbriquée pour générer la paire ( H, A ). La complexité temporelle de ce code est O(n2), ce qui n'est pas une approche efficace. Comprenons la deuxième méthode.

Méthode efficace

Dans cette méthode, nous trions d'abord les deux tableaux par ordre croissant, puis trouvons la surface maximale en trouvant toute longueur d'hypoténuse en vérifiant

H

2

> 4 * A

. ^Exemple

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

Sortie

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

Explication du code ci-dessus

Dans ce code, nous trions d'abord les deux tableaux par ordre croissant, puis vérifions chaque longueur possible en utilisant la recherche binaire pour trouver la région maximale.

Supposons que l'aire maximale se trouve à l'indice 3 dans le tableau de la région A[ ], alors toutes les régions plus petites que l'indice 3 satisfont également à cette équation, nous pouvons donc former 3 paires possibles.

>

Conclusion

Dans cet article, nous avons résolu le problème de trouver le nombre de paires d'hypoténuse et d'aire utilisées pour former un triangle rectangle. Nous avons appliqué une approche par force brute, qui a une complexité temporelle de O(n

2

), et une approche efficace, qui a une complexité temporelle de O(s1 log(s2)). J'espère que cet article vous sera utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!