数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究给定范围内的偶数或奇数概率的 C++ 查询
找到数字奇偶性的概率，即它是偶数还是奇数，以及给定的范围。对于每个查询，我们需要打印表示概率的 p 和 q，例如 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在这个问题中，我们将维护两个数组，分别包含直到该索引存在的奇数和偶数的数量。这简化了我们的问题，现在我们需要打印它们的计数以及该范围内存在的元素数量。
查找解决方案的方法
在这种方法中，我们维护两个数组。它们包含直到第 i 个索引找到的偶数和奇数的数量，并像前缀和问题一样解决此问题。
示例
#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'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;
}输出
0 3 4
以上代码的解释
在上述方法中，我们通过维护两个数组来计算到第 i 个索引找到的偶数和奇数的数量。现在我们需要找到给定范围内存在的偶数或奇数的数量并打印该数字，并打印存在的元素总数。
结论
在本教程中，我们解决了给定范围内偶数或奇数概率的查询。我们还学习了此问题的 C++ 程序以及解决此问题的完整方法（常规）。我们可以用其他语言（如 C、Java、Python 和其他语言）编写相同的程序。我们希望您觉得本教程有所帮助。
更新于： 2021年11月25日
236 次查看
广告