游戏面试题-武器升级 - tenos - 博客园

游戏面试题-武器升级 - tenos - 博客园
一把武器，最低是1级，最高可以升到9级，每次升级成功率30%，失败率70%。失败会退一级，在1级的时候如果失败则仍然为1级。问：该武器从1级升到9级的所需次数的期望？

记从第k-1级升到第k级所需次数的期望是E_k。

假设武器处于k级，那么从k级升到k+1所需次数的期望E_(k+1) 如何求呢？ 分为两种情况：
（1）、从k到k+1第一次成功，概率是0.3，所需次数是1      
（2）、第一次不成功，退回到了k-1级，概率是0.7，这时需要先从k-1上升到k（需要的次数期望是E_k），再从k上升到k+1(需要的次数期望是E_(k+1))，总的所需次数是 E_k + E_(k+1) + 1。

根据期望的计算公式可以得到： E_(k+1) = 0.3*1 + 0.7*(E_k + E_(k+1) + 1)
上式化简为：0.3E_(k+1) = 0.7E_k + 1
作简单变换可得：0.3(E_(k+1) + 2.5) = 0.7(E_k + 2.5)
很明显E_k+2.5 是等比数列，可以很容易求得E_k的通项公式。
那么最终从1级上升到9级所需次数期望 = E_2 + E_3 + E_4 + … + E_9， 可以根据等比数列求和公式求得。
http://www.jiancool.com/article/57262548818/

设f(x,y)表示从x升级到y的宝石数期望，则：

f(0,3)  =  1 + f(1,3)

f(1,3)  =  A1*(1+f(2,3)) + B1*(1+f(1,3)) + C1*(1+f(0,3))

f(2,3) =  A2*1 + B2*(1+f(2,3)) + C2*(1+f(1,3))

很明显，这是一个三元一次方程组，必定可以计算出f(0,3)，f(1,3)，f(2,3)

其中f(0,3)为最终的答案

其实，这个思想并不难，关键是有没有想到，下面做简单分析

• f(0,3)用一块宝石升级到1级后，继续的期望是f(1,3) =>  f(0,3) = 1 +f(1,3)
• f(x,y)用一块宝石升级一次后，有Ax的概率升一级，之后期望为f(x+1,y)，这部分为Ax*(1+f(x+1,y))，之后部分类似分析，即可得到 f(x,y) = Ax*(1+f(x+1,y)) + Bx*(1+f(x,y)) + Cx*(1+f(x-1,y))，关于x与y的大小，还有一些边界就自己去考虑吧
• f(x,x)为0

最终答案：

如果我们令[A0,B0,C0] = [1,0,0] ，[A1,B1,C1] = [1/3,1/3,1/3]，[A2,B2,C2] = [1/9,4/9,4/9] ，那么f(0,3) = 30  f(1,3) = 29   f(2,3) = 25

注意，根据我们上面简单分析中的第二条f(x,y)的计算，其实可以解决升级到任意等级的需要的宝石数，包括将最高等级扩展到N，只要有对应的[Ai,Bi,Ci]，因为实际上最后问题都是一个方程组，可以编程来解决，参考矩阵的相关知识，见数值计算。

Read full article from 游戏面试题-武器升级 - tenos - 博客园