写点什么

趣题与算法(1)

发布于: 1 小时前
趣题与算法(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;     }}
复制代码

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


用户头像

还未添加个人签名 2020.03.22 加入

还未添加个人简介

评论

发布
暂无评论
趣题与算法(1)