Chương trình tính số bước di chuyển kỳ vọng game Lotus và Caterpillar trong Python

Lưới n hàng, m cột. Amal (sen) ở hàng trên, Bimal (sâu) ở hàng dưới. Amal di chuyển 8 hướng, Bimal chỉ trái/phải/giữ nguyên. Amal muốn bắt nhanh, Bimal muốn sống lâu. Cột khởi tạo ngẫu nhiên. Tính kỳ vọng số bước Amal thắng.

Công thức

Kỳ vọng = (1/m) * Σ_{l=0}^{m-1} [ n-1 + max(0, l-n+1)*(l-1)/m + max(0, m-n-l)*(m-l-2)/m ]

Ví dụ

def solve(n, m):
    r = 0
    for l in range(m):
        temp = n - 1.0
        if l >= n:
            temp += (l - n + 1) * ((l - 1) / m)
        if l < m - n:
            temp += (m - n - l) * ((m - l - 2) / m)
        r += temp / m
    return r

print(solve(5, 7))  # Output: 4.571428571428571

Giải thích

n=5, m=7 → kỳ vọng ≈ 4.57 bước.