学步园

题目：把n个骰子扔在地上，所有骰子朝上一面的点数之和为S。输入n，打印出S的所有可能的值出现的概率。

用P_N,S来表示N个骰子，顶面数字之和为S出现的概率，则：

P_N,S=a_N,S/6^N

其中a_N,S为N个骰子顶面数之和为S的状态的数量，6^N为总的状态数量，因为每个骰子有6种状态，N个骰子组成的状态数就是6^N。

下面给出求a_i,j的递推公式，即求i(1=<i<=N)个骰子顶面数之和为j(i=<j<=6*i)时的状态数量：

a_i,j= a_i-1,j-1   //第i个骰子顶面为1时，其他i-1个骰子顶面数之和为j-1时的状态数量

    + a_i-1,j-2   //第i个骰子顶面为2时，其他i-1个骰子顶面数之和为j-2时的状态数量

    + a_i-1,j-3   //第i个骰子顶面为3时，其他i-1个骰子顶面数之和为j-3时的状态数量

    + a_i-1,j-4   //第i个骰子顶面为4时，其他i-1个骰子顶面数之和为j-4时的状态数量

    + a_i-1,j-5   //第i个骰子顶面为5时，其他i-1个骰子顶面数之和为j-5时的状态数量

    + a_i-1,j-6   //第i个骰子顶面为6时，其他i-1个骰子顶面数之和为j-6时的状态数量

其中递推公式中i>1。

对于任意的1=<i<=N，j<=0或j<i或j>6*i，a_i,j=0。

下面是算法c++实现代码

void PrintSumProbabilityOfDices(unsigned int n)
{
	const unsigned int MAX=12;  //max number of dices
	if(n>MAX)
	{
		printf("Overflow!\n");
		return;
	};

	unsigned int a[MAX+1][6*MAX+1];
	unsigned int i,j,k;
	memset(a,0,sizeof(a));
	for(j=1;j<=6;j++)
		a[1][j]=1;
	for(i=2;i<=n;i++)
		for(j=i;j<=6*i;j++)
		{
			a[i][j]=0;
			for(k=1;k<=6&&k<=j;k++)
				a[i][j]+=a[i-1][j-k];
		}

	unsigned int nTotal=pow(6,n);
	for(i=n;i<=6*n;i++)
		printf("Sum=%d,Probability=%.15lf\n",i,a[n][i]*1.0/nTotal);
}