怎样写描写初春的作文呢

1、1苍穹龙骑 http:/2理解产生伪随机数的算法理解产生伪随机数的算法掌握数值概率算法的设计思想掌握数值概率算法的设计思想掌握舍伍德算法的设计思想掌握舍伍德算法的设计思想掌握拉斯维加斯算法的设计思想掌握拉斯维加斯算法的设计思想掌握蒙特卡罗算法的设计思想掌握蒙特卡罗算法的设计思想学习要点3概率算法的特点1. 当算法执行过程中面临选择时，概率算法通当算法执行过程中面临选择时，概率算法通常比最优选择算法省时。常比最优选择算法省时。2. 对所求问题的同一实例用同一概率算法求解对所求问题的同一实例用同一概率算法求解两次，两次求解所需的时间甚至所得的结果两次，两次求解所需的时间甚至所得的结果可能有相当大的

2、差别。可能有相当大的差别。3. 设计思想简单，易于实现。设计思想简单，易于实现。4概率算法的分类数值概率算数值概率算法法A A蒙特卡罗算法蒙特卡罗算法B B舍伍德算法舍伍德算法D D 拉斯维加斯算法拉斯维加斯算法C C5随机数随机数在概率算法设计中扮演着十分重要的随机数在概率算法设计中扮演着十分重要的角色。角色。在现实计算机上无法产生真正的随机数，因在现实计算机上无法产生真正的随机数，因此在概率算法中使用的随机数都是一定程度上随此在概率算法中使用的随机数都是一定程度上随机的，即机的，即伪随机数伪随机数。6随机数线性同余法线性同余法是产生伪随机数的最常用的方法。由是产生伪随机数的最常用的方法。由

