文档介绍：第7章概率算法
1
理解产生伪随机数的算法
掌握数值概率算法的设计思想
掌握舍伍德算法的设计思想
掌握拉斯维加斯算法的设计思想
掌握蒙特卡罗算法的设计思想
学习要点
2
概率算法的特点
当算法执行过程中面临选择时,概率算法通常比最优选择算法省时。
对所求问题的同一实例用同一概率算法求解两次,两次求解所需的时间甚至所得的结果可能有相当大的差别。
设计思想简单,易于实现。
3
概率算法的分类
数值概率算法
A
蒙特卡罗算法
B
舍伍德算法
D
拉斯维加斯算法
C
4
随机数
随机数在概率算法设计中扮演着十分重要的角色。
在现实计算机上无法产生真正的随机数,因此在概率算法中使用的随机数都是一定程度上随机的,即伪随机数。
5
随机数
线性同余法是产生伪随机数的最常用的方法。由线性同余法产生的随机序列a0,a1,…,an满足:
其中b0,c0,dm。d称为该随机序列的种子。m应取充分大,因此可取m为机器大数,另外应取gcd(m,b)=1,因此可取b为一素数。
6
数值概率算法
7
计算值
设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分布,因而所投入的点落入圆内的概率为。
当n足够大时,k与n之比就逼近这一概率:
8
计算值
程序代码如下:
double Darts(int n)
{ // 用随机投点法计算值
static RandomNumber dart;
int k=0;
for (int i=1;i <=n;i++) {
double x=();
double y=();
if ((x*x+y*y)<=1) k++;
}
return 4*k/double(n);
}
9
计算定积分
设f(x)是[0,1]上的连续函数,且0f(x)1。
需要计算的积分为,积分I等于图中的绿色面积G。
10