- 题目描述：
-
六一儿童节到了,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
思路：
意思是掷多次骰子得到的和为A，找出其分布中出现概率最高的三个数。
果断递归或者说动态规划来解决，第N+1次之后的结果从第N次的结果推出。
代码：
#include <stdio.h>
#include <stdlib.h>
#define N 10
#define M 8
struct node {
int index;
double p;
} c[N*M+1];
int cmp(const void *a, const void *b)
{
struct node *c = (struct node *)a;
struct node *d = (struct node *)b;
if (c->p != d->p)
return (d->p > c->p) ? 1 : -1;
else
return c->index - d->index;
}
int main(void)
{
int n, m, i, j, k;
double a[N*M+1];
double b[N*M+1];
int count;
count = 0;
while (scanf("%d", &n) != EOF && n)
{
scanf("%d", &m);
b[0] = 1;
for(i=1; i<=n; i++)
{
for (j=i; j<=i*m; j++)
{
a[j] = 0;
for (k=j-1; k>=j-m; k--)
{
if (k>=i-1 && k<=(i-1)*m)
a[j] += b[k]/m;
}
//if (i == n)
// printf("%d: %.4lf
", j, a[j]);
}
for (j=i; j<=i*m; j++)
b[j] = a[j];
}
for (i=n; i<=n*m; i++)
{
c[i-n].index = i;
double t0 = a[i]*100;
double t1 = (double)((int)t0);
double t2 = (double)((int)t0+1);
double t;
if (t0-t1 < t2-t0)
t = t1;
else
t = t2;
c[i-n].p = t/100;
}
qsort(c, (m-1)*n+1, sizeof(c[0]), cmp);
if (count > 0)
printf("
");
for (i=0; i<3; i++)
printf("%d %.2lf
", c[i].index, c[i].p);
count ++;
}
return 0;
}
/**************************************************************
Problem: 1360
User: liangrx06
Language: C
Result: Accepted
Time:10 ms
Memory:916 kb
****************************************************************/