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