LintCode 20 骰子求和

2019-11-08 02:38:11

字體：大中小

來源：轉載

供稿：網友

題目:dicesSum

要求:

扔 n 個骰子，向上面的數字之和為 S。給定 Given n，請列出所有可能的 S 值及其相應的概率。

樣例:

給定 n = 1，返回 [ [1, 0.17], [2, 0.17], [3, 0.17], [4, 0.17], [5, 0.17], [6, 0.17]]。

算法要求:

無

解題思路:

剛開始的時候，用的時模擬投擲的方法，結果只能計算3個骰子的概率。后來在1，2，3骰子的概率分布中發現了規律。現在我把分布圖發一下，大家看看有沒有什么規律前面為總和，后面為次數 1 1 2 1 3 1 2 1 3 2 4 3 3 1 4 3 5 6 4 1 5 4 6 10 5 1 6 5 7 15 6 1 7 6 8 21 8 5 9 25 9 4 10 27 10 3 11 27 11 2 12 25 12 1 13 21 14 15 15 10 16 6 17 3 18 1分別是1，2，3個骰子的次數。可以看出，最小的點數都是骰子的個數，最大是骰子的個數 * 6。再看一下，1個骰子和2個骰子的差距和聯系。拿2個骰子的分布表來說，總和為2的次數為1次，總和為3的次數為2次，依次到總和為8的時候，發現次數為5，先把疑問放在這里，等會回頭來看。接著看2個骰子和3個骰子，總和為3的次數為1，總和為4的次數為3，依次到總和為9的時候，次數為25，本來以為1，3，6，10，15，21發現規律了，其實不然，我為什么說要1和2一起看，2和3一起看呢？現在將上面2次觀察的結果拿在一起看一看，能不能發現什么規律。2個骰子總和為8的次數為1+1+1+1+1=5,總和為7的次數為1+1+1+1+1+1=6，那么看一下3個骰子總和為9的次數為2+3+4+5+6+5=25,看一下總和為8的次數為1+2+3+4+5+6=21，是不是發現了規律。如果發現了規律，讀者可以拿紙寫一下4個骰子的分布圖（最下面會貼出來4個骰子的分布圖）。如果讀到這里明白了，理解了，還不會寫，那就再從頭看一遍吧。。

算法如下:

double setDoublePRecision(double d, int n) { int temp = d * pow(10.0, n + 3); if (temp % 1000 >= 499) { temp -= temp % 1000; temp += 1000; } else { temp -= temp % 1000; } return temp / pow(10.0, n + 3); } vector<pair<int, double> > dicesSum(int n) { vector<pair<int, double> > vec; double m = pow(6, n); double time[n*6 + 1][2]; int last = 0; int now = 1; for (int i = 1; i < n*6 + 1; i++) { time[i][now] = 1; time[i][last] = 0; } for (int i = 2; i <= n; i++) { now += last; last = now - last; now -= last; for (int j = i; j <= i * 6; j++) { time[j][now] = 0; for (int k = 1; k <= 6; k++) { if (j - k >= i - 1 && j - k <= i * 6 - 6) { time[j][now] += time[j - k][last]; } } } } for (int k = n; k < n * 6 + 1; k++) { pair<int, double> p; p.first = k; p.second = setDoublePrecision(time[k][now]/m, 2); vec.push_back(p); } return vec; }

補充

