理解产生伪随机数的算法掌握数值概率算法的设计思想掌握舍

《理解产生伪随机数的算法掌握数值概率算法的设计思想掌握舍》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章概率算法1理解产生伪随机数的算法掌握数值概率算法的设计思想掌握舍伍德算法的设计思想掌握拉斯维加斯算法的设计思想掌握蒙特卡罗算法的设计思想学习要点2概率算法的特点当算法执行过程中面临选择时，概率算法通常比最优选择算法省时。对所求问题的同一实例用同一概率算法求解两次，两次求解所需的时间甚至所得的结果可能有相当大的差别。设计思想简单，易于实现。3概率算法的分类数值概率算法A蒙特卡罗算法B舍伍德算法D拉斯维加斯算法C4随机数随机数在概率算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数，因此在概率算法中使用的随机数都是一定程度上随机的，即伪随机数。

2、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计算值程序代码如下：doubleDarts(intn){//用随机投点法计算值staticRandomNumb

3、erdart;intk=0;for(inti=1;i<=n;i++){doublex=dart.fRandom();doubley=dart.fRandom();if((x*x+y*y)<=1)k++;}return4*k/double(n);}9计算定积分设f(x)是[0，1]上的连续函数，且0f(x)1。需要计算的积分为,积分I等于图中的绿色面积G。10计算定积分在图所示单位正方形内均匀地作投点试验，则随机点落在曲线下面的概率为假设向单位正方形内随机地投入n个点(xi,yi)。如果有m个点落入G内，则随机点落入G内的概率11计算定积分程序代码如下：dou

4、bleDarts(intn){//用随机投点法计算定积分staticRandomNumberdart;intk=0;for(inti=1;i<=n;i++){doublex=dart.fRandom();doubley=dart.fRandom();if(y<=f(x))k++;}returnk/double(n);}12解非线性方程组求解下面的非线性方程组其中，x1,x2,…,xn是实变量，fi是未知量x1,x2,…,xn的非线性实函数。要求确定上述方程组在指定求根范围内的一组解13注：一般而言，概率算法费时，但设计思想简单，易实现。对于精度要求高的问题，可以

5、提供较好的初值。解非线性方程组线性化方法求函数极小值方法14解非线性方程组在求根区域D内，选定随机点x0作为随机搜索的出发点。按照预先选定的分布（正态分布、均匀分布等），逐个选取随机点xj，计算目标函数，满足精度要求的随机点就是近似解。在算法的搜索过程中，假设第j步随机搜索得到的随机搜索点为xj。在第j+1步，生成随机搜索方向和步长，计算出下一步的增量xj。从当前点xj依xj得到第j+1步的随机搜索点。当Φ(x)<时，取为所求非线性方程组的近似解。否则进行下一步新的随机搜索过程。15解非线性方程组While((min>epsilon)&&(j

6、){//计算随机搜索步长因子if(fxM)a/=k;success=false;}for(inti=1;i

7、=1;i<=n;i++)x[i]+=dx[i]];//计算目标函数值fx=f(x,n);}if(fx>tA(n)的可能性。19舍伍德(Sherwood)算法注：当s(n)与tA(n)相比可忽略时，舍伍德算法可获得很好的平均性能

8、。舍伍德算法设计的基本思