Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Xác suất - Thống kê] Kiểm định số lần chạy (Runs Test)

    Kiểm định số lần chạy (Runs Test / Wald–Wolfowitz runs test) dùng để kiểm tra tính ngẫu nhiên của một dãy nhị phân.

    Cho một dãy gồm NNN ký hiệu, mỗi ký hiệu là 0 hoặc 1. Gọi n1n_1n1​ là số lượng ký hiệu 0, n2n_2n2​ là số lượng ký hiệu 1 (đảm bảo n1≥1n_1 \ge 1n1​≥1 và n2≥1n_2 \ge 1n2​≥1). Một run là một dãy con liên tiếp tối đa gồm các ký hiệu giống nhau. Gọi RRR là tổng số run trong dãy.

    Dưới giả thuyết dãy ngẫu nhiên, kỳ vọng và phương sai của RRR là: μR=2n1n2n1+n2+1,σR2=2n1n2(2n1n2−n1−n2)(n1+n2)2(n1+n2−1)\mu_R = \frac{2 n_1 n_2}{n_1+n_2} + 1, \qquad \sigma_R^2 = \frac{2 n_1 n_2 (2 n_1 n_2 - n_1 - n_2)}{(n_1+n_2)^2 (n_1+n_2-1)}μR​=n1​+n2​2n1​n2​​+1,σR2​=(n1​+n2​)2(n1​+n2​−1)2n1​n2​(2n1​n2​−n1​−n2​)​

    Thống kê chuẩn hóa: z=R−μRσRz = \dfrac{R - \mu_R}{\sigma_R}z=σR​R−μR​​. Quy ước: nếu σR=0\sigma_R = 0σR​=0 (trường hợp suy biến khi n1=n2=1n_1=n_2=1n1​=n2​=1) thì z=0z=0z=0.

    Yêu cầu: Đọc dãy, tính RRR, μR\mu_RμR​, σR\sigma_RσR​ và zzz.

    Ví dụ: Dãy "1 0 0 1 1 1 0": các run là (1)(00)(111)(0)(1)(00)(111)(0)(1)(00)(111)(0), suy ra R=4R=4R=4; n1=3n_1=3n1​=3 (số lượng số 0), n2=4n_2=4n2​=4 (số lượng số 1). μR=2⋅3⋅47+1≈4.4286\mu_R = \frac{2\cdot3\cdot4}{7}+1 \approx 4.4286μR​=72⋅3⋅4​+1≈4.4286. σR2=2⋅3⋅4⋅(24−7)49⋅6≈1.3878\sigma_R^2 = \frac{2\cdot3\cdot4\cdot(24-7)}{49\cdot6} \approx 1.3878σR2​=49⋅62⋅3⋅4⋅(24−7)​≈1.3878, σR≈1.1780\sigma_R \approx 1.1780σR​≈1.1780. z≈4−4.42861.1780≈−0.3638z \approx \frac{4-4.4286}{1.1780} \approx -0.3638z≈1.17804−4.4286​≈−0.3638.

    • Định dạng đầu vào:

      Dòng đầu chứa số nguyên NNN (2≤N≤100002 \le N \le 100002≤N≤10000) — độ dài dãy.

      Dòng thứ hai chứa NNN số nguyên, mỗi số là 0 hoặc 1, cách nhau bởi khoảng trắng. Đảm bảo dãy có ít nhất một số 0 và ít nhất một số 1.

    • Định dạng đầu ra:

      In trên một dòng 4 giá trị cách nhau bởi khoảng trắng: RRR (số nguyên), μR\mu_RμR​, σR\sigma_RσR​, zzz (ba số thực, mỗi số làm tròn đến 4 chữ số thập phân). Ví dụ: 4 4.4286 1.1780 -0.3638.

    Ví dụ:

    Đầu vào:

    7
1 0 0 1 1 1 0

    Đầu ra:

    4 4.4286 1.1780 -0.3638

    Đầu vào:

    2
0 1

    Đầu ra:

    2 2.0000 0.0000 0.0000

    Đang tải editor...