剑指Offer - 九度1360 - 乐透之猜数游戏 - zhuli19901106 - 博客园
Read full article from 剑指Offer - 九度1360 - 乐透之猜数游戏 - zhuli19901106 - 博客园
- 六一儿童节到了,YZ买了很多丰厚的礼品,准备奖励给JOBDU里辛劳的员工。为了增添一点趣味性,他还准备了一些不同类型的骰子,打算以掷骰子猜数字的方式发放奖品。例如,有的骰子有6个点数(点数分别为1~6),有的骰子有7个(点数分别为1~7),还有一些是8个点数(点数分别为1~8) 。他每次从中拿出n个同一类型的骰子(假设它们都是拥有m个点数并且出现概率相同)投掷,然后让员工在纸上按优先级(从高到低)的顺序写下3个数上交,表示他们认为这些骰子最有可能的点数之和是多少。第一个数就猜对的人,是一等奖;第二个数才猜对的人是二等奖;如果三个数都不是正确答案,别灰心!YZ还准备了很多棒棒糖。ZL很聪明,他想了想,打算把概率(以保留两位小数的概率计)最高的三个数找出来,如果有概率相同,则选择其中点数和最小的那个数。你觉得ZL会依次写下哪三个数?
扔骰(tou,不是shai)子求点数应该也是很常见的概率问题了。对于一个点数范围1~m的骰子,扔了n次,求出点数之和概率最大的三个值,以及对应的概率。 首先,扔一次获得各个点数的概率是相等的,因此各点数之和的概率分布一定是对称的,所以概率最大的一定就是正中间的三个点数和。因此,均值n*(1+m)/2就是概率最大的。考虑到奇偶和取整问题,在n奇m偶的情况下,概率最大的点数有两个。 如果你做过另一个题:求x+y+z=n的非负整数解,应该会想在这题上试试用组合数学来搞出个巧妙解法。但由于这道题中限制每个数都在1~m的范围内,需要分情况处理。所以我还是决定用n^2*m规模的动态规划来解决。 k个骰子能扔出的点数之和最小是k,最大是m*k,因此只要知道了k-1个骰子的所有扔法,就能推导出k个骰子的所有扔法的概率分布。 递推公式为: 1. 用a[n][k]表示n个骰子扔出的点数和为k的扔法个数。 2. a[1][j]=1, j=[1,m] 3. a[i][j]=sigma(a[i-1][k]), j=[i,i*m], k∈[i-1,(i-1)*m]∩[j-m,j-1] 由于递推需要进行n轮,每轮的点数之和从i到i*m。所以时间复杂度是O(n*(n*m)),也就是O(n^2*m),空间复杂度可以优化为O(n*m),不过本题中n和m都比较小,所以我没有进一步优化。
Read full article from 剑指Offer - 九度1360 - 乐透之猜数游戏 - zhuli19901106 - 博客园