Xác suất cặp ngẫu nhiên là cặp trọng số lớn nhất trong C++

Cho hai mảng, tìm xác suất cặp ngẫu nhiên (một phần tử từ mảng 1, một từ mảng 2) là cặp có trọng số lớn nhất (cả hai phần tử đều là max của mảng tương ứng).

Đầu vào 1

arr1[] = {2, 23}, arr2[] = {10, 3, 8}

Đầu ra 1

xác suất cặp max = 0.166667

Giải thích − Các cặp: (2,10),(2,3),(2,8),(23,10),(23,3),(23,8). Cặp max: (23,8). Xác suất = 1/6

Đầu vào 2

arr1[] = {4, 5, 6}, arr2[] = {6, 2, 6}

Đầu ra 2

xác suất cặp max = 0.222222

Giải thích − Cặp max (6,6) xuất hiện 2 lần. Tổng 9 cặp. Xác suất = 2/9

Phương pháp

• Tìm max và tần suất xuất hiện của max trong mỗi mảng
• Số cặp max = count_max1 * count_max2
• Tổng cặp = size1 * size2
• Xác suất = số cặp max / tổng cặp

Thuật toán

double xacSuatCapMax(int arr1[], int arr2[], int n1, int n2) {
    int max1 = INT_MIN, cnt1 = 0;
    for (int i = 0; i < n1; i++) {
        if (arr1[i] > max1) { max1 = arr1[i]; cnt1 = 1; }
        else if (arr1[i] == max1) cnt1++;
    }
    int max2 = INT_MIN, cnt2 = 0;
    for (int i = 0; i < n2; i++) {
        if (arr2[i] > max2) { max2 = arr2[i]; cnt2 = 1; }
        else if (arr2[i] == max2) cnt2++;
    }
    return (double)(cnt1 * cnt2) / (n1 * n2);
}

Ví dụ mã nguồn

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

double xacSuatCapMax(int arr1[], int arr2[], int n1, int n2) {
    int max1 = INT_MIN, cnt1 = 0;
    for (int i = 0; i < n1; i++) {
        if (arr1[i] > max1) { max1 = arr1[i]; cnt1 = 1; }
        else if (arr1[i] == max1) cnt1++;
    }
    int max2 = INT_MIN, cnt2 = 0;
    for (int i = 0; i < n2; i++) {
        if (arr2[i] > max2) { max2 = arr2[i]; cnt2 = 1; }
        else if (arr2[i] == max2) cnt2++;
    }
    return (double)(cnt1 * cnt2) / (n1 * n2);
}

int main() {
    int arr1[] = {2, 23};
    int arr2[] = {10, 3, 8};
    int n1 = sizeof(arr1)/sizeof(arr1[0]);
    int n2 = sizeof(arr2)/sizeof(arr2[0]);
    cout << "Xác suất cặp max: " << xacSuatCapMax(arr1, arr2, n1, n2);
    return 0;
}

Kết quả

Xác suất cặp max: 0.166667