算法合集之信息学竞赛中概率问题求解初探.pptx

122走进概率的世界走进概率的世界 信息学竞赛中概率问题求解初探信息学竞赛中概率问题求解初探安徽省合肥一中安徽省合肥一中 梅诗珂梅诗珂222 引言引言u算法设计中很多问题的解决都用到了算法设计中很多问题的解决都用到了概率分析概率分析一个大家熟知的例子是，快速排序中通过随机一个大家熟知的例子是，快速排序中通过随机选择划分点而使极端情况出现的概率大大减小选择划分点而使极端情况出现的概率大大减小u在信息学竞赛中，与概率有关的问题在信息学竞赛中，与概率有关的问题占据着相当的分量占据着相当的分量在在05，06，08年的年的NOI中都出现了与概率有关中都出现了与概率有关的试题的试题322全文总览全文总览样本空间样本空间随机变量离散型随机变量连续型随机变量UVA RandomnessSRM 349 LastMarble SPOJ RNGSGU Random Shooting422要用到的定义要用到的定义u连续型随机变量的概率分布连续型随机变量的概率分布 设有随机变量设有随机变量X，称称 F(x)=P(Xx)为为X的概率分布函的概率分布函数，如果有非负可积函数数，如果有非负可积函数 f(x)使使 成立，则称成立，则称 f(x)是是X的概率密度函数的概率密度函数u均匀分布均匀分布若随机变量若随机变量 X 在在a,b上等概率地取每个值，称上等概率地取每个值，称 X 在在a,b上均匀分布，由概率密度的定义知上均匀分布，由概率密度的定义知 522SPOJ RNGu 题目大意题目大意有有N个随机数生成器，第个随机数生成器，第i个等概率地返回个等概率地返回0,Ri中中的一个实数的一个实数 (1 i N)问所有随机生成数的和小于等于问所有随机生成数的和小于等于b的概率是多少的概率是多少 u约束条件约束条件 N、Ri都是范围在都是范围在1到到10内的正整数内的正整数(1 i N)622题意分析题意分析u第第i i个随机数生成器返回的值是一个在个随机数生成器返回的值是一个在 0,R0,Ri i 中均匀分布的连续型随机变量中均匀分布的连续型随机变量不妨设为不妨设为X Xi i，显然这，显然这 N N 个随机变量是互相个随机变量是互相独立的独立的(1iN 1iN)它们的和，即它们的和，即X X1 1+X+X2 2+X+XN N，也是一个随机变，也是一个随机变量，不妨设为量，不妨设为S S 那么那么SbSb的概率就是我们要求的，记为的概率就是我们要求的，记为 P(S b)P(S b)722方法一方法一u(X X1 1,X,X2 2)的取值范围可看的取值范围可看成平面直角坐标系的一个成平面直角坐标系的一个矩形矩形uS=XS=X1 1+X+X2 2bb可以看成半可以看成半平面平面uP(Sb)P(Sb)就是它们的公共就是它们的公共部分的面积与矩形的面积部分的面积与矩形的面积(R(R1 1RR2 2)的比值的比值当当N=2时时（N=1略）略）822方法一方法一当当N=3时时u与与N=2N=2的情况类似的情况类似(X X1 1,X,X2 2,X,X3 3)的取值范围可看的取值范围可看成空间直角坐标系的长方体成空间直角坐标系的长方体S=XS=X1 1+X+X2 2+X+X3 3bb可以看成半空可以看成半空间间P(Sb)P(Sb)就是它们的公共部就是它们的公共部分的体积，与长方体的体积分的体积，与长方体的体积(R R1 1RR2 2RR3 3)的比值的比值922方法一方法一u(X1,X2,XN)的取值范围就是的取值范围就是N维空间中的一维空间中的一个区域，个区域，S b是一个半是一个半N维空间，它们公共部维空间，它们公共部分的体积与分的体积与(R1R2RN)的比值就是的比值就是P(S b)不妨记为不妨记为 V(0,R1,0,R2,0,RN,b)补集转化补集转化0,Ri=0,+)(Ri,+)当当N为任意值时为任意值时1022方法一方法一u以以N=2为例为例V(0,R1,0,R2,b)=V(0,+),0,+),b)-V(0,+),(R2,+),b)-V(R1,+),0,+),b)1122方法一方法一u当当X Xi i的取值范围为的取值范围为 0,+0,+)或或(R Ri i,+,+)时，怎样求时，怎样求V Vu当当X Xi i的取值范围为的取值范围为(R Ri i,+,+)时，定义时，定义X Xi i=X=Xi i-R-Ri iu用用X Xi i替换替换X Xi i,同时把同时把b b减去减去R Ri i,问题等价。问题等价。u求求V(V(0,+0,+),),0,+0,+),),b b)N=1N=1时时 V(V(0,+0,+),),b b)=)=b bN=2N=2时时 V(0,+),(V(0,+),(0,+0,+),),b b)=)=b b2 2/2/2N=3N=3时时 V(V(0,+0,+),(),(0,+0,+),(0,+),),(0,+),b b)=)=b b3 3/6/6V(V(0,+0,+),),0,+0,+),),b b)=)=b bN N/N!/N!1222方法一总结方法一总结从从N=2N=2、3 3开始分析开始分析求区域体积求区域体积有限区间无限区间问题解决问题解决补集转化1322方法二方法二u当当N=1N=1时（先说明时（先说明X X）1422方法二方法二u当当N=2时时(R2xR1)（2）(R1xR1+R2)（3）(0 xR2)（1）(R1+R2R1)当当i=1i=1时时1922证明思路证明思路u设设i=N-1时结论成立时结论成立,证明证明i=N时成立。时成立。u由于前由于前(i-1)个数的和与个数的和与Xi是互相独立的，有是互相独立的，有 j-Ri j-Ri+1 j j+1 t j j+1 xPPj-Ri+1,jj,xx-Ri,j-Ri+12022本题总结本题总结u在解决本题的过程中，我们遇到了这样的困难：在解决本题的过程中，我们遇到了这样的困难：N个随机变量代表着个随机变量代表着N维空间，较为抽象维空间，较为抽象u两个解法都从两个解法都从N较小的情况开始分析，发现规律较小的情况开始分析，发现规律比较两种解法，第二种比第一种思考与编程复杂度都比较两种解法，第二种比第一种思考与编程复杂度都大一些大一些但是第二种解法可推广性强，在但是第二种解法可推广性强，在N N个随机变量不为均匀个随机变量不为均匀分布时依然适用分布时依然适用随机变量均匀分布是能用第一种方法解题的根本原因随机变量均匀分布是能用第一种方法解题的根本原因2122总结总结u通过对上面例题的分析，我们发现概率问通过对上面例题的分析，我们发现概率问题有如下特点题有如下特点数学性强数学性强问题抽象，复杂问题抽象，复杂紧扣数学定义，牢牢紧扣数学定义，牢牢把握问题的本质把握问题的本质从特殊情况，简单从特殊情况，简单情况入手情况入手2222谢谢大家谢谢大家欢迎提问欢迎提问2322V(0,R1,0,R2,0,RN,x)的表示。uV(0,R1,0,R2,0,RN,x)=V(0,+)-(R1,+),0,+)-(R2,+),0,+)-(R2,+),x)u设设(1iN)，设集合为所有满足下标集合，设集合为所有满足下标集合，那么那么V(0,R1,0,R2,0,RN,x)=u该式与容斥原理的公式相近。该式与容斥原理的公式相近。2422u用归纳法，当用归纳法，当N=1时，时，V(0,+),x)=x显然显然符合结论。符合结论。u 设当设当N=2,3,k-1时都有结论成立，那么时都有结论成立，那么N=k时，时，V(0,+),0,+),0,+),x)就就是一个是一个k维锥体的维锥体的k维体积，椎体的底面面维体积，椎体的底面面积是积是u同时我们知道体积就是截面面积的积分值，同时我们知道体积就是截面面积的积分值，而对与锥体的顶点距离为而对与锥体的顶点距离为h的截面而言，其的截面而言，其截面面积截面面积 为为,所以所以uV(0,+),0,+),0,+),x)=2522u方法二的可推广性强。这是因为每个随机变量都是方法二的可推广性强。这是因为每个随机变量都是均匀分布这个条件对方法二中的证明来说可以减弱：均匀分布这个条件对方法二中的证明来说可以减弱：只要每个随机变量的概率密度函数是多项式即可。只要每个随机变量的概率密度函数是多项式即可。而方法一中之所以能把概率看成而方法一中之所以能把概率看成N维体积的比值，维体积的比值，其根本原因就是每个随机变量都是均匀分布的。其根本原因就是每个随机变量都是均匀分布的。u举个简单的例子：如果要求的是举个简单的例子：如果要求的是N个随机数的平方个随机数的平方和小于等于和小于等于b的概率，那么方法一将无能为力，而的概率，那么方法一将无能为力，而方法二只要简单套用即可。方法二只要简单套用即可。u两种方法都从分析简单情况着手，但第二种方法对两种方法都从分析简单情况着手，但第二种方法对题目数学本质把握更透彻，这使方法二在一定程度题目数学本质把握更透彻，这使方法二在一定程度上成为解决连续型随机变量问题的一般性方法。上成为解决连续型随机变量问题的一般性方法。2622对对 的解释的解释一般的积分式的积分区间是一个有限闭区间，但是一些情况下它不能一般的积分式的积分区间是一个有限闭区间，但是一些情况下它不能满足需要，于是有了无穷积分，也即积分区间为无穷区间的积分。满足需要，于是有了无穷积分，也即积分区间为无穷区间的积分。如果可积函数如果可积函数f(t)在在(-,b)上都有定义，并且如果极限上都有定义，并且如果极限 存在并有限，则把该极限记为存在并有限，则把该极限记为