C++ Fragen Sie die Wahrscheinlichkeit gerader oder ungerader Zahlen in einem bestimmten Bereich ab

Finden Sie die Paritätswahrscheinlichkeit einer Zahl in einem bestimmten Bereich, d. h. ob es sich um eine gerade oder eine ungerade Zahl handelt. Für jede Abfrage müssen wir p und q ausgeben, z. B. die Wahrscheinlichkeit mit p / q bezeichnen.

Input : N = 5, arr[] = { 6, 5, 2, 1, 7 }
query 1: 0 2 2
query 2: 1 2 5
query 3: 0 1 4

Output : 0
3 4
1 2

In diesem Problem werden wir zwei Arrays verwalten, die ungerade und gerade Mengen bis zu diesem Index enthalten. Dies vereinfacht unser Problem, jetzt müssen wir ihre Anzahl und die Anzahl der im Bereich vorhandenen Elemente ausdrucken.

Lösungsmethode

Bei dieser Methode verwalten wir zwei Arrays. Sie enthalten die Anzahl der gefundenen geraden und ungeraden Zahlen bis zum i-ten Index und lösen das Problem wie ein Präfixsummenproblem.

Beispiel

#include <bits/stdc++.h>
using namespace std;
void solve(int arr[], int n, int Q,int query[][3]){
    int even[n + 1]; // our array for counting the number of evens find till ith index
    int odd[n + 1]; // our array for counting the number of odds find till ith index
    even[0] = 0; odd[0] = 0; // as we are doing 1 based indexing so we just set 0th index of both arrays to 0
    for (int i = 0; i < n; i++) {
        if (arr[i] & 1) { // if we found odd number we increment odd
            odd[i + 1] = odd[i] + 1;
            even[i + 1] = even[i];
        }
        else { // else we increment even
            even[i + 1] = even[i] + 1;
            odd[i + 1] = odd[i];
        }
    }
    for (int i = 0; i < Q; i++) { // traversing the queries
        int r = query[i][2]; // right range
        int l = query[i][1]; // left range
        int k = query[i][0]; // type of query
        int q = r - l + 1; // number of elements in the given range
        int p;
        if (k) // k is the type of query and we are finding the
            //number of elements with same parity in the given range
            p = odd[r] - odd[l - 1];
        else
            p = even[r] - even[l - 1];
        if (!p) // if p is zero we simply print 0
            cout << "0\n";
        else if (p == q) // if p == q we print 1
            cout << "1\n";
        else {
            int g = __gcd(p, q);
            cout << p / g << " " << q / g << "\n"; // as p and shouldn&#39;t have a common gcd so we divide the gcd
        }
    }
}
int main(){
    int arr[] = { 6, 5, 2, 1, 7 }; // given array
    int n = sizeof(arr) / sizeof(int); // size of our array
    int Q = 2; // number of our queries
    int query[Q][3] = {{ 0, 2, 2 },{ 1, 2, 5 }}; // given queries
    solve(arr, n, Q, query);
    return 0;
}

Ausgabe

0
3 4

Erklärung des obigen Codes

In der obigen Methode zählen wir die Anzahl der gefundenen geraden und ungeraden Zahlen bis zum i-ten Index, indem wir zwei Arrays verwalten. Jetzt müssen wir die Anzahl der geraden oder ungeraden Zahlen in einem bestimmten Bereich ermitteln und diese Zahl sowie die Gesamtzahl des Vorkommens von Elementen ausgeben.

Fazit

In diesem Tutorial haben wir die Frage nach der Wahrscheinlichkeit einer geraden oder ungeraden Zahl in einem bestimmten Bereich gelöst. Wir haben auch das C++-Programm für dieses Problem und unsere vollständige Methode zur Lösung dieses Problems (normale Methode) gelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen schreiben. Ich hoffe, Sie fanden dieses Tutorial hilfreich.

Das obige ist der detaillierte Inhalt vonC++ Fragen Sie die Wahrscheinlichkeit gerader oder ungerader Zahlen in einem bestimmten Bereich ab. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!