一些经典的概率问题的分析

《一些经典的概率问题的分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一些经典的概率问题1.布丰针问题问题：给定间距为2a的平行线，将长度为2c(c

2、=aa2πPθdθ2c0P==2ππa最后的P就是答案。2.多边形布丰针问题（HDU4978）问题：给定间距为2a的直线和直径不超过2a的凸多边形，随机投掷凸多边形，问相交概率。解：我们假定不知道上一问的答案（实际上这道题有现成的结论），完整地再推一遍。当然我们可以认为是对连续多条边的积分，不过这里我们改成对点的积分，考虑一条直线从a距离处不断向着中心靠拢，最先碰到的是哪个顶点呢？以A顶点为例，显然是α1+α3。这里我们把它拆分开，对于凸多边形的每一条边，计算它的两个端点：0π−OB,AB1P=OAcosθdθ+OBcosθdθ2πaAB0π−

3、OA,AB11P=OBsinOB,AB−OAsinOA,AB=AB2πa2πaABAB3.拉普拉斯针问题问题：给定正交的间距为2a和2b的平行线，将长度为2c(cR讨论交点个数z=0、1、2的概率。解答：这里“随机”是有两种理解的。一种是点随机（先x坐标再y坐标），一种是矢径角随机（先取中心到针的距离u再取角度）。就像我们在

4、一个棒上取两个点，是同时取还是先后取概率会不一样。当然，交度在这一题中没有意义。为了计算方便，我们采取第一种理解方法，这样圆内每一块区域取到的概率和它的面积成正比，而u的概率分布函数为：2u,0≤x≤Rgu=R20,>分类讨论如下：A.d>2R显然P(z=2)=1,P(z=1)=P(z=0)=0B.2R>=d>R此时一定有P(z=0)=0B1.0

5、(u)du+p2u×g(u)du0d−Rd−R2uduR2R2−d2−u22uduPz=2=+cos−1−1R2π2duR20d−Rd令γ=，积分得：Rγ42+γ2γPz=2=4−γ2−1+sin−1−cos−1ππ4π2P(z=1)的结果是1减去上述值。C.0

6、24γ2γ81+γPz=1=1−γ2−4−γ2−2+cos−1+sin−1π4π2π242+γ−sin−1π42γ12γPz=2=1−4−γ2−1−γ2−cos−1π2π241+γ42+γ−sin−1+sin−1π2π45.连续切圆的期望（ZOJ3744）问题：有一个半径不超过2的圆，每次随机在圆内取一个点，然后在圆内切一个最大的圆，新的圆必须把旧的圆排除在外，问新圆半径小于等于1所需的步数的期望。解：显见Ex≤1=0，假设半径出现在距圆心距离为r处，则2πr2rr+x概率为Pr==，新半径为，因此期望为Ex=1+πx2x22xr+xx2t−xPrE()dr=1+4E

7、(t)dt，这个方程微分两次可以变成普021x2通二阶微分方程，此处不加求解。6.有向图中删点期望（HDU5036）问题：给定一个定向图，每次操作随机在图内取一个顶点，然后删除这个点和所有这个点能到达的点。问期望的操作次数是多少。解：考虑每一个点可以被它的所有直接的和间接的父亲删除（有环也无所谓）。假设这些点一共有k个，那么这个点直接被删的概率就是1/k，因此只要将原图反向之后求出可达矩阵，然后判断每个点的可达点有多少个，取倒数相加即可。7.连通图的概率（POJ3557）问题：先确定顶点的个数N和一个概率p，然后遍历所有的点对