趣题与算法（1）

升级装备耗宝石

升级装备题，每升级一次消耗一颗宝石，从一级升至五级概率分别为 80%，40%，30%，10%，升级失败会掉级，第一级不会掉级。请问从 1 级升至 5 级平均消耗多少宝石？

数学思维：

相信很多人在看到这个题目的时候会觉得自己概率论学的不够好，不妨由浅入深，从第一级升级到第二级消耗宝石期望是多少呢？

肯定不止一颗宝石吧，所以直觉上是 1/(80%),虽然直觉不靠谱，我先假设确实如此，那第二级升到第三级呢？这个好像就有点懵了，所以我们需要思路清晰、简洁明了的公式，而不是直觉。

假设第一级升级到第二级平均需要消耗宝石 p1,那 p1 应该满足什么条件呢？或者什么等式？

我们这么想：消耗一颗宝石会有什么结果？每种结果是什么概率？

答案显然是 80%的概率升级，20%的概率还在一级，这样的话到二级还得 P1 颗宝石。

那就是 80%的概率消耗一颗宝石就升级了，20%的概率消耗(p1+1)颗宝石实现升级。而这正是实现升级的宝石期望 p1。所以有了下面等式：80%×1+20%×（p1+1）=p1 。

p1=1/0.8;

主要是用这种思维思考接来下的开始变得简单：

一级二级三级四级升级概率 80%40%30%10%升一级平均需要宝石 p1p2p3p4

如上等式一样，有如下等式：

1×40%+(1+p1+p2)×60%=p2;

1×30%+ (1+p2+p3)×70%=p3;

1×10%+ (1+p3+p4)×90%=p4;

所以接下来只需要解方程。p1+p2+p3+p4 就是最后需要的结果。

编程思维：

假设有 n 级，1~n-1 每个等级升级的概率为数组 P：{p[0],p[1],……p[n-2]} ，升级失败会掉级。那么从一级升级到 n 级需要多少颗宝石？

假设有数值 i，1<=i<n，i 级升级到 i+1 级概率为 p[i-1],消耗宝石期望为：E[i-1], E 为数组。

12……i……n-1np[0]p[1]……p[i-1]……p[n-2]

E[0]E[1]……E[i-1]……E[n-2]

有如下等式：p[i-1]+(1+E[i-1]+E[i-2])*(1-p[i-1])=E[i-1]

E[i]=(1+E[i-1])/p[i] - E[i-1]

public class Main {     public static void main(String[] args){        double e = getSumE(0.8,0.4,0.3,0.1);         System.out.println(e);        double e2 = getSumE(0.8,0.4,0.2,0.1);         System.out.println(e2);     }    static double getSumE(double ...p) {        int len = p.length;         double[]E=new double[len];         E[0]=1/p[0];         double sum=E[0];         for(int i=1;i<len;i++) {             E[i]=(1+E[i-1])/p[i]-E[i-1];             sum+=E[i];         }         return sum;     }}

这样我们就能处理任意等级的升级需要宝石的状况了