题目：把n个骰子仍在地上，所有骰子的点数和为s。输入n，打印s所有可能取值的概率。

分析1：容易知道，有n个骰子的话，s的最小取值为n（全为1），最大取值为6n（全为6）。

如果只有1个骰子，那么很简单，s取1，2，3，4，5，6的情况数均为1，概率为1/6；设想有n个骰子，出现和为s，我们可以这样考虑，如果第一个骰子有6中情况，取1，2，3，4，5，6；那么剩下的n-1个骰子的和则分别取s-1，s-2, s-3,s-4,s-5, s-6，我们将所有这些情况相加，就可以得出总的情况数。看出了吗？亲，这是什么问题？对了，还是递归问题，根据以上分析我们不难写出如下的递归公式：

对公式的说明：（1）f(s,n)表示，有n个骰子，出现和为s的情况总数；（2）对于公式第二行的解释；如果有一个骰子，那么点数为8或者0的情况数，我们记为0，这样是为了在计算递归时更为方便所作的处理；例如有公式可知f(8,2)=f(7,1)+f(6,1)+f(5,1)+f(4,1)+f(3,1)+f(2,1)，如果我们规定了f(7,1)=0那么计算会方便很多。

有了上面的分析，我们可以写出如下的C++代码：

1 #include
     
        2 #include
      
         3 #include
       
          4 using namespace std;  5  6  7 int diceMaxValue = 6;  8 //计算给定diceNumber个骰子，出现和为diceTotalSum的所有可能情况的总数  9 int fun(int diceTotalSum, int diceNumber) 10 {
   11     //骰子数小于1，错误； 12     if(diceNumber < 1) 13     {
   14         cout<<"diceNumber must >= 1"<
        
         = diceNumber && diceTotalSum <= diceMaxValue*diceNumber)) 23             return 1; 24         else 25             return 0; 26     } 27 28     //n>1，递归； 29     if(diceNumber > 1) 30     {
   31         int sum=0; 32         for(int i = 1; i <= diceMaxValue;++i){
   33             sum += fun(diceTotalSum-i,diceNumber-1); 34         } 35         return sum; 36     } 37 } 38 39 //给定number个骰子，打印出现各种情况的概率 40 void printSumProbabilityOfDice(int number) 41 {
   42     if(number < 1) 43     {
   44         return; 45     } 46 47     int maxSum = number * diceMaxValue; 48     float *pProbability = new float[maxSum - number + 1]; 49     50     //数组pProbability存放出现和s时的情况数 51     for(int s = number;s <= maxSum;++s) 52     {
   53         pProbability[s-number] = fun(s,number); 54     } 55     56     //计算总共出现所有的情况数 57     int total = pow(diceMaxValue,number); 58 59     //计算概率，打印概率 60     for(int j = 0;j < maxSum - number + 1;++j) 61     {
   62         pProbability[j] /= total; 63         cout<
         
          <<"\t"<
          
           <
          
         
        
       
      
     

我们计算3个骰子的情况，运行情况如下：

在开始的定义中，我定义了一个表示单个骰子最大值的变量，并赋值为6，是借鉴了博主所说的保证代码的可重用性。

 

分析2：和算法2中求解斐波那契数列的方法类似，递归的效率太差，我们可以正向来求解，假设我们有一个数组表示k-1个骰子中各点数的情况，令第s个分量表示和为s时情况总数，那么当有k个骰子是，其和为s时的情况总数，就是表示k-1骰子的数组中的s-1,s-2,s-3,s-4,s-5,s-6的和（分别令引入的第k个骰子的值分别取1，2，3，4，5，6即可，其实和分析1的思路差不太多）。根据这个思想，我们可以用两个数组交替表示数组k-1和数组k，于是我们有如下的代码：

#include
     
       #include
      
        #include
       
         using namespace std; int diceMaxValue = 6; void PrintProbabilityOfDice(int number) {
   double* pProbability[2];     pProbability[0] = new double[number * diceMaxValue + 1];     pProbability[1] = new double[number * diceMaxValue + 1]; //初始化数组     for(int i = 0;i < number * diceMaxValue + 1;++i)     {
           pProbability[0][i]=0;         pProbability[1][i]=0;     } int flag = 0; //将第一个数组下标为1-6的赋值为1     for(int a = 1;a <= diceMaxValue;++a)     {
           pProbability[flag][a] = 1;     } //骰子数k从2到n循环；对于每一k，s取值为[k,6k]，对于每一个s计算前一个数组 //的s-1,s-2,s-3,s-4,s-5,s-6;因为前一个数组的最小值为k-1,因为因而有s-j>=k-1；     for(int k = 2;k <= number;++k)     {
   for(int s = k; s <= diceMaxValue * k;++s)         {
               pProbability[1-flag][s] = 0; for(int j = 1;j <= diceMaxValue && j <= s - k + 1;++j)             {
                   pProbability[1-flag][s] += pProbability[flag][s-j];             }         }         flag = 1-flag;     } //除以总数，计算并输出概率；     double total = pow((double)diceMaxValue,number); for(int ss = number;ss <= number * diceMaxValue;++ss)     {
           pProbability[flag][ss] /= total;         cout<
        
         <<"\t"<
         
          <
         
        
       
      
     

运行结果如下：

 

最后分析：我们看到和【算法02】中提到的一样，虽然该算法的时间复杂度提高了很多，但是动态创建了两个数组，而且每一个的数组长度都没分析1中的长度多了一个n，因而还是以空间换时间的思想。好了，这个算法就到这，祝各位愉快！

 

参考文献：

【1】何海涛博客：

【2】Wikipedia:

【3】

 

 

注：

1）本博客所有的代码环境编译均为win7+VC6。所有代码均经过博主上机调试。

2）博主python27对本博客文章享有版权，网络转载请注明出处。对解题思路有任何建议，欢迎在评论中告知。