【劍指Offer面試程式設計題】題目1360：樂透之猜數遊戲--九度OJ

題目描述：

六一兒童節到了,YZ買了很多豐厚的禮品,準備獎勵給JOBDU裡辛勞的員工。為了增添一點趣味性,他還準備了一些不同類型的骰子,打算以擲骰子猜數字的方式發放獎品。例如,有的骰子有6個點數(點數分别為1~6),有的骰子有7個(點數分别為1~7),還有一些是8個點數(點數分别為1~8) 。他每次從中拿出n個同一類型的骰子(假設它們都是擁有m個點數并且出現機率相同)投擲,然後讓員工在紙上按優先級(從高到低)的順序寫下3個數上交,表示他們認為這些骰子最有可能的點數之和是多少。第一個數就猜對的人,是一等獎;第二個數才猜對的人是二等獎;如果三個數都不是正确答案,别灰心！YZ還準備了很多棒棒糖。ZL很聰明,他想了想,打算把機率(以保留兩位小數的機率計)最高的三個數找出來,如果有機率相同,則選擇其中點數和最小的那個數。你覺得ZL會依次寫下哪三個數？

輸入：

輸入有多組資料。

每組資料一行,包含2個整數n(0<=n<=10),m(6<=m<=8),n表示YZ拿出的骰子數,m表示骰子擁有的點數。如果n=0,則結束輸入。

輸出：

對應每組資料,輸出ZL最可能依次寫下的點數,以及其對應的機率值。機率值按4舍5入要求保留2位小數。每組資料之間空一行,注意:最後一組資料末尾無空行。

樣例輸入：

1 6
4 6
3 7
0      

樣例輸出：

1 0.17
2 0.17
3 0.17

13 0.11
14 0.11
15 0.11

12 0.11
10 0.10
11 0.10      

【解題思路】本題的機率等于次數除以總的次數，是以，我們可以記錄次數，這樣更加簡單。然後，我們發現每投擲一次得到的次數，都與前面幾次有關系，是以我們可以總結該問題為dp問題。

      我們可以設aa[i][j]代碼投擲i次，得到總和為j的次數。那麼aa[i][j]+=aa[i-1][j-k],其中k為第i次單個骰子的出現的點數，j為之前所出現的點數。建立dp連接配接式我們可以很快得到結果。當然最後我們需要先算出四舍五入的機率後再排序。

AC code：

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
 
struct st
{
  int idx,val;
  double vl;
};
 
bool cmp(const st &s1,const st &s2)
{
  if(s1.val!=s2.val)
    return s1.val>s2.val;
  else
    return s1.idx<s2.idx;
}
 
int main()
{
  int n,m;
  bool pt=false;
  int aa[11][81];
  while(scanf("%d",&n)!=EOF && n>0)
  {
    scanf("%d",&m);
    memset(aa,0,11*81*sizeof(int));
    for(int i=1;i<=m;++i)
      aa[1][i]=1;
    int all=m;
    for(int i=2;i<=n;++i)
    {
      for(int k=1;k<=m;++k)
      {
        for(int j=i-1;j<=(i-1)*m;++j)
          aa[i][j+k]+=aa[i-1][j];
      }
      all*=m;
    }
    vector<st> vecin;
    for(int i=n;i<=n*m;++i)
    {
      st ts;
      ts.idx=i;
      ts.val=aa[n][i];
      vecin.push_back(ts);
    }
    int ep=pow(m*1.,n);
    for(int i=0;i<vecin.size();++i)
    {
       vecin[i].vl=vecin[i].val*1./ep;
       int tt=(vecin[i].vl+0.005)*100;
       vecin[i].vl=tt*1./100;
       vecin[i].val=tt%100;
    }
    sort(vecin.begin(),vecin.end(),cmp);
    if(pt)printf("\n");
    pt=true;
    for(int i=0;i<3;++i)
    {
      printf("%d %.2f\n",vecin[i].idx,vecin[i].vl);
    }
  }
  return 0;
}
/**************************************************************
    Problem: 1360
    User: huo_yao
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1024 kb
****************************************************************/
           

題目連結：http://ac.jobdu.com/problem.php?pid=1360




九度-劍指Offer習題全套答案下載下傳：http://download.csdn.net/detail/huoyaotl123/8276299