下面是4個骰子的，再貼出來一個50個骰子的4 15 46 107 208 359 5610 8011 10412 12513 14014 14615 14016 12517 10418 8019 5620 3521 2022 1023 424 1下面是50個骰子的50 151 5052 127553 2210054 29282555 316251056 2898962557 23191490058 165234772559 1064776895060 6281371505561 34254199980062 174060948775063 829668543410064 3730464658095065 15898658323772066 64490487783767567 249881191711515068 927783169178862669 3310135112526969670 11376452065846697671 37747662697443065672 121159315349725158473 376862830524663193674 1137815587177531801675 3339338047190670950476 9539599545071417753677 26559057463258736230478 72143191062907636940879 191393180094869012480080 496385732932091668070481 1259667322396517335040082 3130329809355818611507283 7623433090236471364812884 18207196127494790761676885 42672934609137666569011286 98207588519055658791731287 222059647679977912428134488 493582318496199027248332889 1079030751051588012972441690 2321122691356475647223398491 4915255339370737447416627292 10250859844158831265736294493 21062647494554792338705612894 42654689875077895826073190495 85167850527867796081292083296 167720204105796591307194368097 325862217583921569609862348898 624816700661998060984231526499 11826758184971481912837144576100 22105054690914109051786756096101 40807766889960957171640303616102 74426331366143498666393993216103 134135917079908275320791236608104 238943734726994109399023222784105 420795669863941446284232097792106 732758215324367850067955023872107 1261969259771325128085604401152108 2149891831514317318666491789312109 3623612879581447239348864942080110 6043640346604650949260045451264111 9976040508464536697090063990784112 16300042701998167798456105566208113 26366688036068095922448199843840114 42230031124767134932033521844224115 66980185783001117781688972214272116 105217541543334346970712216961024117 163720191094905172618374029508608118 252372409575413793194274900148224119 385441265120671675208073406840832120 583311340952280287154631188938752121 874814127386972787738765074366464122 1300318598090814484648122082394112123 1915782083369040976180865837039616124 2797994489233293584610913146634240125 4051282172863713527645763843129344126 5815967528628700696614541207797760127 8278902789701428938737899613978624128 11686406958072359501084195305816064129 16359927445172843359078204624076800130 22714716432711158094504151062937600131 31281749104483644316352213281669120132 42733009591776564311023597062717440133 57910124024005790326366984747352064134 77856123013322064311823247781920768135 103849864884592972506473858271805440136 137442345783118050884988130715238400137 180493767427391277724992029904076800138 235209836877307326842264992954187776139 304175350418849666956651117276037120140 390382687215016679008612838793019392141 497252436045344038915076182547365888142 628643034682218344840100598201188352143 788846055605075602315290445296435200144 982563666214909024696219498310533120145 1214864869165193850303792198319079424146 1491117428450357943814892549507645440147 1816892942006990206009991699858718720148 2197843352983018546169207711453937664149 2639548305161884949689113647360507904150 3147334129588464359562096047565045760151 3726066863256740511750802106673528832152 4379923486946076221727303621261918208153 5112147444366405114027240834174287872154 5924796363582303813065557156372152320155 6818491621976713107237380706334146560156 7792180844982473590887686256319266816157 8842925471658356937798517720453480448158 9965726030187900697398975314572345344159 11153397635757119137731885728008241152160 12396507374046471384208177845239808000161 13683383627432368228696558686145871872162 15000205047112809379804266437757894656163 16331173834333526764862981969973084160164 17658774382872218649252361819920531456165 18964114318679270097659414738758533120166 20227340759956928081916101736418770944167 21428120452432806847299035547238924288168 22546168567052286915005973893413339136169 23561807636520859357989241316291117056170 24456535588845715475244717094289276928171 25213580307592797778918949646430633984172 25818417752360614623609320814925578240173 26259231483293091467107946679070883840174 26527293448223798880814724639153455104175 26617249029052548232041745031318470656176 26527293448223808325547690378443882496177 26259231483293091467107946679070883840178 25818417752360614623609320814925578240179 25213580307592797778918949646430633984180 24456535588845715475244717094289276928181 23561807636520859357989241316291117056182 22546168567052286915005973893413339136183 21428120452432806847299035547238924288184 20227340759956930443099343171241377792185 18964114318679272458842656173581139968186 17658774382872218649252361819920531456187 16331173834333529126046223404795691008188 15000205047112811740987507872580501504189 13683383627432372951063041555791085568190 12396507374046473745391419280062414848191 11153397635757121498915127162830848000192 9965726030187904239173837466806255616193 8842925471658358118390138437864783872194 7792180844982474771479306973730570240195 6818491621976713107237380706334146560196 5924796363582303813065557156372152320197 5112147444366403343139809758057332736198 4379923486946075041135682903850614784199 3726066863256739331159181389262225408200 3147334129588464359562096047565045760201 2639548305161884064245398109302030336202 2197843352983018251021302532101111808203 1816892942006989615714181341153067008204 1491117428450357943814892549507645440205 1214864869165193555155887018966253568206 982563666214909024696219498310533120207 788846055605075749889243034972848128208 628643034682218418627076893039394816209 497252436045344186489028772223778816210 390382687215016826582565428469432320211 304175350418849740743627412114243584212 235209836877307363735753140373291008213 180493767427391277724992029904076800214 137442345783118106225220351843893248215 103849864884593009399962005690908672216 77856123013322082758567321491472384217 57910124024005799549739021602127872218 42733009591776564311023597062717440219 31281749104483644316352213281669120220 22714716432711162706190169490325504221 16359927445172847970764223051464704222 11686406958072361806927204519510016223 8278902789701431244580908827672576224 5815967528628703002457550421491712225 4051282172863714104106516146552832226 2797994489233293584610913146634240227 1915782083369041552641618140463104228 1300318598090815061108874385817600229 874814127386972931853953150222336230 583311340952280503327413302722560231 385441265120671747265667444768768232 252372409575413865251868938076160233 163720191094905208647171048472576234 105217541543334382999509235924992235 66980185783001126788888226955264236 42230031124767125924834267103232237 26366688036068095922448199843840238 16300042701998167798456105566208239 9976040508464536697090063990784240 6043640346604650949260045451264241 3623612879581446113448958099456242 2149891831514317318666491789312243 1261969259771324705873139335168244 732758215324367568592978313216245 420795669863941375915487920128246 238943734726994039030279045120247 134135917079908275320791236608248 74426331366143481074207948800249 40807766889960948375547281408250 22105054690914104653740244992251 11826758184971477514790633472252 6248167006619977311307431936253 3258622175839215696098623488254 1677202041057966187949850624255 851678505278678235690827776256 426546898750778958260731904257 210626474945547992106532864258 102508598441588312657362944259 49152553393707365884231680260 23211226913564756472233984261 10790307510515880129724416262 4935823184961989198741504263 2220596476799779661152256264 982075885190556587917312265 426729346091376732798976266 182071961274947907616768267 76234330902364713648128268 31303298093558190309376269 12596673223965169156096270 4963857329320917729280271 1913931800948690386944272 721431910629076369408273 265590574632587427840274 95395995450714210304275 33393380471906701312276 11378155871775313920277 3768628305246631936278 1211593153497251584279 377476626974430528280 113764520658466960281 33101351125269700282 9277831691788624283 2498811917115150284 644904877837675285 158986583237720286 37304646580950287 8296685434100288 1740609487750289 342541999800290 62813715055291 10647768950292 1652347725293 231914900294 28989625295 3162510296 292825297 22100298 1275299 50300 1有興趣的可以弄200個骰子的，有能力的可以寫出來10000個骰子的，需要用的高精度運算。所以以后大家玩骰子，一般都是靠中間的點數幾率大喔~

上一篇：有趣的蜂鳴器

下一篇：重拾算法之劍指Offier——樹的子結構