n个骰子的点数

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

分析：骰子一共6个面，每个面上都有一个点数，对应的数字是1到 6之间的一个数字。所以，n个骰子的点数和的最小值为n，最大值为6n。因此，一个直观的思路就是定义一个长度为6n-n的数组，和为S的点数出现的次数保存到数组第S-n个元素里。另外，我们还知道n个骰子的所有点数的排列数6^n。一旦我们统计出每一点数出现的次数之后，因此只要把每一点数出现的次数除以n^6，就得到了对应的概率。

该思路的关键就是统计每一点数出现的次数。要求出n个骰子的点数和，我们可以先把n个骰子分为两堆：第一堆只有一个，另一个有n-1个。单独的那一个有可能出现从1到6的点数。我们需要计算从1到6的每一种点数和剩下的n-1个骰子来计算点数和。接下来把剩下的n-1个骰子还是分成两堆，第一堆只有一个，第二堆有n-2个。我们把上一轮那个单独骰子的点数和这一轮单独骰子的点数相加，再和剩下的n-2个骰子来计算点数和。分析到这里，我们不难发现，这是一种递归的思路。递归结束的条件就是最后只剩下一个骰子了。

基于这种思路，我们可以写出如下代码：

int g_maxValue=6;

void SubProbabilityofDices(int original, int current, int value, int tempSum, int *pProbalities)
{
	if(current==1)
	{
		int sum=value+tempSum;
		pProbalities[sum-original]++;
	}
	else
	{
		for(int i=1; i<=g_maxValue; i++)
		{
			int sum=value+tempSum;
			SubProbabilityofDices(original, current-1, i, sum, pProbalities);
		}
	}
}

void SumProbabilityofDices(int number, int* pProbabilities)
{
	for(int i=1; i<=g_maxValue; i++)//第一个骰子
		SubProbabilityofDices(number, number, i, 0, pProbabilities);

}

void PrintSumProbabilityofDices_1(int number)
{
	if(number<1)
		return;

	int maxSum=number*g_maxValue;
	int* pProbabilities=new int [maxSum-number+1];
	for(int i=number; i<=maxSum; i++)
		pProbabilities[i-number]=0;

	SumProbabilityofDices(number, pProbabilities);

	int total=pow((double)g_maxValue, number);
	for(i=number; i<=maxSum; i++)
	{
		float ratio=(float)pProbabilities[i-number]/total;
		cout<<i<<":"<<ratio<<endl;
	}
	delete[] pProbabilities;
}

上述算法当number比较小的时候表现很优异。但由于该算法基于递归，它有很多计算是重复的，从而导致当number变大时性能让人不能接受。

为了避免递归时的重复计算，我们很自然联想到动态规划（DP）。用表格法，一行代表一个骰子，列表示各个S值，所以一共有6*N列。本来是要用N行的，可是这里只用了一个二维的数组，因为现在计算的值只与前一次计算的值相关，所以其中一行保存上一次计算的结果，另一行保存正在计算的结果，这样可以节省大量的空间。我们可以考虑用两个数组来存储骰子点数每一总数出现的次数。在一次循环中，第一个数组中的第n个数字表示骰子和为n出现的次数。那么在下一循环中，我们加上一个新的骰子。那么此时和为n的骰子出现的次数，应该等于上一次循环中骰子点数和为n-1、n-2、n-3、n-4、n-5与n-6的总和。所以我们把另一个数组的第n个数字设为前一个数组对应的第n-1、n-2、n-3、n-4、n-5与n-6之和。

void PrintSumProbabilityofDices_2(int number)
{
	double* pProbabilities[2];
	pProbabilities[0]=new double[number*g_maxValue+1];
	pProbabilities[1]=new double[number*g_maxValue+1];

	for(int i=0; i<number*g_maxValue+1; i++)
	{
		pProbabilities[0][i]=0;
		pProbabilities[1][i]=0;
	}

	int flag=0;
	for(i=1; i<=g_maxValue; i++)
		pProbabilities[flag][i]=1;

	for(int k=2; k<=number; k++)
	{
		for(int i=k; i<=g_maxValue*k; i++)
		{
			pProbabilities[1-flag][i]=0;
			for(int j=1; j<=i && j<=g_maxValue; j++)
				pProbabilities[1-flag][i]+=pProbabilities[flag][i-j];
		}
		flag=1-flag;
	}

	double total=pow((double)g_maxValue, number);

	for(i=number; i<=g_maxValue*number; i++)
	{
		double ratio=pProbabilities[flag][i]/total;
		cout<<i<<":"<<ratio<<endl;
	}

	delete[] pProbabilities[0];
	delete[] pProbabilities[1];
}