Écrit en C++, trouvez le nombre de quadruples dont les trois premiers termes sont des séquences arithmétiques et les trois derniers termes sont des séquences géométriques.

Dans cet article nous décrirons toutes les manières possibles de trouver des quaternions, où les 3 premiers termes sont en A.P. et les 3 derniers termes sont en G.P. Tout d’abord, nous expliquerons les définitions de base de la progression arithmétique (A.P.) et de la progression géométrique (G.P.).

Progression arithmétique (A.P.) - C'est une séquence de nombres où la différence commune (d) est la même ou constante, ce qui signifie que la différence de deux nombres consécutifs est constante. Par exemple : 1,3,5,7,9 | d = 2

Progression géométrique (G.P.) - Il s'agit d'une séquence de nombres où la raison (r) est la même, ce qui signifie que nous pouvons multiplier la précédente numéroter par avec un numéro fixe. Par exemple : 3, 6, 12, 24, .... | r = 2

Dans ce problème, nous devons déterminer combien de quadruples d'index (a, b, c) se trouvent dans le tableau arr[] de N entiers , d). En conséquence, arr[a], arr[b] et arr[c] sont dans A.P., tandis que arr[d], arr[c] et arr[b] sont dans G.P. Les quatre tuples qu'il contient doivent être déterministes. Voici l'exemple -

Input : arr[ ] = { 9, 6, 4, 2, 1, 2 }
Output : 2
Explanation: Elements in the quadruples are at { 3, 2, 1, 0 } and { 5, 2, 1, 0 } indexes where quadruples are { 2, 4, 6, 9 } for both positions.

Input : arr[ ] = { 2, 6, 1, 4, 2 }
Output : 2
Explanation: Elements in the quadruples are at { 1, 3, 0, 2 } and { 1, 3, 4, 2 } indexes where quadruples are { 6, 4, 2, 1 } for both positions.

Méthode pour trouver la solution

Nous allons maintenant décrire deux méthodes différentes pour trouver la solution -

Méthode de la force brute

Il s'agit d'une méthode simple à résoudre à l'aide de quatre boucles imbriquées. Cette question vérifie ensuite si les trois premiers éléments sont dans A.P. Si oui, vérifiez si les 3 derniers éléments sont dans G.P. Si tel est le cas, ajoutez 1 à la variable count. Cependant, cette méthode prend beaucoup de temps car sa complexité temporelle est O(n4).

Méthode efficace

Dans cette méthode, nous trouvons d'abord le nombre de chaque élément du tableau, puis considérons ces deux éléments comme des deuxième et troisième nombres et exécutons deux boucles imbriquées puis la première. Les éléments seront arr[b] – (arr[c ] – arr[b]) et le quatrième élément sera arr[c] * arr[c] / arr[b].

Exemple

#include <bits/stdc++.h>
using namespace std;
int main (){
    unordered_map < int, int >map;
    int arr[] = { 2, 6, 1, 4, 2 };
    int size = sizeof (arr) / sizeof (arr[0]);
    // Processing every elent and increasing the count
    for (int a = 0; a < size; a++)
      map[arr[a]]++;

    int count = 0;
    // Running two nested loops for second & third element
    for (int b = 0; b < size; b++){
        for (int c = 0; c < size; c++){
            if (b == c)
                continue;
                // Decreasing the count
                map[arr[b]]--;
            map[arr[c]]--;
            // Finding the first element using common difference
            int first = arr[b] - (arr[c] - arr[b]);
            // Finding the fourth element using GP
            int fourth = (arr[c] * arr[c]) / arr[b];
            if ((arr[c] * arr[c]) % arr[b] == 0){
                // Increment count if not equal
                if (arr[b] != arr[c])
                    count += map[first] * map[fourth];
                else
                 count += map[first] * (map[fourth] - 1);
            }
            map[arr[b]]++;
            map[arr[c]]++;
        }
    }
    cout <<"Number of quadruples: " << count;
    return 0;
}

Output

Number of quadruples: 2

Explication du code ci-dessus

Dans ce code, nous utilisons la combinatoire, en utilisant deux boucles imbriquées pour les deuxième et troisième éléments, et en utilisant arr[a] – (arr[c] trouve le premier élément – ​​​​arr[b]) et le quatrième élément arr[c] * arr[c] / arr[b]. Ainsi, en gardant les deuxième et troisième éléments fixes, le nombre de quaternions indexés par A et B est le décompte du premier nombre * le quatrième nombre. La complexité temporelle du code ci-dessus est O(n2).

Conclusion

Dans cet article, nous avons résolu le problème de trouver des quaternions où les trois premiers termes sont en AP et les trois derniers termes sont en GP. Nous avons discuté de l'utilisation de Bruteforce [ O(n4) ] et de la méthode efficace [ O (n2). ) ] Deux façons de résoudre ce problème.

Nous avons résolu ce problème en utilisant C++, cela peut également être résolu dans divers autres langages comme Java, Python, C ou tout autre langage de programmation.

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!