一些經(jīng)典的概率問題

1、 WORD 一些經(jīng)典的概率問題1. 布豐針問題問題：給定間距為2a的平行線，將長度為2c(ca)的棒隨機投向地板（隨機的含義是獨立隨機的x,y坐標(biāo)和角度），問相交概率。解答：限定棒的中心和線的距離不超過a的情況下，考慮棒的一端和某一條特定的直線相交的概率：顯見在特定的角度下，相交的概率是心、線距離的概率，也就是，計算得。注意到和x的分布是獨立的、均勻的，它們的分布函數(shù)互相不影響，所以我們在計算概率的時候?qū)⑦@兩個變量分離，進行累次積分（如果互相影響，要先解方程找出至少一個獨立的，再積分）：最后的P就是答案。2. 多邊形布豐針問題（HDU4978）問題：給定間距為2a的直線和直徑不超過2a的凸多邊

2、形，隨機投擲凸多邊形，問相交概率。解：我們假定不知道上一問的答案（實際上這道題有現(xiàn)成的結(jié)論），完整地再推一遍。當(dāng)然我們可以認為是對連續(xù)多條邊的積分，不過這里我們改成對點的積分，考慮一條直線從a距離處不斷向著中心靠攏，最先碰到的是哪個頂點呢？以A頂點為例，顯然是。這里我們把它拆分開，對于凸多邊形的每一條邊，計算它的兩個端點：3. 拉普拉斯針問題問題：給定正交的間距為2a和2b的平行線，將長度為2c(cab)的棒隨機投向地板，問相交概率。答案：4. 圓上的布豐針問題（原作者M.F.NEUTS）問題：給定一個半徑為R的圓，將長度為2d的棒隨機投向圓中，分dR討論交點個數(shù)z=0、1、2的概率。解答：這

3、里“隨機”是有兩種理解的。一種是點隨機（先x坐標(biāo)再y坐標(biāo)），一種是矢徑角隨機（先取中心到針的距離u再取角度）。就像我們在一個棒上取兩個點，是同時取還是先后取概率會不一樣。當(dāng)然，交度在這一題中沒有意義。為了計算方便，我們采取第一種理解方法，這樣圓每一塊區(qū)域取到的概率和它的面積成正比，而u的概率分布函數(shù)為：分類討論如下：A.d2R顯然P(z=2)=1,P(z=1)=P(z=0)=0B.2R=dR此時一定有P(z=0)=0B1.0u=d-R此時一定有兩個交點p1(u)=0,p2(u)=1B2.d-Ru=R此時如圖：有，由余弦定理：因此令，積分得：P(z=1)的結(jié)果是1減去上述值。C.0d=RC1.0

4、uR-d此時沒有交點。C2.此時最多一個交點，定義同上，有：C3.此時至少一個交點，有：積分結(jié)果是：5. 連續(xù)切圓的期望（ZOJ3744）問題：有一個半徑不超過2的圓，每次隨機在圓取一個點，然后在圓切一個最大的圓，新的圓必須把舊的圓排除在外，問新圓半徑小于等于1所需的步數(shù)的期望。解：顯見，假設(shè)半徑出現(xiàn)在距圓心距離為r處，則概率為，新半徑為，因此期望為，這個方程微分兩次可以變成普通二階微分方程，此處不加求解。6. 有向圖中刪點期望（HDU5036）問題：給定一個定向圖，每次操作隨機在圖取一個頂點，然后刪除這個點和所有這個點能到達的點。問期望的操作次數(shù)是多少。解：考慮每一個點可以被它的所有直接的和

5、間接的父親刪除（有環(huán)也無所謂）。假設(shè)這些點一共有k個，那么這個點直接被刪的概率就是1/k，因此只要將原圖反向之后求出可達矩陣，然后判斷每個點的可達點有多少個，取倒數(shù)相加即可。7. 連通圖的概率（POJ3557）問題：先確定頂點的個數(shù)N和一個概率p，然后遍歷所有的點對(i,j)，如果生成的0到1之間的隨機實數(shù)小于p，那么就會有一條邊連接這兩個頂點。問最后得到的圖是連通圖的概率有多少？解：dpi為在當(dāng)前情況下，構(gòu)成i個點的連通點集的概率。計算時我們反過來考慮不能連通的情況。從(i-1)個點中，劃分出一個(j-1)的子集，共有種；將這個子集加上新加入的點，若使這j個點構(gòu)成連通點集，概率為dpj；若使

6、這i個點不連通，則在上面所說的兩個子集之間沒有連通的邊，因為一共可能有種連邊方式，所以概率為。綜合考慮得：8. 走出迷宮的期望（HDU4035）問題：迷宮是一個樹形圖，從1開始，每個點有概率回到1，有概率逃脫，剩下的情況以均等概率走一步到達任何一個相鄰點。問逃脫迷宮的期望步數(shù)。解：設(shè)表示i點走出的期望，表示i點的父親節(jié)點，表示i的第j個孩子，表示i的度數(shù)，那么有葉子節(jié)點：非葉子節(jié)點：另：，則有：從葉子節(jié)點開始做樹狀DP，直到計算出1的值，答案為9. 狀壓期望問題（HDU4921）問題：給定若干條鏈，每條鏈可以從頭開始選取若干長度（可以是0）的一段。鏈條上的每個點有一個分數(shù)?？偟梅质紫扔扇窟x取

7、的點的分數(shù)和構(gòu)成。若每條鏈長度為i的元素被選取個數(shù)大于1，而一共有個這樣的點，那么你還會額外得到的獎勵分，式中是這一層選取的點分數(shù)和。問最終得分的期望。解：分層考慮每一層的可能選取方法，狀壓枚舉之，統(tǒng)計每一種分布對應(yīng)的得分以與在總選取方案中占的比例即可。10. 放棋子期望問題（ZOJ3822）問題：給定NxM的空棋盤，每次隨機選取一個空格放上棋子，直到每行每列都至少有一個棋子為止，問棋子個數(shù)的期望。解：三維概率DP，dpijk表示放了i個棋子占據(jù)j行k列的概率（注意：不是從那個狀態(tài)開始到達目標(biāo)的期望）。于是得到方程：最后計算i*(dpiNM-dpi-1NM)之和即可。11. 鈍角三角形概率問題問題：給定1xL的矩形，每次隨機選取三個點，問這三個點構(gòu)成的三角形為鈍角的概率。解：記答案為P(L)，記三點為，顯見六個變量各自獨立服從均勻分布。于是有設(shè)F(x)是X的累計分布函數(shù)（具體解法是先設(shè)x1=a然后在直角坐標(biāo)系中畫出x2x3，計算滿足條件的區(qū)域所占面積，最后對a積分），那么有此處積分計算較為繁瑣?？偨Y(jié)概率論中的多個連續(xù)變量的問題通?？梢赞D(zhuǎn)化成連續(xù)的積分問題，把握住概率密度函數(shù)就可以迎刃而解。原問題