《算法设计与分析第7章》由会员分享，可在线阅读，更多相关《算法设计与分析第7章（22页珍藏版）》请在金锄头文库上搜索。
1、第7章 随机化算法1学习要点理解产生伪随机数的算法掌握数值随机化算法的设计思想 掌握蒙特卡罗算法的设计思想掌握拉斯维加斯算法的设计思想掌握舍伍德算法的设计思想2随机数随机数在随机化算法设计中扮演着十分重要的角色。在现实计算 机上无法产生真正的随机数，因此在随机化算法中使用的随机数 都是一定程度上随机的，即伪随机数。 线性同余法是产生伪随机数的最常用的方法。由线性同余法产生 的随机序列a0,a1,an满足其中b0，c0，dm。d称为该随机序列的种子。如何选取该 方法中的常数b、c和m直接关系到所产生的随机序列的随机性 能。这是随机性理论研究的内容，已超出本书讨论的范围。从 直观上看，m应取得充分
2、大，因此可取m为机器大数，另外应 取gcd(m,b)=1，因此可取b为一素数。3数值随机化算法 4用随机投点法计算值 设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个 点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分 布，因而所投入的点落入圆内的概率为 。所以当n足够大时，k与n之比就逼近这一概率。从而double Darts(int n) / 用随机投点法计算值static RandomNumber dart;int k=0;for (int i=1;i void Shuffle(Type a, int n) / 随机洗牌算法static RandomNumber rnd;
3、for (int i=0;i0。 设t(x)是算法obstinate找到具体实例x的一个解所需的平均时间 ,s(x)和e(x)分别是算法对于具体实例x求解成功或求解失败所需 的平均时间，则有： 解此方程可得： 14n后问题对于n后问题的任何一个解而言，每一个皇后在棋盘上的位置无 任何规律，不具有系统性，而更象是随机放置的。由此容易想到 下面的拉斯维加斯算法。 在棋盘上相继的各行中随机地放置皇后，并注意使新放置的皇后 与已放置的皇后互不攻击，直至n个皇后均已相容地放置好，或 已没有下一个皇后的可放置位置时为止。如果将上述随机放置策略与回溯法相结合，可能会获得更好的 效果。可以先在棋盘的若干行中随
4、机地放置皇后，然后在后继 行中用回溯法继续放置，直至找到一个解或宣告失败。随机放 置的皇后越多，后继回溯搜索所需的时间就越少，但失败的概 率也就越大。 stopVegaspset 01.0000262.00-262.00 50.503933.8847.2380.39 120.046513.0010.20222.1115整数因子分解设n1是一个整数。关于整数n的因子分解问题是找出n的如下形 式的唯一分解式： 其中，p11) Type x=Ti; / 随机选择数组元素int k=0;for (int j=1;jn/2); / kn/2 时T含有主元素 template bool MajorityM
5、C(Type *T, int n, double e) / 重复调用算法Majorityint k=ceil(log(1/e)/log(2);for (int i=1;i0，算法 majorityMC重复调用log(1/) 次 算法majority。它是一个偏真蒙特 卡罗算法，且其错误概率小于。算 法majorityMC所需的计算时间显然 是O(nlog(1/ )。20素数测试WilsonWilson定理定理：对于给定的正整数n，判定n是一个素数的充要条件 是(n-1)! -1(mod n)。 费尔马小定理费尔马小定理：如果p是一个素数，且0ap，则ap-1(mod p)。 二次探测定理二次探
6、测定理：如果p是一个素数，且0xp，则方程x21(mod p) 的解为x=1，p-1。void power( unsigned int a, unsigned int p, unsigned int n, unsigned int if (p=0) result=1;else power(a,p/2,n,x,composite); / 递归计算result=(x*x)%n; / 二次探测if (result=1)if (p%2)=1) / p是奇数result=(result*a)%n; bool Prime(unsigned int n) / 素数测试的蒙特卡罗算法RandomNumber rnd;unsigned int a, result;bool composite=false;a=rnd.Random(n-3)+2;power(a,n-1,n,result,composite);if (composite|(result!=1) return false;else return true; 算法prime是一个偏假3/4正确的蒙 特卡罗算法。通过多次重复调用错 误概率不超过(1/4)k。这是一个很保 守的估计，实际使用的效果要好得 多。2122
