โปรแกรมคำนวณความน่าจะเป็นคู่สุ่มเป็นคู่น้ำหนักสูงสุดใน C++

ภาพรวมปัญหา

โปรแกรมนี้คำนวณความน่าจะเป็นที่คู่ (Pair) ที่สุ่มมาจากสองอาร์เรย์จะเป็น Maximum Weighted Pair โดยคู่น้ำหนักสูงสุดหมายถึงคู่ที่มี:

• องค์ประกอบตัวแรก = ค่าสูงสุดของอาร์เรย์ 1
• องค์ประกอบตัวที่สอง = ค่าสูงสุดของอาร์เรย์ 2

นิยามคู่น้ำหนักสูงสุด

กำหนดอาร์เรย์ A (ขนาด m) และอาร์เรย์ B (ขนาด n)

เซตของคู่ทั้งหมด = { (A[i], B[j]) | 0 ≤ i < m, 0 ≤ j < n } มีทั้งหมด m × n คู่

คู่น้ำหนักสูงสุด = (max(A), max(B))

สูตรความน่าจะเป็น

P(Max Pair) = (จำนวน max ใน A × จำนวน max ใน B) / (m × n)

ตัวอย่างการคำนวณ

ตัวอย่างที่ 1

A = {2, 23}        max(A) = 23, count = 1
B = {10, 3, 8}     max(B) = 10, count = 1
Total pairs = 2 × 3 = 6
Max pairs = 1 × 1 = 1
P = 1/6 = 0.166667

ตัวอย่างที่ 2

A = {4, 5, 6}      max(A) = 6, count = 1
B = {6, 2, 6}      max(B) = 6, count = 2
Total pairs = 3 × 3 = 9
Max pairs = 1 × 2 = 2
P = 2/9 = 0.222222

ตัวอย่างโค้ด C++

#include <iostream>
#include <climits>
#include <iomanip>
using namespace std;

double maxPairProbability(int arr1[], int arr2[], int size1, int size2) {
    // หาค่าสูงสุดและจำนวนครั้งใน arr1
    int max1 = INT_MIN, count1 = 0;
    for (int i = 0; i < size1; i++) {
        if (arr1[i] > max1) {
            max1 = arr1[i];
            count1 = 1;
        } else if (arr1[i] == max1) {
            count1++;
        }
    }
    
    // หาค่าสูงสุดและจำนวนครั้งใน arr2
    int max2 = INT_MIN, count2 = 0;
    for (int i = 0; i < size2; i++) {
        if (arr2[i] > max2) {
            max2 = arr2[i];
            count2 = 1;
        } else if (arr2[i] == max2) {
            count2++;
        }
    }
    
    // คำนวณความน่าจะเป็น
    long long maxPairs = 1LL * count1 * count2;
    long long totalPairs = 1LL * size1 * size2;
    
    return static_cast(maxPairs) / totalPairs;
}

int main() {
    cout << fixed << setprecision(6);
    
    // Test case 1
    int arr1[] = {2, 23};
    int arr2[] = {10, 3, 8};
    int s1 = sizeof(arr1)/sizeof(arr1[0]);
    int s2 = sizeof(arr2)/sizeof(arr2[0]);
    cout << "Test 1: P = " << maxPairProbability(arr1, arr2, s1, s2) << endl;
    
    // Test case 2
    int arr3[] = {4, 5, 6};
    int arr4[] = {6, 2, 6};
    int s3 = sizeof(arr3)/sizeof(arr3[0]);
    int s4 = sizeof(arr4)/sizeof(arr4[0]);
    cout << "Test 2: P = " << maxPairProbability(arr3, arr4, s3, s4) << endl;
    
    // Test case 3: ทุกค่าเท่ากัน
    int arr5[] = {5, 5, 5};
    int arr6[] = {3, 3};
    int s5 = sizeof(arr5)/sizeof(arr5[0]);
    int s6 = sizeof(arr6)/sizeof(arr6[0]);
    cout << "Test 3 (all same): P = " << maxPairProbability(arr5, arr6, s5, s6) << endl;
    // ทุกคู่เป็น max pair → P = 1.0
    
    return 0;
}

ผลลัพธ์ตัวอย่าง

Test 1: P = 0.166667
Test 2: P = 0.222222
Test 3 (all same): P = 1.000000

ความซับซ้อนของอัลกอริทึม

• เวลา: O(m + n) - สแกนแต่ละอาร์เรย์หนึ่งครั้ง
• พื้นที่: O(1) - ใช้ตัวแปรคงที่

การขยาย: หาความน่าจะเป็นของ Top-K Pairs

หากต้องการหาความน่าจะเป็นของคู่ที่มีน้ำหนักสูงสุด k อันดับแรก สามารถ:

1. หาค่าสูงสุด k อันดับของแต่ละอาร์เรย์
2. นับความถี่ของแต่ละค่า
3. คำนวณความน่าจะเป็นสะสม

กรณีพิเศษ

ประยุกต์ใช้

• การวิเคราะห์อัลกอริทึมสุ่ม (Randomized Algorithms)
• Game Theory: กลยุทธ์การเลือกคู่ที่ดีที่สุด
• Database: การประมาณผลลัพธ์ Join ของตารางสองตาราง