阿里巴巴筆試題集第23題及分析-創(chuàng)新互聯(lián)

題目：一個(gè)骰子， 6 面， 1 個(gè)面是 1 ， 2 個(gè)面是 2 ， 3 個(gè)面是 3 ， 問(wèn)平均擲多少次能使 1 、 2 、 3 都至少出現(xiàn)一次。

貴南網(wǎng)站建設(shè)公司創(chuàng)新互聯(lián),貴南網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為貴南上千多家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\成都外貿(mào)網(wǎng)站建設(shè)要多少錢(qián)，請(qǐng)找那個(gè)售后服務(wù)好的貴南做網(wǎng)站的公司定做！

方法： 面對(duì)面試概率題幾乎屢試不爽的分叉樹(shù)遞歸列方程法。

這是一個(gè)求數(shù)學(xué)期望的問(wèn)題，最終是求 1 ， 2 ， 3 出現(xiàn)至少一次的最短長(zhǎng)度的期望。

這樣分叉樹(shù)的每個(gè)節(jié)點(diǎn)是一個(gè)期望狀態(tài)，而每個(gè)分叉是一次投擲結(jié)果。將后續(xù)期望出現(xiàn) 1 、 2 、 3 各至少一次的情形記作 L 123 （即題目所求），將后續(xù)期望出現(xiàn) 1 、 2 各至少一次（ 3 無(wú)關(guān)）情形記作 L 12 ，而 1 至少一次（ 2 ， 3 無(wú)關(guān)）情形 L 1 ，其余數(shù)值符號(hào)類(lèi)推，則樹(shù)結(jié)構(gòu)如下（列出 4 級(jí)結(jié)構(gòu)已經(jīng)足夠）：

?

接下來(lái)，就是要排出方程，因?yàn)橐还?7 個(gè)未知數(shù)，如果排出 7 個(gè)線性方程就能解決問(wèn)題。
在此我向大家推薦一個(gè)架構(gòu)學(xué)習(xí)交流圈。交流學(xué)習(xí)企鵝群號(hào)：948368769（里面有大量的面試題及答案）里面會(huì)分享一些資深架構(gòu)師錄制的視頻錄像：有Spring，MyBatis，Netty源碼分析，高并發(fā)、高性能、分布式、微服務(wù)架構(gòu)的原理，JVM性能優(yōu)化、分布式架構(gòu)等這些成為架構(gòu)師必備的知識(shí)體系。還能領(lǐng)取免費(fèi)的學(xué)習(xí)資源，目前受益良多

這方程組里的未知數(shù)對(duì)應(yīng)上述的狀態(tài)，而其數(shù)值則是一個(gè)對(duì)長(zhǎng)度（投擲次數(shù)）的數(shù)學(xué)期望。

根據(jù)這個(gè)樹(shù)狀結(jié)構(gòu)和其中的遞歸關(guān)系，這個(gè)方程組就是：

L 123 ? = p 1 ? (L 23 + 1) + ? p 2 ? (L 13 +1) + p 3 ? (L 12 ? + 1) = p 1 ? L 23 ? + p 2 ? L 13 +? p 3 ? L 12 ? + 1

（以這個(gè) L 123 為例，解釋?zhuān)稊S 1 的概率是 p 1 而由此得到的結(jié)果是需要期待后續(xù) 2 和 3 各至少出現(xiàn)一次，于是長(zhǎng)度期望是 L 23 + 1 ，加 1 是因?yàn)橥稊S了一次，亦即即增進(jìn)一級(jí)）

L 23 ? = ? p 1 ? L 23 ? + p 2 ? L 3 +? p 3 ? L 2 ? + 1

L 13 ? = ? p 1 ? L 3 ? + p 2 ? L 13 +? p 3 ? L 1 ? + 1

L 12 ? = ? p 1 ? L 2 ? + p 2 ? L 1 +? p 3 ? L 12 ? + 1

L 1 ? = p 1+p 2 ? L 1 +? p 3 ? L 1 ? + 1

（這里實(shí)際上是 ? L 1 ? =p 1 ? ·1 + p 2 ? (L 1 + 1) + p 3 ? (L 1 ? + 1) ? = p 2 ? L 1 +? p 3 ? L 1 ? + 1 ，因?yàn)閷?duì) L 1 情形，如果投了 1 就目的達(dá)到終止了）

