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

891-理解产生伪随机数的算法掌握数值概率算法的设计思想掌握舍伍德算
理解产生伪随机数的算法掌握数值概率算法的设计思想掌握舍伍德算法的设计思想掌握拉斯维加斯算法的设计思想掌握蒙特卡罗算法的设计思想概率算法的特点概率算法的分类随机数随机数数值概率算法线性化方法求函数极小值方法舍伍德算法 bool Prime(unsigned int n) {// 素数测试的蒙特卡罗算法 RandomNumber rnd; unsigned int a, result; posite=false; a=(n-3)+2; power(a,n-1,n,posite); if (composite||(result!=1)) return false; else return true; } 拉斯维加斯( Las Vegas )算法拉斯维加斯算法的一个显著特征是它所作的随机性决策有可能导致算法找不到所需的解。 void obstinate(Object x, Object y) {// 反复调用拉斯维加斯算法LV(x,y),直到找到问题的一个解y bool ess= false; while (!ess) ess=lv(x,y); } 拉斯维加斯( Las Vegas )算法设p(x)是对输入x调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算法应该对所有输入x均有p(x) 0。设t(x)是算法obstinate找到具体实例x的一个解所需的平均时间,s(x)和e(x)分别是算法对于具体实例x求解成功或求解失败所需的平均时间,则有: 。解此方程可得: n后问题对于n后问题的任何一个解而言,每一个皇后在棋盘上的位置无任何规律,不具有系统性,而更象是随机放置的。由此容易想到拉斯维加斯算法。如果将上述随机放置策略与回溯法相结合,可能会获得更好的效果。 n后问题可以先在棋盘的若干行中随机地放置皇后,然后在后继行中用回溯法继续放置,直至找到一个解或宣告失败。随机放置的皇后越多,后继回溯搜索所需的时间就越少,但失败的概率也就越大。 12 5 -- 0 t e s p stopVegas 给定一个合数n,求n的一个非平凡因子的问题称为整数n的因子分割问题。整数因子分解设n 1是一个整数。关于整数n的因子分解问题是找出n的如下形式的唯一分解式: 。其中,p1 p2 … pk是k个素数,m1,m2,…,mk是k个正整数。如果n是一个合数,则n必有一个非平凡因子x,1 x n,使得x可以整除n。整数因子分解 int Split(int n) { int m = floor(sqrt(double(n))); for (int i=2; i =m; i++) if (n%i==0) return i; return 1; } 事实上,算法split(n)是对范围在1~x的所有整数进行了试除而得到范围在1~x2的任一整数的因子分割。 Pollard算法在开始时选取0~n-1范围内的随机数,然后递归地由产生无穷序列对于i=2k,以及2k j?2k+1,算法计算出xj-xi与n的最大公因子d=gcd(xj-xi,n)。如果d是