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