1、第 7章 概率算法1 学习要点 理解产生伪随机数的算法 掌握数值概率算法的设计思想 掌握蒙特卡罗算法的设计思想 掌握拉斯维加斯算法的设计思想 掌握舍伍德算法的设计思想2随机数随机数在概率算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数，因此在概率算法中使用的随机数都是一定程度上随机的，即伪随机数。线性同余法 是产生伪随机数的最常用的方法。由线性同余法产生的随机序列 a0,a1,a n满足其中 b0， c0， dm。 d称为该随机序列的种子。如何选取该方法中的常数 b、 c和 m直接关系到所产生的随机序列的随机性能。这是随机性理论研究的内容，已超出本书讨论的范围。从直观上看，
2、m应取得充分大，因此可取 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 Rando
3、mNumber rnd;for (int i=0;in;i+) int j=rnd.Random(n-i)+i;Swap(ai, aj); 9跳跃表舍伍德型算法的设计思想还可用于设计高效的数据结构。如果用有序链表来表示一个含有 n个元素的有序集 S，则在最坏情况下，搜索 S中一个元素需要 (n)计算时间。提高有序链表效率的一个技巧是在有序链表的部分结点处增设附加指针以提高其搜索性能。在增设附加指针的有序链表中搜索一个元素时，可借助于附加指针跳过链表中若干结点，加快搜索速度。这种增加了向前附加指针的有序链表称为 跳跃表 。应在跳跃表的哪些结点增加附加指针以及在该结点处应增加多少指针完全采用随机化方法来确定。这使得跳跃表可在 O(logn)平均时间内支持关于有序集的搜索、插入和删除等运算。 10
