找回密码
 欢迎注册
查看: 26795|回复: 2

[原创] 三消游戏自动消除n个障碍的概率

[复制链接]
发表于 2014-11-20 01:18:35 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
有一个宽度为$1$,高度为$+\infty$的容器。

一开始容器的顶部有$3$个空位,其余全是障碍物(云层),如下图所示:

1.png

如果容器顶部有空位,那么这些空位会被小动物填补。

小动物只有$2$种。

每个空位被填补的小动物是随机且独立的,

被青蛙填补的概率是$p$,

被狐狸填补的概率是$(1-p)$。

下图是其中一种可能的填补:

2.png

当所有空位都被填满后,如果有连续$3$个或$3$个以上相同的小动物排在一起,这些小动物会被消除。

如果紧贴云层的小动物被消除,那么这块云层也会被一起消除,如下图所示:

3.png

小动物和云层被消除后都会变成空位,空位上方的小动物(如果有的话)会依次落下来。

当所有小动物都落稳后,容器顶部的空位会被新的小动物(按照$p$和$(1-p)$的概率随机、独立地)填补。

下图是其中一种可能的填补:

4.png

填补后如果还有连续$3$个或$3$个以上相同的小动物排在一起,这些小动物会被消除。

5.png

上述过程不断反复,直到没有连续$3$个或$3$个以上相同的小动物排在一起为止,如下图所示:

6.png

我们把上述过程消除掉的云层总数记为$n$。

问题$1$:

当$p=0.5$时,给定非负整数$k$,求$n=k$的概率$P(n=k)$是多少。(如果没有通式,求出$P(n=0)$、$P(n=1)$、……、$P(n=20)$即可)

问题$2$:

当$p=0.5$,$k->\infty$时,$\frac{P(n=k+1)}{P(n=k)}$是否有极限?如果有,该极限是多少?

问题$3$:

当$p$取何值时,我们有$\sum_{k=0}^\infty P(n=k)<1$?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-11-22 10:51:27 来自手机 | 显示全部楼层
这个问题状态很复杂,感觉很难求解,不知道是否可以有近似解法。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-11-22 20:02:48 | 显示全部楼层
动态规划可以求解,想法是在一开始就确定某个动物是怎么被消除的。(状态维数很大,可能要4维或者5维)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-11-24 10:27 , Processed in 0.033216 second(s), 24 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表