学习要点理解产生伪随机数的算法掌握数值概率算法的设计思想掌握蒙特卡罗算法的设计思想掌握拉斯维加斯算法的设计思想掌握舍伍德算法的设计思想随机化算法随机数随机数用随机投点法计算值计算定积分解非线性方程组解非线性方程组舍伍德(Sherwood)算法舍伍德(Sherwood)算法舍伍德(Sherwood)算法舍伍德(Sherwood)算法舍伍德(Sherwood)算法:随机洗牌搜索有序表跳跃表跳跃表跳跃表跳跃表跳跃表注意到，在一个完全跳跃表中，具有i级指针的结点中有一半同时具有i+1级指针。为了维持跳跃表的平衡性，可以事先确定一个实数0<p<1，并要求在跳跃表中维持在具有i级指针的结点中同时具有i+1级指针的结点所占比例约为p。为此目的，在插入一个新结点时，先将其结点级别初始化为0，然后用随机数生成器反复地产生一个[0，1]间的随机实数q。如果q<p，则使新结点级别增加1，直至qp。由此产生新结点级别的过程可知，所产生的新结点的级别为0的概率为1-p(?)，级别为1的概率为p(1-p)，…，级别为i的概率为pi(1-p)。如此产生的新结点的级别有可能是一个很大的数，甚至远远超过表中元素的个数。为了避免这种情况，用作为新结点级别的上界。其中n是当前跳跃表中结点个数。当前跳跃表中任一结点的级别不超过当p=0.5时，刚好拉斯维加斯(LasVegas)算法n后问题while((k<=n)&&(count>0)){x[k]=i;if(Place(k))y[count++]=i;}if(count>0)x[k++]=y[rnd.Random(count)];stopVegas整数因子分解Pollard算法蒙特卡罗(MonteCarlo)算法蒙特卡罗(MonteCarlo)算法主元素问题素数测试素数测试素数测试：模n的大数幂乘的快速算法