Chương trình tìm giá trị kỳ vọng của phương trình lồng căn cho số ngẫu nhiên trong Python

Cho số n. Xét x = rand() mod n, với rand() sinh số nguyên ngẫu nhiên đều trong [0, 10¹⁰⁰]. Định nghĩa:

Y = √(x + √(x + √(x + √(x + ...))))

Tìm giá trị kỳ vọng của Y. n trong khoảng [1, 5×10⁶].

Ví dụ: n = 5 → kết quả ≈ 1.696.

Thuật toán giải quyết

Giải phương trình Y = √(x + Y) → Y² = x + Y → Y = (1 + √(1+4x))/2 (nghiệm dương).

Kỳ vọng E[Y] = (1/n) * Σ_{x=0}^{n-1} (1 + √(1+4x))/2.

• Nếu n < 5×10⁶: tính trước mảng prefix sum
• Nếu n ≥ 5×10⁶: xấp xỉ bằng tích phân ∫√(4x+5)dx với hằng số sửa err

Ví dụ minh họa

def solve(n):
    err = 2235.023971557617
    max_n = 5 * 10**6
    pref = [0]
    for i in range(1, 5 * 10**6):
        pref.append(pref[-1] + (1 + (4 * i + 1)**0.5) * 0.5)
    if n < max_n:
        return pref[n - 1] / n
    else:
        total = (4 * (n - 1) + 5)**1.5 / 6 - 5**1.5 / 6 - err
        ans = 0.5 + total / (2 * n)
        return ans

n = 5
print(solve(n))

Đầu vào

5

Đầu ra

1.69647248786