題目:把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]; }