C++ Interroger la probabilité d'avoir des nombres pairs ou impairs dans une plage donnée

Trouvez la probabilité de parité d'un nombre dans une plage donnée, c'est-à-dire s'il s'agit d'un nombre pair ou d'un nombre impair. Pour chaque requête, nous devons imprimer p et q, par exemple désigner la probabilité par p / q.

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

Dans ce problème, nous maintiendrons deux tableaux contenant des quantités paires et impaires jusqu'à cet index. Cela simplifie notre problème, nous devons maintenant imprimer leur numéro et le nombre d'éléments présents dans la gamme.

Méthode de solution

Dans cette méthode, nous maintenons deux tableaux. Ils contiennent le nombre de nombres pairs et impairs trouvés jusqu'au i-ième indice et résolvent le problème comme un problème de somme de préfixes.

Exemple

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

Sortie

0
3 4

Explication du code ci-dessus

Dans la méthode ci-dessus, nous comptons le nombre de nombres pairs et impairs trouvés jusqu'au i-ème index en maintenant deux tableaux. Nous devons maintenant trouver le nombre de nombres pairs ou impairs dans une plage donnée, imprimer ce nombre et imprimer le nombre total d'occurrences d'éléments.

Conclusion

Dans ce tutoriel, nous avons résolu la question sur la probabilité d'un nombre pair ou impair dans une plage donnée. Nous avons également appris le programme C++ pour ce problème et notre méthode complète pour résoudre ce problème (méthode normale). Nous pouvons écrire le même programme dans d'autres langages comme C, Java, Python et autres. J'espère que vous avez trouvé ce tutoriel 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!