3、线性同余法产生的随机序列线性同余法产生的随机序列a0,a1,an满足满足:, 2 , 1mod)(10nmcbaadann其中其中b 0，c 0，d m。d称为该随机序列的种子。称为该随机序列的种子。m应取充分大，因此可取应取充分大，因此可取m为机器大数，另外应为机器大数，另外应取取gcd(m,b)=1，因此可取，因此可取b为一素数。为一素数。7数值概率算法 8计算值 设有一半径为设有一半径为r的圆及其外切四边形。向该正方形随的圆及其外切四边形。向该正方形随机地投掷机地投掷n个点。设落入圆内的点数为个点。设落入圆内的点数为k。由于所投入的。由于所投入的点在正方形上均匀分布，因而所投入的点落入圆

4、内的概率点在正方形上均匀分布，因而所投入的点落入圆内的概率为为 。 当当n足够大时，足够大时，k与与n之比就逼近这一概率：之比就逼近这一概率：2244rrnk49计算值 程序代码如下：程序代码如下：double Darts(int n) / 用随机投点法计算用随机投点法计算 值值 static RandomNumber dart; int k=0; for (int i=1;i =n;i+) double x=dart.fRandom(); double y=dart.fRandom(); if (x*x+y*y)=1) k+; return 4*k/double(n);10计算定积分设设f(

5、x)是是0，1上的连续函数，且上的连续函数，且0 f(x) 1。需要计算的积分为需要计算的积分为 ,积分积分I等于图中的等于图中的绿绿色面积色面积G。10)(dxxfI11计算定积分在图所示单位正方形内均匀地作投点试验，则在图所示单位正方形内均匀地作投点试验，则随机点落在曲线下面的概率为随机点落在曲线下面的概率为 假设向单位正方形内随机地投入假设向单位正方形内随机地投入n个点个点(xi,yi)。如果有。如果有m个点落入个点落入G内，则随机点落入内，则随机点落入G内的概率内的概率 10)(010)()(xfrdxxfdydxxfyPnmI12计算定积分 程序代码如下：程序代码如下：double

6、Darts(int n) / 用随机投点法计算用随机投点法计算定积分定积分 static RandomNumber dart; int k=0; for (int i=1;i =n;i+) double x=dart.fRandom(); double y=dart.fRandom(); if (y=f(x) k+; return k/double(n);13解非线性方程组求解下面的非线性方程组求解下面的非线性方程组0),(0),(0),(21212211nnnnxxxfxxxfxxxf其中，其中，x1,x2,xn是实变量，是实变量，fi是未知量是未知量x1,x2,xn的非线性实函数。要求确定

7、上述方程组在指定求的非线性实函数。要求确定上述方程组在指定求根范围内的一组解根范围内的一组解*2*1,nxxx14注：一般而言，概率算法费时，但设计思注：一般而言，概率算法费时，但设计思想简单，易实现。对于精度要求高的问题，想简单，易实现。对于精度要求高的问题，可以提供较好的初值。可以提供较好的初值。解非线性方程组 n线性化方法线性化方法n求函数极小值方法求函数极小值方法2( )( )ixfx15解非线性方程组 在求根区域在求根区域D内，选定随机点内，选定随机点x0作为随机搜索的出发点。作为随机搜索的出发点。1. 按照预先选定的分布（正态分布、均匀分布等），逐个按照预先选定的分布（正态分布、均

8、匀分布等），逐个选取随机点选取随机点xj，计算目标函数，满足精度要求的随机点就，计算目标函数，满足精度要求的随机点就是近似解。是近似解。2. 在算法的搜索过程中，假设第在算法的搜索过程中，假设第j步随机搜索得到的随机搜步随机搜索得到的随机搜索点为索点为xj。在第。在第j+1步，生成随机搜索方向和步长，计算步，生成随机搜索方向和步长，计算出下一步的增量出下一步的增量 xj。从当前点。从当前点xj依依 xj得到第得到第j+1步的随机步的随机搜索点。当搜索点。当( (x) ) epsilon)&(j Steps) /计算随机搜索步长因子计算随机搜索步长因子 if (fx M) a/= k;succe

9、ss = false; for (int i = 1; i n; i+) /计算随机搜索方向和增量计算随机搜索方向和增量 ri = 2.0 * rnd.fRandom() 1; if (success) for(int i=1; i = n; i+) dxi = a * ri; else for(int i=1; i = n; i+) dxi = a * ri;17解非线性方程组/计算下一个搜索点计算下一个搜索点 for(int i=1; i = n; i+) xi += dxi; /计算目标函数值计算目标函数值 fx = f(x,n); if (fx tA(n) 的可能性。的可能性。20舍伍

10、德(Sherwood)算法注：当注：当s(n)与与tA(n)相比可忽略时，舍伍德算相比可忽略时，舍伍德算法可获得很好的平均性能法可获得很好的平均性能。舍伍德算法设计的基本思想舍伍德算法设计的基本思想 希望获得一个概率算法希望获得一个概率算法B B，用该算法，用该算法处理问题的输入，使得对问题的输入规模处理问题的输入，使得对问题的输入规模为为n n的每一个实例均有的每一个实例均有)()()(nsntxtAB21舍伍德(Sherwood)算法 这两种算法的核心都在于选择合适的划分这两种算法的核心都在于选择合适的划分基准。舍伍德算法随机地选择一个数组元素作基准。舍伍德算法随机地选择一个数组元素作为划

11、分基准。为划分基准。线性时间选择算法线性时间选择算法 No.1快速排序算法快速排序算法 No.222舍伍德(Sherwood)算法如果所给的确定性算法无法直接改造成舍伍如果所给的确定性算法无法直接改造成舍伍德型算法。此时可借助于随机预处理技术，不改变德型算法。此时可借助于随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌，同原有的确定性算法，仅对其输入进行随机洗牌，同样可收到舍伍德算法的效果。样可收到舍伍德算法的效果。 如，对于确定性选择算法，可以用下面的洗牌如，对于确定性选择算法，可以用下面的洗牌算法算法shuffle将数组将数组a中元素随机排列，然后用确定中元素随机排列，然后用

12、确定性选择算法求解。这样做所收到的效果与舍伍德型性选择算法求解。这样做所收到的效果与舍伍德型算法的效果是一样的。算法的效果是一样的。 23舍伍德(Sherwood)算法Shuffle函数的代码：函数的代码：templatevoid Shuffle(Type a, int n)/ 随机洗牌算法随机洗牌算法 static RandomNumber rnd; for (int i=0;i0。设。设t(x)是算法是算法obstinate找找到具体实例到具体实例x的一个解所需的平均时间的一个解所需的平均时间 ,s(x)和和e(x)分分别是算法对于具体实例别是算法对于具体实例x求解成功或求解失败所需的求解

13、成功或求解失败所需的平均时间，则有：平均时间，则有： 。 解此方程可得：解此方程可得： )()()(1 ()()()(xtxexpxsxpxt)()()(1)()(xexpxpxsxt32n后问题对于对于n后问题的任何一个解而言，每一个后问题的任何一个解而言，每一个皇后在棋盘上的位置无任何规律，不具有系统皇后在棋盘上的位置无任何规律，不具有系统性，而更象是随机放置的。由此容易想到性，而更象是随机放置的。由此容易想到拉斯拉斯维加斯算法维加斯算法。如果将上述随机放置策略与回溯法相如果将上述随机放置策略与回溯法相结合，可能会获得更好的效果结合，可能会获得更好的效果。33n后问题可以先在棋盘的若干行中

14、随机地放置皇后，可以先在棋盘的若干行中随机地放置皇后，然后在后继行中用回溯法继续放置，直至找到一个然后在后继行中用回溯法继续放置，直至找到一个解或宣告失败。随机放置的皇后越多，后继回溯搜解或宣告失败。随机放置的皇后越多，后继回溯搜索所需的时间就越少，但失败的概率也就越大。索所需的时间就越少，但失败的概率也就越大。 stopVegaspset01.0000262.00-262.0050.503933.8847.2380.39120.046513.0010.20222.1134 给定一个合数给定一个合数n n，求，求n n的一个非平凡因子的问题称为整的一个非平凡因子的问题称为整数数n n的因子分割

15、问题。的因子分割问题。整数因子分解设设n1是一个整数。关于整数是一个整数。关于整数n的因子分解问题是的因子分解问题是找出找出n的如下形式的唯一分解式：的如下形式的唯一分解式： 。 其中，其中，p1p2pk是是k个素数，个素数，m1,m2,mk是是k个个正整数。如果正整数。如果n是一个合数，则是一个合数，则n必有一个非平凡必有一个非平凡因子因子x，1xn，使得，使得x可以整除可以整除n。 kmkmmpppn212135整数因子分解int Split(int n) int m = floor(sqrt(double(n); for (int i=2; i=m; i+) if (n%i=0) ret

16、urn i; return 1; 事实上，算法事实上，算法split(n)split(n)是对范围是对范围在在1 1x x的所有整数的所有整数进行了试除而得到进行了试除而得到范围在范围在1 1x x2 2的任一的任一整数的因子分割。整数的因子分割。 36Pollard算法 在开始时选取在开始时选取0n-1范围内的随机数，然后范围内的随机数，然后递归地由递归地由 产生无穷序列产生无穷序列 对于对于i=2k，以及，以及2k1) & (dn) coutdendl; if (i=k) y=x; k*=2; 对对Pollard算法更深入的算法更深入的分析可知，执行算法的分析可知，执行算法的while循环

17、约循环约 次后，次后，Pollard算法会输出算法会输出n的的一个因子一个因子p。由于。由于n的最的最小 素 因 子小 素 因 子 p ， 故， 故Pollard算法可在算法可在O(n1/4)时间内找到时间内找到n的一个素因的一个素因子。子。np38蒙特卡罗(Monte Carlo)算法设设p是一个实数，且是一个实数，且1/2pn/2时，称元素x是数组T的主元素。 templatebool Majority(Type *T, int n)/ 判定主元素的蒙特卡罗算法 int i=rnd.Random(n)+1; Type x=Ti; / 随机选择数组元素 int k=0; for (int j

18、=1;jn/2); / kn/2 时T含有主元素templatebool MajorityMC(Type *T, int n, double e)/ 重复调用算法Majority int k=ceil(log(1/e)/log(2); for (int i=1;i0，算法majorityMC重复调用log(1/) 次算法majority。它是一个偏真蒙特卡罗算法，且其错误概率小于。算法majorityMC所需的计算时间显然是O(nlog(1/ )。44素数测试：对于给定的正整数n，判定n是一个素数的充要条件是(n-1)! -1(mod n)。void power( unsigned int a, unsigned int p, unsigned int