1
第 7章 概率算法
2
随机数随机数在概率算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数，因此在概率算法中使用的随机数都是一定程度上随机的，即伪随机数。
线性同余法 是产生伪随机数的最常用的方法。由线性同余法产生的随机序列 a0,a1,…,a n满足
,2,1m o d)( 1
0
nmcbaa
da
nn
其中 b?0,c?0,d?m。 d称为该随机序列的种子。如何选取该方法中的常数 b,c和 m直接关系到所产生的随机序列的随机性能。这是随机性理论研究的内容，已超出本书讨论的范围。从直观上看,m应取得充分大，因此可取 m为机器大数，另外应取 gcd(m,b)=1，因此可取 b为一素数。
3
数值概率算法
4
用随机投点法计算?值设有一半径为 r的圆及其外切四边形。向该正方形随机地投掷 n个点。设落入圆内的点数为 k。由于所投入的点在正方形上均匀分布，因而所投入的点落入圆内的概率为 。所以当 n足够大时,k与 n之比就逼近这一概率。从而 。
44 2
2
r
r
n
k4
public static double darts(int n)
{ // 用随机投点法计算?值
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 4*k/(double)n;
}
5
计算定积分设 f(x)是 [0,1]上的连续函数，且 0?f(x)?1。
需要计算的积分为,积分 I等于图中的面积 G。
1
0
)( dxxfI
在图所示单位正方形内均匀地作投点试验，则随机点落在曲线下面的概率为假设向单位正方形内随机地投入 n个点 (xi,yi)。如果有 m个点落入
G内，则随机点落入 G内的概率
1
0
)(
0
1
0
)()}({
xf
r dxxfd y d xxfyP
n
m?I
6
解非线性方程组求解下面的非线性方程组
0),,,(
0),,,(
0),,,(
21
212
211
nn
n
n
xxxf
xxxf
xxxf
其中,x1,x2,…,x n是实变量,fi是未知量 x1,x2,…,x n的非线性实函数。要求确定上述方程组在指定求根范围内的一组解 **2*1,,,nxxx?
在指定求根区域 D内，选定一个随机点 x0作为随机搜索的出发点。在算法的搜索过程中，假设第 j步随机搜索得到的随机搜索点为 xj。在第 j+1步，计算出下一步的随机搜索增量?xj。从当前点 xj依?xj得到第 j+1步的随机搜索点。当 x<?时，取为所求非线性方程组的近似解。否则进行下一步新的随机搜索过程。
7
舍伍德 (Sherwood)算法设 A是一个确定性算法，当它的输入实例为 x时所需的计算时间记为 tA(x)。设 Xn是算法 A的输入规模为 n的实例的全体，则当问题的输入规模为 n时，算法 A所需的平均时间为
nXx
nAA Xxtnt ||/)()(
这显然不能排除存在 x∈ Xn使得 的可能性。希望获得一个概率算法 B，使得对问题的输入规模为 n的每一个实例均有这就是舍伍德算法设计的基本思想。当 s(n)与 tA(n)相比可忽略时，
舍伍德算法可获得很好的平均性能。
)()( ntxt AA
)()()( nsntxt AB
8
舍伍德 (Sherwood)算法复习学过的 Sherwood算法：
（ 1）线性时间选择算法
（ 2）快速排序算法有时也会遇到这样的情况，即所给的确定性算法无法直接改造成舍伍德型算法。此时可借助于随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌，同样可收到舍伍德算法的效果。例如，对于确定性选择算法，可以用下面的洗牌算法 shuffle将数组 a中元素随机排列，然后用确定性选择算法求解。这样做所收到的效果与舍伍德型算法的效果是一样的。
public static void shuffle(Comparable []a,int n)
{// 随机洗牌算法
rnd = new Random();
for (int i=1;i<n;i++) {
int j=rnd.random(n-i+1)+i;
MyMath.swap(a,i,j);
}
}
9
跳跃表
舍伍德型算法的设计思想还可用于设计高效的数据结构。
如果用有序链表来表示一个含有 n个元素的有序集 S，则在最坏情况下，搜索 S中一个元素需要?(n)计算时间。
提高有序链表效率的一个技巧是在有序链表的部分结点处增设附加指针以提高其搜索性能。在增设附加指针的有序链表中搜索一个元素时，可借助于附加指针跳过链表中若干结点，加快搜索速度。这种增加了向前附加指针的有序链表称为 跳跃表 。
应在跳跃表的哪些结点增加附加指针以及在该结点处应增加多少指针完全采用随机化方法来确定。这使得跳跃表可在 O(logn)
平均时间内支持关于有序集的搜索、插入和删除等运算。
10
跳跃表在一般情况下，给定一个含有 n个元素的有序链表，可以将它改造成一个完全跳跃表，使得每一个 k级结点含有 k+1个指针，分别跳过 2k-1,2k-1-1,…,20-1个中间结点。第 i个 k级结点安排在跳跃表的位臵 i2k处,i?0。这样就可以在时间 O(logn)内完成集合成员的搜索运算。在一个完全跳跃表中，最高级的结点是?logn?
级结点。
完全跳跃表与完全二叉搜索树的情形非常类似。它虽然可以有效地支持成员搜索运算，但不适应于集合动态变化的情况。集合元素的插入和删除运算会破坏完全跳跃表原有的平衡状态，
影响后继元素搜索的效率。
11
跳跃表为了在动态变化中维持跳跃表中附加指针的平衡性，必须使跳跃表中 k级结点数维持在总结点数的一定比例范围内。注意到在一个完全跳跃表中,50%的指针是 0级指针； 25%的指针是 1级指针； … ； (100/2k+1)%的指针是 k级指针。因此，在插入一个元素时，以概率 1/2引入一个 0级结点，以概率 1/4引入一个 1级结点,…,以概率 1/2k+1引入一个 k级结点。另一方面，一个 i级结点指向下一个同级或更高级的结点，它所跳过的结点数不再准确地维持在 2i-1。经过这样的修改，就可以在插入或删除一个元素时，通过对跳跃表的局部修改来维持其平衡性。
12
跳跃表注意到，在一个完全跳跃表中，具有 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是当前跳跃表中结点个数。当前跳跃表中任一结点的级别不超过 np/1log
np/1log
13
拉斯维加斯 ( Las Vegas )算法拉斯维加斯算法的一个显著特征是它所作的随机性决策有可能导致算法找不到所需的解。
public static void obstinate(Object x,Object y)
{// 反复调用拉斯维加斯算法 LV(x,y)，直到找到问题的一个解 y
boolean success= false;
while (!success) success=lv(x,y);
}
设 p(x)是对输入 x调用拉斯维加斯算法获得问题的一个解的概率。
一个正确的拉斯维加斯算法应该对所有输入 x均有 p(x)>0。
设 t(x)是算法 obstinate找到具体实例 x的一个解所需的平均时间,s(x)和 e(x)分别是算法对于具体实例 x求解成功或求解失败所需的平均时间，则有：
解此方程可得：
))()())((1()()()( xtxexpxsxpxt
)()( )(1)()( xexp xpxsxt
14
n后问题对于 n后问题的任何一个解而言，每一个皇后在棋盘上的位臵无任何规律，不具有系统性，而更象是随机放臵的。由此容易想到下面的 拉斯维加斯算法 。
在棋盘上相继的各行中随机地放臵皇后，并注意使新放臵的皇后与已放臵的皇后互不攻击，直至 n个皇后均已相容地放臵好，或已没有下一个皇后的可放臵位臵时为止。
如果将上述随机放臵策略与回溯法相结合，可能会获得更好的效果。可以先在棋盘的若干行中随机地放臵皇后，然后在后继行中用回溯法继续放臵，直至找到一个解或宣告失败。随机放臵的皇后越多，后继回溯搜索所需的时间就越少，但失败的概率也就越大。
stopVegas p s e t
0 1.0000 262.00 -- 262.00
5 0.5039 33.88 47.23 80.39
12 0.0465 13.00 10.20 222.11
15
整数因子分解设 n>1是一个整数。关于整数 n的因子分解问题是找出 n的如下形式的惟一分解式：
其中,p1<p2<…<p k是 k个素数,m1,m2,…,m k是 k个正整数。
如果 n是一个合数，则 n必有一个非平凡因子 x,1<x<n，使得 x可以整除 n。 给定一个合数 n，求 n的一个非平凡因子的问题称为整数 n的因子分割问题。
kmkmm pppn?21 21?
private static int split(int n)
{
int m = (int) Math.floor(Math.sqrt((double)n));
for (int i=2; i<=m; i++)
if (n%i==0) return i;
return 1;
}
事实上，算法 split(n)是对范围在 1～ x的所有整数进行了试除而得到范围在 1～ x2的任一整数的因子分割。
16
Pollard算法在开始时选取 0～ n-1范围内的随机数，然后递归地由产生无穷序列对于 i=2k，以及 2k<j?2k+1，算法计算出 xj-xi与 n的最大公因子
d=gcd(xj-xi,n)。如果 d是 n的非平凡因子，则实现对 n的一次分割，算法输出 n的因子 d。
nxx ii m o d)1( 2 1
,,,,21 kxxx
private static void pollard(int n)
{// 求整数 n因子分割的拉斯维加斯算法
rnd = new Random(); // 初始化随机数
int i=1,k=2;
int x=rnd.random(n),y=x; // 随机整数
while (true) {
i++;
x=(x*x-1)%n;
int d=gcd(y-x,n); // 求 n的非平凡因子
if ((d>1) && (d<n)) System.out.println(d);
if (i==k) {
y=x;
k*=2;} } }
对 Pollard算法更深入的分析可知，执行算法的 while循环约次后,Pollard算法会输出 n的一个因子 p。由于 n的最小素因子 p?,故 Pollard算法可在
O(n1/4)时间内找到 n的一个素因子。
n
p
17
蒙特卡罗 (Monte Carlo)算法
在实际应用中常会遇到一些问题，不论采用确定性算法或概率算法都无法保证每次都能得到正确的解答。蒙特卡罗算法则在一般情况下可以保证对问题的所有实例都以高概率给出正确解，但是通常无法判定一个具体解是否正确。
设 p是一个实数，且 1/2<p<1。如果一个蒙特卡罗算法对于问题的任一实例得到正确解的概率不小于 p，则称该蒙特卡罗算法是
p正确 的，且称 p-1/2是该算法的 优势 。
如果对于同一实例，蒙特卡罗算法不会给出 2个不同的正确解答，
则称该蒙特卡罗算法是 一致的 。
有些蒙特卡罗算法除了具有描述问题实例的输入参数外，还具有描述错误解可接受概率的参数。这类算法的计算时间复杂性通常由问题的实例规模以及错误解可接受概率的函数来描述。
18
蒙特卡罗 (Monte Carlo)算法对于一个一致的 p正确蒙特卡罗算法，要提高获得正确解的概率，
只要执行该算法若干次，并选择出现频次最高的解即可。
如果重复调用一个一致的 (1/2+?)正确的蒙特卡罗算法 2m-1次，
得到正确解的概率至少为 1-?，其中，
mi
i mim
i
4
)41()
4
1(2
2
1 221
0
对于一个解所给问题的蒙特卡罗算法 MC(x)，如果存在问题实例的子集 X使得：
(1)当 x?X时,MC(x)返回的解是正确的；
(2)当 x?X时，正确解是 y0，但 MC(x)返回的解未必是 y0。
称上述算法 MC(x)是 偏 y0的算法 。
重复调用一个一致的,p正确偏 y0蒙特卡罗算法 k次，可得到一个 O(1-(1-p)k)正确的蒙特卡罗算法，且所得算法仍是一个一致的偏 y0蒙特卡罗算法。
19
主元素问题设 T[1:n]是一个含有 n个元素的数组。当 |{i|T[i]=x}|>n/2时，
称元素 x是数组 T的主元素。
public static boolean majority(int[]t,int n)
{// 判定主元素的蒙特卡罗算法
rnd = new Random();
int i=rnd.random(n)+1;
int x=t[i]; // 随机选择数组元素
int k=0;
for (int j=1;j<=n;j++)
if (t[j]==x) k++;
return (k>n/2); // k>n/2 时 t含有主元素
}
public static boolean majorityMC(int[]t,int n,double e)
{// 重复 é ù次调用算法 majority
int k= (int) Math.ceil(Math.log(1/e)/Math.log(2));
for (int i=1;i<=k;i++)
if (majority(t,n)) return true;
return false;
}
对于任何给定的?>0，算法
majorityMC重复调用?log(1/?)? 次算法 majority。它是一个偏真蒙特卡罗算法，且其错误概率小于?。算法 majorityMC所需的计算时间显然是 O(nlog(1/?))。
20
素数测试
Wilson定理,对于给定的正整数 n，判定 n是一个素数的充要条件是 (n-1)!?-1(mod n)。
费尔马小定理,如果 p是一个素数，且 0<a<p，则 ap-1(mod p)。
二次探测定理,如果 p是一个素数，且 0<x<p，则方程 x2?1(mod p)
的解为 x=1,p-1。
private static int power(int a,int p,int n)
{// 计算 ap mod n，并实施对 n的二次探测
int x,result;
if (p==0) result=1;
else {
x=power(a,p/2,n); // 递归计算
result=(x*x)%n; // 二次探测
if ((result==1)&&(x!=1)&&(x!=n-1))
composite=true;
if ((p%2)==1) // p是奇数
result=(result*a)%n;
}
return result;}
public static boolean prime(int n)
{// 素数测试的蒙特卡罗算法
rnd = new Random();
int a,result;
composite=false;
a=rnd.random(n-3)+2;
result=power(a,n-1,n);
if (composite||(result!=1)) return false;
else return true;
}
算法 prime是一个偏假 3/4正确的蒙特卡罗算法。通过多次重复调用错误概率不超过 (1/4)k。这是一个很保守的估计，实际使用的效果要好得多。
第 7章 概率算法
2
随机数随机数在概率算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数，因此在概率算法中使用的随机数都是一定程度上随机的，即伪随机数。
线性同余法 是产生伪随机数的最常用的方法。由线性同余法产生的随机序列 a0,a1,…,a n满足
,2,1m o d)( 1
0
nmcbaa
da
nn
其中 b?0,c?0,d?m。 d称为该随机序列的种子。如何选取该方法中的常数 b,c和 m直接关系到所产生的随机序列的随机性能。这是随机性理论研究的内容，已超出本书讨论的范围。从直观上看,m应取得充分大，因此可取 m为机器大数，另外应取 gcd(m,b)=1，因此可取 b为一素数。
3
数值概率算法
4
用随机投点法计算?值设有一半径为 r的圆及其外切四边形。向该正方形随机地投掷 n个点。设落入圆内的点数为 k。由于所投入的点在正方形上均匀分布，因而所投入的点落入圆内的概率为 。所以当 n足够大时,k与 n之比就逼近这一概率。从而 。
44 2
2
r
r
n
k4
public static double darts(int n)
{ // 用随机投点法计算?值
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 4*k/(double)n;
}
5
计算定积分设 f(x)是 [0,1]上的连续函数，且 0?f(x)?1。
需要计算的积分为,积分 I等于图中的面积 G。
1
0
)( dxxfI
在图所示单位正方形内均匀地作投点试验，则随机点落在曲线下面的概率为假设向单位正方形内随机地投入 n个点 (xi,yi)。如果有 m个点落入
G内，则随机点落入 G内的概率
1
0
)(
0
1
0
)()}({
xf
r dxxfd y d xxfyP
n
m?I
6
解非线性方程组求解下面的非线性方程组
0),,,(
0),,,(
0),,,(
21
212
211
nn
n
n
xxxf
xxxf
xxxf
其中,x1,x2,…,x n是实变量,fi是未知量 x1,x2,…,x n的非线性实函数。要求确定上述方程组在指定求根范围内的一组解 **2*1,,,nxxx?
在指定求根区域 D内，选定一个随机点 x0作为随机搜索的出发点。在算法的搜索过程中，假设第 j步随机搜索得到的随机搜索点为 xj。在第 j+1步，计算出下一步的随机搜索增量?xj。从当前点 xj依?xj得到第 j+1步的随机搜索点。当 x<?时，取为所求非线性方程组的近似解。否则进行下一步新的随机搜索过程。
7
舍伍德 (Sherwood)算法设 A是一个确定性算法，当它的输入实例为 x时所需的计算时间记为 tA(x)。设 Xn是算法 A的输入规模为 n的实例的全体，则当问题的输入规模为 n时，算法 A所需的平均时间为
nXx
nAA Xxtnt ||/)()(
这显然不能排除存在 x∈ Xn使得 的可能性。希望获得一个概率算法 B，使得对问题的输入规模为 n的每一个实例均有这就是舍伍德算法设计的基本思想。当 s(n)与 tA(n)相比可忽略时，
舍伍德算法可获得很好的平均性能。
)()( ntxt AA
)()()( nsntxt AB
8
舍伍德 (Sherwood)算法复习学过的 Sherwood算法：
（ 1）线性时间选择算法
（ 2）快速排序算法有时也会遇到这样的情况，即所给的确定性算法无法直接改造成舍伍德型算法。此时可借助于随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌，同样可收到舍伍德算法的效果。例如，对于确定性选择算法，可以用下面的洗牌算法 shuffle将数组 a中元素随机排列，然后用确定性选择算法求解。这样做所收到的效果与舍伍德型算法的效果是一样的。
public static void shuffle(Comparable []a,int n)
{// 随机洗牌算法
rnd = new Random();
for (int i=1;i<n;i++) {
int j=rnd.random(n-i+1)+i;
MyMath.swap(a,i,j);
}
}
9
跳跃表
舍伍德型算法的设计思想还可用于设计高效的数据结构。
如果用有序链表来表示一个含有 n个元素的有序集 S，则在最坏情况下，搜索 S中一个元素需要?(n)计算时间。
提高有序链表效率的一个技巧是在有序链表的部分结点处增设附加指针以提高其搜索性能。在增设附加指针的有序链表中搜索一个元素时，可借助于附加指针跳过链表中若干结点，加快搜索速度。这种增加了向前附加指针的有序链表称为 跳跃表 。
应在跳跃表的哪些结点增加附加指针以及在该结点处应增加多少指针完全采用随机化方法来确定。这使得跳跃表可在 O(logn)
平均时间内支持关于有序集的搜索、插入和删除等运算。
10
跳跃表在一般情况下，给定一个含有 n个元素的有序链表，可以将它改造成一个完全跳跃表，使得每一个 k级结点含有 k+1个指针，分别跳过 2k-1,2k-1-1,…,20-1个中间结点。第 i个 k级结点安排在跳跃表的位臵 i2k处,i?0。这样就可以在时间 O(logn)内完成集合成员的搜索运算。在一个完全跳跃表中，最高级的结点是?logn?
级结点。
完全跳跃表与完全二叉搜索树的情形非常类似。它虽然可以有效地支持成员搜索运算，但不适应于集合动态变化的情况。集合元素的插入和删除运算会破坏完全跳跃表原有的平衡状态，
影响后继元素搜索的效率。
11
跳跃表为了在动态变化中维持跳跃表中附加指针的平衡性，必须使跳跃表中 k级结点数维持在总结点数的一定比例范围内。注意到在一个完全跳跃表中,50%的指针是 0级指针； 25%的指针是 1级指针； … ； (100/2k+1)%的指针是 k级指针。因此，在插入一个元素时，以概率 1/2引入一个 0级结点，以概率 1/4引入一个 1级结点,…,以概率 1/2k+1引入一个 k级结点。另一方面，一个 i级结点指向下一个同级或更高级的结点，它所跳过的结点数不再准确地维持在 2i-1。经过这样的修改，就可以在插入或删除一个元素时，通过对跳跃表的局部修改来维持其平衡性。
12
跳跃表注意到，在一个完全跳跃表中，具有 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是当前跳跃表中结点个数。当前跳跃表中任一结点的级别不超过 np/1log
np/1log
13
拉斯维加斯 ( Las Vegas )算法拉斯维加斯算法的一个显著特征是它所作的随机性决策有可能导致算法找不到所需的解。
public static void obstinate(Object x,Object y)
{// 反复调用拉斯维加斯算法 LV(x,y)，直到找到问题的一个解 y
boolean success= false;
while (!success) success=lv(x,y);
}
设 p(x)是对输入 x调用拉斯维加斯算法获得问题的一个解的概率。
一个正确的拉斯维加斯算法应该对所有输入 x均有 p(x)>0。
设 t(x)是算法 obstinate找到具体实例 x的一个解所需的平均时间,s(x)和 e(x)分别是算法对于具体实例 x求解成功或求解失败所需的平均时间，则有：
解此方程可得：
))()())((1()()()( xtxexpxsxpxt
)()( )(1)()( xexp xpxsxt
14
n后问题对于 n后问题的任何一个解而言，每一个皇后在棋盘上的位臵无任何规律，不具有系统性，而更象是随机放臵的。由此容易想到下面的 拉斯维加斯算法 。
在棋盘上相继的各行中随机地放臵皇后，并注意使新放臵的皇后与已放臵的皇后互不攻击，直至 n个皇后均已相容地放臵好，或已没有下一个皇后的可放臵位臵时为止。
如果将上述随机放臵策略与回溯法相结合，可能会获得更好的效果。可以先在棋盘的若干行中随机地放臵皇后，然后在后继行中用回溯法继续放臵，直至找到一个解或宣告失败。随机放臵的皇后越多，后继回溯搜索所需的时间就越少，但失败的概率也就越大。
stopVegas p s e t
0 1.0000 262.00 -- 262.00
5 0.5039 33.88 47.23 80.39
12 0.0465 13.00 10.20 222.11
15
整数因子分解设 n>1是一个整数。关于整数 n的因子分解问题是找出 n的如下形式的惟一分解式：
其中,p1<p2<…<p k是 k个素数,m1,m2,…,m k是 k个正整数。
如果 n是一个合数，则 n必有一个非平凡因子 x,1<x<n，使得 x可以整除 n。 给定一个合数 n，求 n的一个非平凡因子的问题称为整数 n的因子分割问题。
kmkmm pppn?21 21?
private static int split(int n)
{
int m = (int) Math.floor(Math.sqrt((double)n));
for (int i=2; i<=m; i++)
if (n%i==0) return i;
return 1;
}
事实上，算法 split(n)是对范围在 1～ x的所有整数进行了试除而得到范围在 1～ x2的任一整数的因子分割。
16
Pollard算法在开始时选取 0～ n-1范围内的随机数，然后递归地由产生无穷序列对于 i=2k，以及 2k<j?2k+1，算法计算出 xj-xi与 n的最大公因子
d=gcd(xj-xi,n)。如果 d是 n的非平凡因子，则实现对 n的一次分割，算法输出 n的因子 d。
nxx ii m o d)1( 2 1
,,,,21 kxxx
private static void pollard(int n)
{// 求整数 n因子分割的拉斯维加斯算法
rnd = new Random(); // 初始化随机数
int i=1,k=2;
int x=rnd.random(n),y=x; // 随机整数
while (true) {
i++;
x=(x*x-1)%n;
int d=gcd(y-x,n); // 求 n的非平凡因子
if ((d>1) && (d<n)) System.out.println(d);
if (i==k) {
y=x;
k*=2;} } }
对 Pollard算法更深入的分析可知，执行算法的 while循环约次后,Pollard算法会输出 n的一个因子 p。由于 n的最小素因子 p?,故 Pollard算法可在
O(n1/4)时间内找到 n的一个素因子。
n
p
17
蒙特卡罗 (Monte Carlo)算法
在实际应用中常会遇到一些问题，不论采用确定性算法或概率算法都无法保证每次都能得到正确的解答。蒙特卡罗算法则在一般情况下可以保证对问题的所有实例都以高概率给出正确解，但是通常无法判定一个具体解是否正确。
设 p是一个实数，且 1/2<p<1。如果一个蒙特卡罗算法对于问题的任一实例得到正确解的概率不小于 p，则称该蒙特卡罗算法是
p正确 的，且称 p-1/2是该算法的 优势 。
如果对于同一实例，蒙特卡罗算法不会给出 2个不同的正确解答，
则称该蒙特卡罗算法是 一致的 。
有些蒙特卡罗算法除了具有描述问题实例的输入参数外，还具有描述错误解可接受概率的参数。这类算法的计算时间复杂性通常由问题的实例规模以及错误解可接受概率的函数来描述。
18
蒙特卡罗 (Monte Carlo)算法对于一个一致的 p正确蒙特卡罗算法，要提高获得正确解的概率，
只要执行该算法若干次，并选择出现频次最高的解即可。
如果重复调用一个一致的 (1/2+?)正确的蒙特卡罗算法 2m-1次，
得到正确解的概率至少为 1-?，其中，
mi
i mim
i
4
)41()
4
1(2
2
1 221
0
对于一个解所给问题的蒙特卡罗算法 MC(x)，如果存在问题实例的子集 X使得：
(1)当 x?X时,MC(x)返回的解是正确的；
(2)当 x?X时，正确解是 y0，但 MC(x)返回的解未必是 y0。
称上述算法 MC(x)是 偏 y0的算法 。
重复调用一个一致的,p正确偏 y0蒙特卡罗算法 k次，可得到一个 O(1-(1-p)k)正确的蒙特卡罗算法，且所得算法仍是一个一致的偏 y0蒙特卡罗算法。
19
主元素问题设 T[1:n]是一个含有 n个元素的数组。当 |{i|T[i]=x}|>n/2时，
称元素 x是数组 T的主元素。
public static boolean majority(int[]t,int n)
{// 判定主元素的蒙特卡罗算法
rnd = new Random();
int i=rnd.random(n)+1;
int x=t[i]; // 随机选择数组元素
int k=0;
for (int j=1;j<=n;j++)
if (t[j]==x) k++;
return (k>n/2); // k>n/2 时 t含有主元素
}
public static boolean majorityMC(int[]t,int n,double e)
{// 重复 é ù次调用算法 majority
int k= (int) Math.ceil(Math.log(1/e)/Math.log(2));
for (int i=1;i<=k;i++)
if (majority(t,n)) return true;
return false;
}
对于任何给定的?>0，算法
majorityMC重复调用?log(1/?)? 次算法 majority。它是一个偏真蒙特卡罗算法，且其错误概率小于?。算法 majorityMC所需的计算时间显然是 O(nlog(1/?))。
20
素数测试
Wilson定理,对于给定的正整数 n，判定 n是一个素数的充要条件是 (n-1)!?-1(mod n)。
费尔马小定理,如果 p是一个素数，且 0<a<p，则 ap-1(mod p)。
二次探测定理,如果 p是一个素数，且 0<x<p，则方程 x2?1(mod p)
的解为 x=1,p-1。
private static int power(int a,int p,int n)
{// 计算 ap mod n，并实施对 n的二次探测
int x,result;
if (p==0) result=1;
else {
x=power(a,p/2,n); // 递归计算
result=(x*x)%n; // 二次探测
if ((result==1)&&(x!=1)&&(x!=n-1))
composite=true;
if ((p%2)==1) // p是奇数
result=(result*a)%n;
}
return result;}
public static boolean prime(int n)
{// 素数测试的蒙特卡罗算法
rnd = new Random();
int a,result;
composite=false;
a=rnd.random(n-3)+2;
result=power(a,n-1,n);
if (composite||(result!=1)) return false;
else return true;
}
算法 prime是一个偏假 3/4正确的蒙特卡罗算法。通过多次重复调用错误概率不超过 (1/4)k。这是一个很保守的估计，实际使用的效果要好得多。