L 2 ? = p 2+ p 1 ? L 2 ? +? ? p 3 ? L 2 ? + 1

L 3 ? = p 3+ p 1 ? L 3 ? + p 2 ? L 3 + 1

（以上一開(kāi)始沒(méi)注意，多加了懸空的概率項(xiàng)，故計(jì)算有誤）

其中 ? p 1 ， p 2 ? 和 ? p 3 分別是擲出 1 ， 2 和 3 的概率，即 1/6 ， 1/3 ， 1/2 。

于是求解這個(gè)方程，得到：

L 1 ? = 6 ， ? L 2 ? = 3 ， ? L 3 ? = 2

L 12 ? = 7 ， ? L 13 ? = 13/2 ， ? L 23 ? = 19/56

L 123 ? = ? 219/30 = 7.3 ?259/36 ~= 7.14

故以上如果沒(méi)有計(jì)算錯(cuò)誤，該題結(jié)果是，平均擲 7.3 ?約7.14次可出現(xiàn)這些面值各至少一次。

【另一解法】感謝 4 樓 aaaxingruiaaa 同學(xué)提供的答案（指示器變量法），整理如下：

定義隨機(jī)變量 X n ，其可能值為 0 或 1 ，其值為 1 表示 “ 前 n 次擲骰子， 1 ， 2 ， 3 沒(méi)能都至少出現(xiàn)一次 ” 的事件，其值為 0 表示這個(gè)事件沒(méi)有發(fā)生，即 “ 前 n 次擲骰子， 1 ， 2 ， 3 各至少出現(xiàn)一次 ” 。

令 p n 為 “ 擲 n 次骰子， 1 ， 2 ， 3 沒(méi)能都至少出現(xiàn)一次 ” 的概率，所以顯然 p n ? = Pr{ X n =1} ，于是 p n ? = 1·Pr{ X n =1} + 0·Pr{ X n =1}?= E[ X n ] ，即這個(gè)隨機(jī)變量的數(shù)學(xué)期望。

令隨機(jī)變量 X 表示 1 ， 2 ， 3 剛好全部出現(xiàn)過(guò)需要的投擲次數(shù)?？梢?jiàn)題目要求的就是 E[X] 。

關(guān)鍵等式： X = ? Sigma (n=0 to ? Inf; ?X n )??? （這里 Sigma 是求和號(hào)，求和范圍是 n 從 0 到無(wú)窮大）

說(shuō)明一下，等式兩邊都是隨機(jī)變量，假設(shè)對(duì)于某個(gè)隨機(jī)實(shí)例（例如，這里指一次具體的投擲序列），其對(duì)應(yīng)事件是： “ 投了 K 次恰好 1 ， 2 ， 3 都出現(xiàn)了 ” ，于是等式左邊顯然等于 K ；而等式右邊，對(duì)于 n < K ，由于這些項(xiàng)的對(duì)應(yīng)定義事件發(fā)生了（即 1 ， 2 ， 3 沒(méi)能出現(xiàn)），所以他們的實(shí)例值是 1 ，而對(duì)于 n?K ，則由于對(duì)應(yīng)定義事件都沒(méi)發(fā)生，實(shí)例值為 0 ，可見(jiàn)這個(gè)和也是 K 。故兩側(cè)相等。（為了達(dá)到這個(gè)相等關(guān)系，可以看出需要把 X 0 包含在內(nèi)的必要性）

值得注意的是（但對(duì)于解這道題也可以不去注意，但注意一下有利于比較深入地理解），對(duì) n < 3 ， X n 顯然恒為1。而對(duì)于 n?3 ，這些隨機(jī)變量不是獨(dú)立的。他們的相關(guān)性是不容易求出的，唯一容易知道的是，當(dāng)序列中一個(gè)項(xiàng)為 0 時(shí)，其后的項(xiàng)均為 0 。好在對(duì)于這題我們不需要擔(dān)憂(yōu)這個(gè)相關(guān)性。

由于數(shù)學(xué)期望的加性與隨機(jī)變量的相關(guān)性無(wú)關(guān)（這是數(shù)學(xué)期望一個(gè)很令人高興的性質(zhì)），所以即便這樣， E[X] 也能容易求出：

E[X] = ? Sigma (n=0 to Inf; E[ X n ] ) =? Sigma (n=0 to ? Inf; ? p n )

