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 และแก้ปัญหาแบบ Prefix Sum

ตัวอย่าง

#include <bits/stdc++.h> 
using namespace std; 

void solve(int arr[], int n, int Q, int query[][3]){ 
    int even[n + 1]; 
    int odd[n + 1]; 
    even[0] = 0; odd[0] = 0; 
    for (int i = 0; i < n; i++) { 
        if (arr[i] & 1) { 
            odd[i + 1] = odd[i] + 1; 
            even[i + 1] = even[i]; 
        } else { 
            even[i + 1] = even[i] + 1; 
            odd[i + 1] = odd[i]; 
        } 
    } 
    for (int i = 0; i < Q; i++) { 
        int r = query[i][2]; 
        int l = query[i][1]; 
        int k = query[i][0]; 
        int q = r - l + 1; 
        int p; 
        if (k) 
            p = odd[r] - odd[l - 1]; 
        else 
            p = even[r] - even[l - 1]; 
        if (!p) 
            cout << "0\n"; 
        else if (p == q) 
            cout << "1\n"; 
        else { 
            int g = __gcd(p, q); 
            cout << p / g << " " << q / g << "\n"; 
        } 
    } 
} 

int main(){ 
    int arr[] = { 6, 5, 2, 1, 7 }; 
    int n = sizeof(arr) / sizeof(int); 
    int Q = 2; 
    int query[Q][3] = {{ 0, 2, 2 },{ 1, 2, 5 }}; 
    solve(arr, n, Q, query); 
    return 0; 
}

ผลลัพธ์

0
3 4

คำอธิบายโค้ด

ในวิธีนี้ เรานับจำนวนเลขคู่และเลขคี่ที่พบจนถึงดัชนี i โดยใช้สองอาร์เรย์ ตอนนี้เราต้องหาจำนวนเลขคู่หรือคี่ในช่วงที่กำหนด และพิมพ์จำนวนนั้นและจำนวนสมาชิกทั้งหมดในช่วง

สรุป

ในบทช่วยสอนนี้ เราแก้ปัญหา Queries on probability of even or odd numbers in given ranges เรายังได้เรียนรู้โปรแกรม C++ และวิธีแก้ปัญหา ซึ่งสามารถเขียนในภาษาอื่น เช่น C, Java, Python ได้ หวังว่าจะเป็นประโยชน์