Số chấm tối đa kỳ vọng khi tung xúc xắc M mặt N lần C++

Xúc xắc có M mặt, mặt i có i chấm (1 ≤ i ≤ M). Tung N lần. Tìm giá trị kỳ vọng của số chấm lớn nhất xuất hiện trong N lần tung.

Ví dụ

M = 2, N = 3 → Output: 1.875
Faces: {1, 2}. Không gian mẫu 2³=8.
Max trong mỗi kết quả: 1,2,2,2,2,2,2,2.
Kỳ vọng = (1 + 2*7) / 8 = 15/8 = 1.875

M = 2, N = 2 → Output: 1.75

Công thức toán học

Xác suất max = i là: P(max = i) = (i/M)^N - ((i-1)/M)^N.

Kỳ vọng: E = Σ[i=1..M] i * [(i/M)^N - ((i-1)/M)^N].

Chương trình C++

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

double maxExpectation(double M, double N) {
    double ans = 0.0;
    for (int i = 1; i <= M; i++) {
        double p = pow(i / M, N) - pow((i - 1.0) / M, N);
        ans += i * p;
    }
    return ans;
}

int main() {
    double M = 2, N = 3;
    cout << fixed << setprecision(3) << maxExpectation(M, N); // 1.875
    return 0;
}

Kết quả

1.875

Độ phức tạp

O(M) với M ≤ 10⁵ rất nhanh. Dùng double cho chính xác.