这个问题实际上是四元递推式,我只能写出递推式,却不会求通式。
设这个问题的解是f(m,n,a,b)
分类讨论摸到的第一个球,第一个球可能是白球也可能是黑球。
如果第一个球是白球,那么剩下的子问题是f(m-1,n,a-1,b).第一个球是白球的概率为 [公式]
如果第一个球是黑球,那么剩下的子问题是f(m,n-1,a,b-1).第一个球是黑球的概率为 [公式]
所以
[公式]
边缘条件是: [公式]
当b=0时,此问题答案很明确:
[公式]
猜测f(m,n,a,b)可能也有某种简单形式。
对于一元递推式,可以用求根+
解方程的方式求出通项。对于此题中的多元递推式有没有系统性的解决方法?
f_dict = {}
def f(m, n, a, b):
"""
m个白球,n个黑球,想要摸到a个白球,b个黑球
用递推式的方式计算准确结果,结果使用分数表示
"""
assert a >= 0 and b >= 0 and m >= 0 and n >= 0
assert a <= m and b <= n
param = (m, n, a, b)
if param in f_dict:
return f_dict[param]
if a == 0 and b == 0:
f_dict[param] = 0
return 0
if m == 0 or n == 0:
f_dict[param] = max(a, b)
return max(a, b)
x = Fraction(m, m + n)
y = Fraction(n, m + n)
ans = 1 + x * f(m - 1, n, max(a - 1, 0), b) + y * f(m, n - 1, a, max(b - 1, 0))
f_dict[param] = ans
return ans
问题来源
最近在做一个麻将小游戏,需要实现一个麻将AI。
麻将AI的关键就是评价一个手牌局面的好坏:我用手牌局面到胡牌局面之间的最短距离表示,最短距离就是“期望摸几次牌才能胡牌”。
麻将的牌堆就像一个袋子,袋子里面有34种小球,每种小球的个数若干,期望摸几次才能摸到想要的“球型”。