题目：
把n个骰子仍在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
思路：
s可能出现的值的范围为：n--6*n
1、全排列
回溯法枚举n个骰子（6面）的全排列，然后计算每一次排列所有值的和，并统计该和的出现的次数，除以6^n（全排列的全部可能性），即为概率。(这里就不列出代码)
2、递归思想
通过递归的思想将n个骰子的点数累加。
要求出n个骰子的点数和，可以先求出前n-1个骰子的点数和，然后加上第n个骰子的点数；
递归结束条件：n=1，此时某个点数和出现的次数+1；
3、动态规划思想
假设f(m,n)表示投第m个骰子时，点数之和n出现的次数,投第m个骰子时的点数之和只与投第m-1个骰子时有关。
递归方程：f(m,n)=f(m-1,n-1)+f(m-1,n-2)+f(m-1,n-3)+f(m-1,n-4)+f(m-1,n-5)+f(m-1,n-6)，表示本轮点数和为n出现次数等于上一轮点数和为n-1，n-2，n-3，n-4，n-5，n-6出现的次数之和。
初始条件：第一轮的f(1),f(2),f(3),f(4),f(5),f(6)均等于1.
代码：
1、递归方法
#include <iostream>
#include <math.h> using namespace std; int g_maxValue=6; void Probability(int original,int index,int curSum,int* pProbability){
if(index==0){
pProbability[curSum-original]+=1;
return;
}
for(int i=1;i<=6;i++)
Probability(original,index-1,curSum+i,pProbability);
} void PrintProbability(int n){
if(n<1)
return;
int maxSum=n*g_maxValue;
int* pProbability=new int[maxSum-n+1];
for(int i=n;i<=maxSum;i++)
pProbability[i-n]=0;
int curSum=0;
Probability(n,n,curSum,pProbability); int total=pow((double)g_maxValue,n);
double prob=0;
for(int i=n;i<=maxSum;i++){
double ratio=(double)pProbability[i-n]/total;
prob+=ratio;
cout<<i<<" "<<ratio<<" "<<endl;
}
cout<<prob<<endl;
cout<<endl; delete[] pProbability;
} int main()
{
int n=5;
PrintProbability(n);
return 0;
}
2、动态规划
#include <iostream>
#include <math.h> using namespace std; int g_maxValue=6;
void PrintProbability(int n){
if(n<1)
return; int* pProbability[2];
pProbability[0]=new int[g_maxValue*n+1];
pProbability[1]=new int[g_maxValue*n+1]; for(int i=0;i<=g_maxValue*n;i++){
pProbability[0][i]=0;
pProbability[1][i]=0;
} int flag=0;
for(int i=1;i<=g_maxValue;i++)
pProbability[flag][i]=1; for(int k=2;k<=n;k++){
for(int i=0;i<k;i++)
pProbability[1-flag][i]=0;
for(int i=k;i<=g_maxValue*k;i++){
pProbability[1-flag][i]=0;
for(int j=1;j<=i && j<=g_maxValue;j++)
pProbability[1-flag][i]+=pProbability[flag][i-j];
}
flag=1-flag;
} int total=pow((double)g_maxValue,n);
double prob=0;
for(int i=0;i<=g_maxValue*n;i++){
//cout<<pProbability[flag][i]<<endl;
double ratio=(double)pProbability[flag][i]/total;
prob+=ratio;
cout<<i<<" "<<ratio<<" "<<endl;
}
cout<<prob<<endl;
cout<<endl; delete[] pProbability[0];
delete[] pProbability[1];
} int main()
{
int n=5;
PrintProbability(n);
return 0;
}