p n 的比較直觀的求法也由 aaaxingruiaaa 同學(xué) 提供了，即所謂容斥原理。稍微解釋一下，由于 p n 考慮的是 n 次投擲三者沒(méi)有全部出現(xiàn)，于是就是其中兩者出現(xiàn)或僅一者出現(xiàn)。假設(shè)單次投擲 1 ， 2 和 3 出現(xiàn)的概率分別為： r 1 ， r 2 和 r 3 。于是 ( r 1 + r 2 ) n 表征 n 次投擲只出現(xiàn) 1 或 2 的概率，這其中包括了出現(xiàn)全 1 和全 2 的情形，于是求 p n 可由這樣的項(xiàng)求和并剔除重復(fù)計(jì)算的單面值情形，于是：

p n ? = ( r 1 + r 2 ) n + ( r 1 + r 3 ) n + ( r 2 + r 3 ) n - r 1 n - r 2 n - r 3 n ，當(dāng) n > 0 ； ? 而 p 0 ? = 1 （由定義；同時(shí)也可以檢驗(yàn)看出，這個(gè) p n 在 n 為 1 和 2 的時(shí)候都是 1 ）

于是由等比級(jí)數(shù)（等比數(shù)列求和）公式：

E[X] = ? 1 + Sigma (n=1 to Inf; ( r 1 + r 2 ) n + ( r 1 + r 3 ) n + ( r 2 + r 3 ) n - r 1 n - r 2 n - r 3 n = 1 + (1 - ? r 3 ) /? r 3 ? + (1 - ? r 2 ) / ? r 2 ? + (1 - ? r 1 ) / ? r 1 ? - ? r 1 ? /?(1 - ? r 1 ) - ? r 2 ? /?(1 - ? r 2 ) - r 3 ? /?(1 - ? r 3 ) = 7.3

【程序仿真】

以下程序進(jìn)行一千萬(wàn)輪投擲的仿真，結(jié)果基本在 7.3 周?chē)?。至此此題答案 7.3 毫無(wú)疑問(wèn)了。

[csharp]view plaincopy

static ? void ?Main( string []?args)?? 
{??
????Random?rand?=?new ?Random();?? 
????int []?diceSurfaces?=? new ? int [6]?{?1,?2,?2,?3,?3,?3?};??? //?6個(gè)面 ?? 
????int ?nRounds?=?10000000;? //?投擲輪數(shù) ?? 
????long ?totalTimes?=?0;???? //?所有輪中投擲數(shù)加起來(lái)的總投擲次數(shù) ?? 
????for ?( int ?iRounds?=?0;?iRounds?<?nRounds;?iRounds++)?? 
????{??
????????bool []?occurred?=? new ? bool [3]?{? false ,? false ,? false ?};?? //?各面值出現(xiàn)標(biāo)記 ?? 
????????int ?sumPicked?=?0;?? //?出現(xiàn)不同面值個(gè)數(shù) ?? 
????????int ?times?=?0;?? 
????????for ?(;?;?)?? 
????????{??
????????????int ?iSurface?=?rand.Next(6);?? 
????????????int ?value?=?diceSurfaces[iSurface]?-?1;?? 
????????????times++;??
????????????if ?(!occurred[value])?? 
????????????{???//?出現(xiàn)新面值 ?? 
????????????????occurred[value]?=?true ;?? 
????????????????sumPicked++;??
????????????????if ?(sumPicked?==?occurred.Length)?? 
????????????????{???//?全部出現(xiàn)，結(jié)束此輪 ?? 
????????????????????break ;?? 
????????????????}??
????????????}??
????????}??
????????totalTimes?+=?times;??
????}??
????Console.WriteLine("average?number?of?times?=?{0}" ,?(( double )totalTimes)?/?nRounds);?? 
}??

創(chuàng)新互聯(lián)www.cdcxhl.cn，專(zhuān)業(yè)提供香港、美國(guó)云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開(kāi)啟，新人活動(dòng)云服務(wù)器買(mǎi)多久送多久。

網(wǎng)站名稱(chēng)：阿里巴巴筆試題集第23題及分析-創(chuàng)新互聯(lián)
標(biāo)題路徑：http://bm7419.com/article14/dscgge.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App設(shè)計(jì)、微信公眾號(hào)、小程序開(kāi)發(fā)、電子商務(wù)、網(wǎng)站設(shè)計(jì)公司、品牌網(wǎng)站設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)