剑指Offer - 九度1360 - 乐透之猜数游戏
2014-02-05 19:54
- 题目描述：
-
六一儿童节到了,YZ买了很多丰厚的礼品,准备奖励给JOBDU里辛劳的员工。为了增添一点趣味性,他还准备了一些不同类型的骰子,打算以掷骰子猜数字的方式发放奖品。例如,有的骰子有6个点数(点数分别为1~6),有的骰子有7个(点数分别为1~7),还有一些是8个点数(点数分别为1~8) 。他每次从中拿出n个同一类型的骰子(假设它们都是拥有m个点数并且出现概率相同)投掷,然后让员工在纸上按优先级(从高到低)的顺序写下3个数上交,表示他们认为这些骰子最有可能的点数之和是多少。第一个数就猜对的人,是一等奖;第二个数才猜对的人是二等奖;如果三个数都不是正确答案,别灰心！YZ还准备了很多棒棒糖。ZL很聪明,他想了想,打算把概率(以保留两位小数的概率计)最高的三个数找出来,如果有概率相同,则选择其中点数和最小的那个数。你觉得ZL会依次写下哪三个数？
- 输入：
-
输入有多组数据。
每组数据一行,包含2个整数n(0<=n<=10),m(6<=m<=8),n表示YZ拿出的骰子数,m表示骰子拥有的点数。如果n=0,则结束输入。
- 输出：
-
对应每组数据,输出ZL最可能依次写下的点数,以及其对应的概率值。概率值按4舍5入要求保留2位小数。每组数据之间空一行,注意:最后一组数据末尾无空行。
- 样例输入：
-
1 6 4 6 3 7 0
- 样例输出：
-
1 0.17 2 0.17 3 0.17 13 0.11 14 0.11 15 0.11 12 0.11 10 0.10 11 0.10
题意分析：
扔骰(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都比较小，所以我没有进一步优化。
最后需要注意的，是对算出来的概率四舍五日到小数点后两位，然后再比较概率。
1 // 689492 zhuli19901106 1360 Accepted 点击此处查看所有case的执行结果 1024KB 1230B 10MS 2 // 201402030320 3 #include <algorithm> 4 #include <cstdio> 5 #include <cstring> 6 #include <vector> 7 using namespace std; 8 9 typedef struct st{ 10 public: 11 int x; 12 int y; 13 st(int _x = 0, int _y = 0): x(_x), y(_y) {}; 14 }st; 15 16 bool comparator(const st &a, const st &b) 17 { 18 if (a.y == b.y) { 19 return a.x < b.x; 20 } else { 21 return a.y > b.y; 22 } 23 } 24 25 int main() 26 { 27 int n, m; 28 int i, j, k; 29 int sum; 30 int a[11][81]; 31 vector<st> v; 32 int cc; 33 34 cc = 0; 35 while (scanf("%d", &n) == 1 && n) { 36 scanf("%d", &m); 37 if (cc > 0) { 38 printf("\n"); 39 } 40 ++cc; 41 memset(a, 0, 11 * 81 * sizeof(int)); 42 for (i = 1; i <= m; ++i) { 43 a[1][i] = 1; 44 } 45 sum = m; 46 for (i = 2; i <= n; ++i) { 47 for (j = 1; j <= m; ++j) { 48 for (k = i - 1; k <= (i - 1) * m; ++k) { 49 a[i][k + j] += a[i - 1][k]; 50 } 51 } 52 sum *= m; 53 } 54 55 for (i = n; i <= n * m; ++i) { 56 v.push_back(st(i, (int)(100.0 * a[n][i] / sum + 0.5))); 57 } 58 59 sort(v.begin(), v.end(), comparator); 60 61 for (i = 0; i < 3; ++i) { 62 printf("%d %.2f\n", v[i].x, v[i].y / 100.0); 63 } 64 v.clear(); 65 } 66 67 return 0; 68 }