一些經(jīng)典的概率問題-資料下載頁
2025-03-24 05:29本頁面
【正文】 選取方案中占的比例即可。10. 放棋子期望問題（ZOJ3822）問題：給定NxM的空棋盤，每次隨機(jī)選取一個(gè)空格放上棋子，直到每行每列都至少有一個(gè)棋子為止，問棋子個(gè)數(shù)的期望。解：三維概率DP，dp[i][j][k]表示放了i個(gè)棋子占據(jù)j行k列的概率（注意：不是從那個(gè)狀態(tài)開始到達(dá)目標(biāo)的期望）。于是得到方程：dpijk=jki+1NMi+1dpi1jk+kNj+1NMi+1dpi1j1k+jMk+1NMi+1dpi1jk1+Nj+1Mk+1NMi+1dpi1j1k1最后計(jì)算i*(dp[i][N][M]dp[i1][N][M])之和即可。11. 鈍角三角形概率問題問題：給定1xL的矩形，每次隨機(jī)選取三個(gè)點(diǎn)，問這三個(gè)點(diǎn)構(gòu)成的三角形為鈍角的概率。解：記答案為P(L)，記三點(diǎn)為P1(x1,y1),P2(x2,y2),P3(x3,y3)，顯見六個(gè)變量各自獨(dú)立服從均勻分布。于是有PL=3P角P1是鈍角=3PX+Y0X=x2x1x3x1Y=y2y1y3y1設(shè)F(x)是X的累計(jì)分布函數(shù)（具體解法是先設(shè)x1=a然后在直角坐標(biāo)系中畫出x2x3，計(jì)算滿足條件的區(qū)域所占面積，最后對(duì)a積分），那么有PL=3∞+∞FxL2dF(x)此處積分計(jì)算較為繁瑣?？偨Y(jié)概率論中的多個(gè)連續(xù)變量的問題通?？梢赞D(zhuǎn)化成連續(xù)的積分問題，把握住概率密度函數(shù)就可以迎刃而解。原問題不便于計(jì)算的，求解其反面。期望的計(jì)算，可以列出當(dāng)前點(diǎn)和可以到達(dá)的點(diǎn)然后遞推，也可以有定義求解?？梢苑纸獾膯栴}，用指示器隨機(jī)變量求解。概率問題的DP，大多從初狀態(tài)開始遞推；而期望問題的DP，大多以到達(dá)終點(diǎn)還需要多少為基準(zhǔn)逆向遞推。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1