Xác suất các mảnh que gãy tạo thành đa giác n cạnh trong C++

Cho que dài bất kỳ, gãy ngẫu nhiên thành n mảnh (số nguyên hoặc thực). Nhiệm vụ: tìm xác suất các mảnh tạo thành đa giác n cạnh.

Điều kiện tạo đa giác

n đoạn thẳng tạo thành đa giác n cạnh ⟺ mỗi đoạn < tổng các đoạn còn lại ⟺ đoạn dài nhất < nửa tổng độ dài.

Công thức xác suất

$$P = 1 - \frac{n}{2^{n-1}}$$

Công thức này đúng khi điểm gãy được chọn ngẫu nhiên đều đặn độc lập trên que.

Ví dụ 1

Input – length = 10, pieces = 4

Output – Probability = 0.5

Giải thích: P = 1 - 4/2³ = 1 - 4/8 = 0.5.

Ví dụ 2

Input – length = 5, pieces = 3

Output – Probability = 0.25

Giải thích: P = 1 - 3/2² = 1 - 3/4 = 0.25. (Tam giác: 3 đoạn tạo thành tam giác iff không đoạn nào ≥ 1/2 tổng).

Ví dụ code

#include <iostream>
#include <cmath>
using namespace std;

double polygonProbability(unsigned pieces) {
    if (pieces < 3) return 0; // Cần ít nhất 3 cạnh
    unsigned denom = 1u << (pieces - 1); // 2^(n-1)
    return 1.0 - (double)pieces / denom;
}

int main() {
    unsigned pieces = 4;
    cout << "Probability: " << polygonProbability(pieces) << endl;
    return 0;
}

Kết quả

Probability: 0.5

Lưu ý: Code gốc có lỗi toán tử `1 < (pieces-1)` thay vì `1 << (pieces-1)`. Đã sửa. Độ dài que không ảnh hưởng xác suất (chỉ tỷ lệ quan trọng).

Chứng minh ý tưởng: Xác suất có ít nhất một đoạn ≥ 1/2 là n/2ⁿ⁻¹ (sự kiện rời rạc, mỗi đoạn có xác suất 1/2ⁿ⁻¹ là đoạn dài nhất ≥ 1/2).