计算机算法设计与分析(第4版)第7章

1、第1，7章随机化算法，第2，了解生成学习点伪随机数的算法掌握数字随机化算法的设计思路掌握拉斯维加斯算法的设计思路掌握Sherwood算法的设计思路3，随机数，随机数在随机化算法设计中发挥着非常重要的作用。实际计算机不能生成实际随机数，所以随机化算法中使用的随机数都是某种程度上的随机，即伪随机数。线性同余法是生成伪随机数最常用的方法。线性联合方法生成的随机序列a0，a1，an满足，其中B0，c0，DM。d被称为这个随机序列的种子。在此方法中，选择常量b、c和m的方法与生成的随机序列的随机性能直接相关。这是随机性论研究的内容，超出了本书讨论的范围。直观地说，m必须足够大，因此所需的m是大量机器，需

2、要使用gcd(m，b)=1，因此所需的b是一个小数。4，数值随机化算法，5，使用随机点方法计算值，半径为r的圆和外切四边形。在这个正方形中随机扔n个点。进入圆内的点是k。投入的点均匀分布在正方形上，因此投入的点进入圆内的概率。因此，当n足够大时，k与n的比率近似于这个概率。使用double Darts(int n)/static random number 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

3、4 * k/double(n)；6，计算有限整数，f(x)为0，1的连续函数，设定0f(x)1。需要计算的积分是。积分I等于图形的面积g。假设在图中所示的单位矩形内均匀地试验点，则随机点落在曲线下的概率是在单位矩形内随机输入n点(xi，yi)。如果m个点在g内，随机点求解g内的概率，7，非线性方程，求解下面的非线性方程。其中x1，x2，xn是实际变量，fi是未知量x1，x2，xn的非线性实际函数。必须选择指定布线区域d内的随机点x0，然后确定指定布线范围内上述表达式的解。假设在算法的搜索过程中，在j阶段随机搜索中获得的随机搜索点为XJ。在步骤J 1中，计算下一步中的随机搜索增量XJ。取得目前点

4、XJ基准XJ第1阶段的随机搜寻点。取x中所需非线性方程的近似解。否则，下一步将执行新的随机搜索过程。8，设定为Sherwood演算法的a是决定演算法，以tA(x)记录输入例证为x时所需的计算时间。如果将Xn设置为算法a的输入大小为n的实例的全部，则当问题的输入大小为n时，算法a所需的平均时间不能排除存在xXn的可能性。我们想得到随机算法b，即问题的输入大小为n的每个实例是shewood算法设计的基本思路。Schwood算法在s(n)相对于tA(n)可忽略时具有良好的平均性能。9，Sherwood算法，复习学过的Sherwood算法：(1)线性时间选择算法(2)快速排序算法有时也不能将给定确定性算法直接转换为基于shewood的算法。此时，利用仅执行随机置乱而不改变原始确定性算法的随机预处理技术，可以达到舍伍德算法的效果。例如，对于确定性选择算法，可以使用下面的洗牌算法shuffle随机排列数组a的元素，然后用确定性选择算法解决。这样做得到的效果与舍伍德型算法的效果相同。template