校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 算法 > 智力分析题
题目

有一个大富翁游戏,骰子共6个数,每次掷骰子等概率产生1-6,可以往前走对应数字个格子,问:不经过100个各自的概率。

解答

这个题目,相对有点绕,也有点动态规划的意思。

简单分析:

到达第一个格子的概率是 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)。

根据公式,这就是一道入门的动态规划题,写出代码不难。其实和经典动态规划题目爬楼梯如出一辙。难倒是不难,但是没有接触过动态规划思想的同学,估计难受了。

C 0条回复 评论

帖子还没人回复快来抢沙发