n個骰子的點數(shù)

題目：把n個骰子扔在地上，所有骰子朝上一面的點數(shù)之和為S。輸入n，打印出S的所有可能的值出現(xiàn)的概率。

分析：骰子一共6個面，每個面上都有一個點數(shù)，對應(yīng)的數(shù)字是1到 6之間的一個數(shù)字。所以，n個骰子的點數(shù)和的最小值為n，最大值為6n。因此，一個直觀的思路就是定義一個長度為6n-n的數(shù)組，和為S的點數(shù)出現(xiàn)的次數(shù)保存到數(shù)組第S-n個元素里。另外，我們還知道n個骰子的所有點數(shù)的排列數(shù)6^n。一旦我們統(tǒng)計出每一點數(shù)出現(xiàn)的次數(shù)之后，因此只要把每一點數(shù)出現(xiàn)的次數(shù)除以n^6，就得到了對應(yīng)的概率。

該思路的關(guān)鍵就是統(tǒng)計每一點數(shù)出現(xiàn)的次數(shù)。要求出n個骰子的點數(shù)和，我們可以先把n個骰子分為兩堆：第一堆只有一個，另一個有n-1個。單獨(dú)的那一個有可能出現(xiàn)從1到6的點數(shù)。我們需要計算從1到6的每一種點數(shù)和剩下的n-1個骰子來計算點數(shù)和。接下來把剩下的n-1個骰子還是分成兩堆，第一堆只有一個，第二堆有n-2個。我們把上一輪那個單獨(dú)骰子的點數(shù)和這一輪單獨(dú)骰子的點數(shù)相加，再和剩下的n-2個骰子來計算點數(shù)和。分析到這里，我們不難發(fā)現(xiàn)，這是一種遞歸的思路。遞歸結(jié)束的條件就是最后只剩下一個骰子了。

基于這種思路，我們可以寫出如下代碼：

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;
}

上述算法當(dāng)number比較小的時候表現(xiàn)很優(yōu)異。但由于該算法基于遞歸，它有很多計算是重復(fù)的，從而導(dǎo)致當(dāng)number變大時性能讓人不能接受。

為了避免遞歸時的重復(fù)計算，我們很自然聯(lián)想到動態(tài)規(guī)劃（DP）。用表格法，一行代表一個骰子，列表示各個S值，所以一共有6*N列。本來是要用N行的，可是這里只用了一個二維的數(shù)組，因為現(xiàn)在計算的值只與前一次計算的值相關(guān)，所以其中一行保存上一次計算的結(jié)果，另一行保存正在計算的結(jié)果，這樣可以節(jié)省大量的空間。我們可以考慮用兩個數(shù)組來存儲骰子點數(shù)每一總數(shù)出現(xiàn)的次數(shù)。在一次循環(huán)中，第一個數(shù)組中的第n個數(shù)字表示骰子和為n出現(xiàn)的次數(shù)。那么在下一循環(huán)中，我們加上一個新的骰子。那么此時和為n的骰子出現(xiàn)的次數(shù)，應(yīng)該等于上一次循環(huán)中骰子點數(shù)和為n-1、n-2、n-3、n-4、n-5與n-6的總和。所以我們把另一個數(shù)組的第n個數(shù)字設(shè)為前一個數(shù)組對應(yīng)的第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];
}