这个题目,相对有点绕,也有点动态规划的意思。
简单分析:
到达第一个格子的概率是 1/6
到达第二个格子的概率是 1/6 + 到达第一个格子并且掷出1的概率
到达第三个格子的概率 1/6 + 到达第1个格子且掷出2的概率 + 到达第2个格子且掷出1的概率
以此类推: 到达第七个格子的概率,便是用户到达第一个格子并掷出6的概率 + 到达第二个格子并掷出5的概率 + 到达第三个格子掷出4的概率 + 到达第四个格子掷出3的概率 + 到达第五个各自掷出2的概率 + 到达第六个格子掷出1的概率
到达第n个格子的概率,就是达到n-1的概率并掷出1的概率 + 达到n-2的概率并掷出2的概率 + 达到n-3的概率并掷出3的概率 + 达到n-4的概率并掷出4的概率 + 达到n-5的概率并掷出5的概率 + 达到n-6的概率并掷出6的概率
以n表示格子数,可以得到如下公式:
如果n > 6:
f(n) = 1/6 * f(n-1) + 1/6 * f(n-2) + 1/6 * f(n-3) + 1/6 * f(n-4) + 1/6 * f(n-5) + 1/6 * f(n-6);
而如果n <= 6 ,那么需要特殊处理,因为 n-x 可能会小于0,如果n-x小于0,那么概率便加0。同时由于可以直接到达,那么必定有1/6的概率保底。公示如下:
f(n) = 1/6 + 1/6 * (n - 1 > 0 ? f(n-1) : 0) + 1/6 * (n - 2 > 0 ? f(n-2) : 0) + 1/6 * (n - 3 > 0 ? f(n-3) : 0) + 1/6 * (n - 4 > 0 ? f(n-4) : 0) + 1/6 * (n - 5 > 0 ? f(n-5) : 0)。
根据公式,这就是一道入门的动态规划题,写出代码不难。其实和经典动态规划题目爬楼梯如出一辙。难倒是不难,但是没有接触过动态规划思想的同学,估计难受了。
帖子还没人回复快来抢沙发