程序员面试题精选100题（43）-n个骰子的点数

程序员面试题精选100题(43)-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 PrintProbability(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;
  Probabilty(number,pProbabilities);
  int total=pow((double)g_maxValue,number);
  for(int i=number;i<maxSum;i++)
  {
    double ratio=(double)pProbabilities[i-number]/total;
printf("%d: %e\n",i,ratio);
  }
  delete[] pProbabilities;
}

void Probability(int number,int* pProbabilities)
{
  for(int i=1;i<=g_maxValue;i++)
 probability(number,number,i,pProbabilities);
}

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

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

我们可以考虑换一种思路来解决这个问题。我们可以考虑用两个数组来存储骰子点数每一总数出现的次数。在一次循环中，第一个数组中的第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 PrintProbability(int number)
{
  if(number<1)
 return;
  int* pProbabilities[2];
  pProbabilities[0]=new int[g_maxValue*number+1];
  pProbabilities[1]=new int[g_maxValue*number+1];
  for(int i=0;i<g_maxValue*number+1;i++)
  {
 pProbabilities[0][i]=0;
 pProbabilities[1][i]=0;      
  }
  int flag=0;
  for(int i=1;i<=g_maxValue;i++)
      pProbabilities[flag][i]=1;
  for(int k=2;k<=number;k++)
  {
    for(int i=0;i<k;i++)
      pProbabilities[1-flag][i]=0;
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]=0;
}
flag=1-flag;
  }
  double total=pow((double)g_maxValue,number);
  for(int i=number;i<maxSum;i++)
  {
    double ratio=(double)pProbabilities[i-number]/total;
printf("%d: %e\n",i,ratio);
  }
  delete[] pProbabilities[0];
  delete[] pProbabilities[1];
  delete pProbabilities;
}