程序員面試題精選100題(43)-n個骰子的點數

時間:2019-09-22 編輯:范文亭
程序員面試題精選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;
}
本文已影響
相關文章
大亨pk10计划苹果版