Ermitteln Sie in C++ die Anzahl der Quadrupel, deren erste drei Terme arithmetische Folgen und deren letzte drei Terme geometrische Folgen sind.

In diesem Artikel beschreiben wir alle möglichen Wege, Quaternionen zu finden, bei denen die ersten drei Begriffe in A.P. und die letzten drei Begriffe in G.P. stehen. Zunächst erklären wir die grundlegenden Definitionen der arithmetischen Progression (A.P.) und der geometrischen Progression (G.P.).

Arithmetische Progression (A.P.) – Es handelt sich um eine Zahlenfolge, bei der die gemeinsame Differenz (d) gleich oder konstant ist, was bedeutet, dass die Differenz zweier aufeinanderfolgender Zahlen konstant ist. Zum Beispiel: 1,3,5,7,9 |. d = 2

Geometrische Progression (G.P.) – Dies ist eine Zahlenfolge, bei der das gemeinsame Verhältnis (r) gleich ist, was bedeutet, dass wir das vorherige multiplizieren können Nummerieren nach mit einer festen Nummer. Zum Beispiel: 3, 6, 12, 24, .... |. r = 2

In diesem Problem müssen wir bestimmen, wie viele Indexquadrupel (a, b, c) im Array arr[] von N ganzen Zahlen sind , D). Infolgedessen sind arr[a], arr[b] und arr[c] in A.P., während arr[d], arr[c] und arr[b] in G.P. sind. Alle darin enthaltenen Vier-Tupel sollten deterministisch sein. Hier ist das Beispiel –

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.

Methode zum Finden der Lösung

Nun beschreiben wir zwei verschiedene Methoden zum Finden der Lösung –

Brute-Force-Methode

Dies ist eine einfache Methode zum Lösen mithilfe von vier verschachtelten Schleifen. Diese Frage prüft dann, ob Die ersten drei Elemente sind in A.P. Wenn ja, prüfen Sie, ob die letzten drei Elemente in G.P. enthalten sind. Wenn ja, addieren Sie 1 zur Zählvariablen. Diese Methode ist jedoch sehr zeitaufwändig, da ihre Zeitkomplexität O(n4) ist.

Effiziente Methode

< p>Bei dieser Methode ermitteln wir zunächst die Anzahl jedes Array-Elements, betrachten dann diese beiden Elemente als zweite und dritte Zahl und führen zwei verschachtelte Schleifen aus, dann die erste. Die Elemente werden arr[b] – (arr[c ] – arr[b]) und das vierte Element wird arr[c] * arr[c] / arr[b] sein.

Beispiel

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

Ausgabe

Number of quadruples: 2

Erklärung des obigen Codes

In diesem Code verwenden wir Kombinatorik, verwenden zwei verschachtelte Schleifen für das zweite und dritte Element und verwenden arr[a] – (arr[c] findet das erste Element – ​​​​arr[b]) und das vierte Element arr[c] * arr[c] / arr[b]. Wenn man also das zweite und dritte Element festhält, entspricht die Anzahl der durch A und B indizierten Quaternionen der Anzahl der ersten Zahl * der vierten Zahl. Die Zeitkomplexität des obigen Codes beträgt O(n2).

Fazit

In diesem Artikel haben wir das Problem gelöst, Quaternionen zu finden, bei denen die ersten drei Terme in AP und die letzten drei Terme in GP sind. Wir haben die Verwendung von Bruteforce [ O(n4) ] und der effizienten Methode [ O (n2) besprochen ) ] Zwei Möglichkeiten, dieses Problem zu lösen.

Wir haben dieses Problem mit C++ gelöst, es kann auch in verschiedenen anderen Sprachen wie Java, Python, C oder jeder anderen Programmiersprache gelöst werden.

Das obige ist der detaillierte Inhalt vonErmitteln Sie in C++ die Anzahl der Quadrupel, deren erste drei Terme arithmetische Folgen und deren letzte drei Terme geometrische Folgen sind.. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!