抽包的數學

# dl.py
def dld(n, x, y):
    if x * y == 0:
        return [(x + y) * (n + 1) / 2., 0., 0.]
    else:
        s = 0
        fx = dld(n, x - 1, y)[0]
        fy = dld(n, x, y - 1)[0]
        fxy = dld(n, x - 1, y - 1)[0]
        stopx = 2 * fxy - 2 * fx + n + 1
        stopy = 2 * fxy - 2 * fy + n + 1
        for m in range(1, n):
            ex = fx if m <= stopx else fxy + (n + 1 - m) / 2.
            ey = fy if m <= stopy else fxy + (n + 1 - m) / 2.
            s += (ex + ey + 2 * m) * (n - m) / (n * n - n)
        return [s, stopx, stopy]
def dlc(x, y):
    if x * y == 0:
        return [(x + y) / 2., 0., 0.]
    else:
        fx = dlc(x - 1, y)[0]
        fy = dlc(x, y - 1)[0]
        fxy = dlc(x - 1, y - 1)[0]
        return [-2 * (fx ** 3 + fy ** 3) / 3. + 2 * (fx ** 2 + fy ** 2) * fxy - 2 * (fx + fy) * fxy ** 2 + (fx + fy) / 2. + 4 * fxy ** 3 / 3. + 1 / 3., 2 * fxy - 2 * fx + 1., 2 * fxy - 2 * fy + 1.] # last two are stopx and stopy

程序裏首先用到了“卡包裏有一種需要卡需要抽幾包”的期望，在剩餘n包時，平均抽(n+1)/2包能抽出來。第一個dld程序是離散的情況，看當前重置與否哪個期望cost最低，再遞歸累計求和。第二個dlc程序是連續的情況，最後的式子是我積分化簡後的結果。原本以爲化簡後觀察前幾個結果能猜出通項公式，再用歸納法證明。但是繁瑣程度超出我的想像。