資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告