如题所说:
像大富翁一样,掷骰子,按骰子的点数,走步数,计算走到第n格的概率是多少?
例如我们的这个函数dp(n)计算的是第n格的概率,则:
//骰子点数必须为(1),这1种可能
p(1)=第1格的概率=1/6
//骰子点数必须为(2),(1,1),两种可能
p(2)=第2格的概率=1/6+(1/6)(1/6)
//骰子点数(3),(1,2),(2,1),(1,1,1)
p(3)=第3格的概率=1/6+(1/6)(1/6)2+(1/6)(1/6)*(1/6)
第4个的排列组合实在是太多了,这里我就不继续列举了
我们来分析一下,这个p(n)改如何计算,第n格的概率其实是第n-6格到第n-1格,整体计算出来的
如果n<6则:
p(1)=1/6
p(2)=p(1)/6+1/6
p(3)=p(1)/6+p(2)/6+1/6
...
如果n>6则:
p(n)=p(n-1)/6+p(n-2)/6+p(n-3)/6+p(n-4)/6+p(n-5)/6+p(n-6)/6
则我们只需要从1开始算概率,
计算1的概率时,必须将第一格对2-7格的概率的影响也计算出来
p(n+1)+=p(n)/6
具体算法如下:
public static double p(int n){
if(n<=0||n>64){
return 0;
}
double arr[] = new double[64];
for(int i = 0;i<64;i++){
if(i<6){
arr[i]+=1.0/6;
}
for(int j=1;j<7;j++){
if(i+j<64)
arr[i+j]+=arr[i]/6.0;
}
}
return arr[n-1];
}