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

——信息学竞赛中概率问题求解初探 引言 算法设计中很多问题的解决都用到了概率分析 一个大家熟知的例子是，快速排序中通过随机选择划分点而使极端情况出现的概率大大减小 在信息学竞赛中，与概率有关的问题占据着相当的分量 在05，06，08年的NOI中都出现了与概率有关的试题 全文总览 要用到的定义 连续型随机变量的概率分布 设有随机变量X，称 F(x) =P(X≤x) 为X的概率分布函数，如果有非负可积函数 f(x) 使 成立，则称 f(x) 是X的概率密度函数 均匀分布 若随机变量 X 在[a,b]上等概率地取每个值，称 X 在[a,b]上均匀分布，由概率密度的定义知 SPOJ RNG 题意分析 方法一 (X1,X2 )的取值范围可看成平面直角坐标系的一个矩形 S =X1+X2≤b可以看成半平面 P(S≤b)就是它们的公共部分的面积与矩形的面积(R1×R2)的比值 方法一 与N=2的情况类似 (X1,X2,X3)的取值范围可看成空间直角坐标系的长方体 S=X1+X2+X3≤b可以看成半空间 P(S≤b)就是它们的公共部分的体积，与长方体的体积(R1×R2×R3)的比值 方法一 (X1,X2,…,XN)的取值范围就是N维空间中的一个区域，S ≤b是一个半N维空间，它们公共部分的体积与(R1×R2×…×RN)的比值就是P(S ≤b) 不妨记为 V([0, R1],[0, R2],…,[0, RN],b) 补集转化[0,Ri] = [0,+∞) – (Ri ,+∞) 方法一 以N=2为例 方法一 当Xi的取值范围为[0,+∞)或(Ri,+∞)时，怎样求V 当Xi的取值范围为(Ri,+ ∞)时，定义X’i=Xi-Ri 用X’i替换Xi,同时把b减去Ri,问题等价。 求V([0,+∞),…,[0,+∞),b) 方法一总结 方法二 当N=1时（先说明X） 方法二 当N=2时 方法二 方法二 N更大时 回顾N=1,N=2 时P(S ≤x)的求解过程，我们发现可以划分若干区间，使每个区间的 P(S ≤x)都可以表示成多项式 如何划分区间 以全体整数为划分点 推想 对任意的N,函数 P(S ≤x) 在任意相邻整数区间内都可表示成多项式 推想正确吗？ 证明思路 要证明P(S ≤x)在相邻整数区间能用多项式表示 只需证明S的概率密度函数在相邻整数区间能用多项式表示。 用归纳法，设 fi(x)为随机变量X1,X2,…,Xi的和(一个随机变量)的概率密度函数 证明思路 设i=N-1时结论成立,证明i=N时成立。 由于前(i-1)个数的和与Xi是互相独立的，有 本题总结 在解决本题的过程中，我们遇到了这样的困难：N个随机变量代表着N维空间，较为抽象 两个解法都从N较小的情况开始分析，发现规律 比较两种解法，第二种比第一种思考与编程复杂度都大一些 但是第二种解法可推广性强，在N个随机变量不为均匀分布时依然适用 随机变量均匀分布是能用第一种方法解题的根本原因 总结 通过对上面例题的分析，我们发现概率问题有如下特点  V([0,R1],[0,R2],…,[0,RN],x)的表示。 V([0,R1],[0,R2],…[0,RN],x) =V([0,+∞)-(R1,+∞),[0,+∞)-(R2,+∞),…, [0,+∞)-(R2,+∞),x) 设(1≤i≤N)，设集合为所有满足下标集合，那么 V([0,R1],[0,R2],[0,RN],x)= 该式与容斥原理的公式相近。 用归纳法，当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) = ■ 方法二的可推广性强。这是因为每个随机变量都是均匀分布这个条件对方法二中的证明来说可以减弱：只要每个随机变量的概率密度函数是多项式即可。而方法一中之所以能把概率看成N维体积的比值，其根本原因就是每个随机变量都是均匀分布的。 举个简单的例子：如果要求的是N个随机数的平方和小于等于b的概率，那么方法一将无能为力，而方法二只要简单套用即可。 两种方法都从分析简单情况着手，但第二种方法对题目数学本质把握更透彻，这使方法二在一定程度上成为解决连续型随机变量问题的一般性方法。 对