屠龙刀的概率升级问题

wayne

一把1级屠龙刀，最高可以升到9级，每次升级成功率30%，失败率70%。失败会退一级，最差退到1级。那么在1000次内升级到9级的概率为多少？

======================

在15分钟内得出正确结果的，可以来梦工厂应聘高级数值策划；在半小时内编出程序实现算法的，可以来梦工厂应聘初级程序员

仙剑魔

f(1)=0.7*f(2)+0.7*f(1)
f(9)=0.3*f(8)
f(n)=0.3*f(n-1)+0.7*f(n+1)
f(1)+f(2)+...+f(9)=1
记得是这么解来着...

KeyTo9_Fans

楼上的太牛了。

看来我只配当后者了。

貌似“高级数值策划”出现断词错误。

正确的断词方案应该是{高级,数值,策划}

而论坛把它断成{高,级数,值,策划}了。

056254628

2楼计算有问题。
从他的计算过程可以看出与升级的次数无关。
但是如果升级次数等于0,f（1）=1,其余等于0.
如果升级次数很大，f（9）趋于0

056254628

应该是这样
f（n，1）=0.7*f（n-1,2）+0.7*f（n-1,1）
f（n，9）=0.3*f（n-1,8）+0.3*f（n-1,9）
f（n，k）=0.3*f（n-1,k-1）+0.7*f（n-1,k+1）
f（0,1）=1
f（0,k）=0
求f（1000,9）？

仙剑魔

其实我那结果貌似无限次的成功率
因为以前遇到的都是类似1000级无限次概率的问题
最后都是转化到一个N元1次方程组，消元求解

因为是1000次以内到9级
所以LS那个可能得  ∑f（n,9）

056254628

如果升级到9级就算成功，不再继续去升级，那么应该
f（n，1）=0.7*f（n-1,2）+0.7*f（n-1,1）
f（n，9）=0.3*f（n-1,8）
f（n，8）=0.3*f（n-1，7）
f（n，k）=0.3*f（n-1,k-1）+0.7*f（n-1,k+1）   
f（0,1）=1
f（0,k）=0
求f（1,9）+......+f（1000,9）？

056254628

上述可简成如下：
f（n，1）=0.7*f（n-1,2）+0.7*f（n-1,1）
f（n，8）=0.3*f（n-1，7）
f（n，k）=0.3*f（n-1,k-1）+0.7*f（n-1,k+1）      k=2、3、...、7
f（0,1）=1
f（0,k）=0        k=2、3、...、8
求1-f（1000,1）-f（1000,2）-......-f（1000,8）

056254628

如果升级到9级就算成功，不再去尝试升级。那么就需要把所有的f(n,9)相加。（如8楼所示。）
n趋向于无穷时，结果就趋向于1。
n=1000时，约等于0.2285568274
------------------------------------------------------
如果9级的也要去进行升级，那么n趋向于无穷时，会存在极限值。（如6楼所示。）
极限值约等于0.000650668157157......
n=250精度就足够了

wayne

我现在还不知道怎么做呢
最开始我也是列出一堆递推公式，
感觉还有更好的方法