文档介绍：文档名
*
随机数
随机数在概率算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数，因此在概率算法中使用的随机数都是一定程度上随机的，即伪随机数。
线性同余法是产生伪随机数的最常用的方法。由回的解是正确的；
(2)当xX时，正确解是y0，但MC(x)返回的解未必是y0。
称上述算法MC(x)是偏y0的算法。
重复调用一个一致的，p正确偏y0蒙特卡罗算法k次，可得到一个O(1-(1-p)k)正确的蒙特卡罗算法，且所得算法仍是一个一致的偏y0蒙特卡罗算法。
*
素数测试
Wilson定理：对于给定的正整数n，判定n是一个素数的充要条件是(n-1)! -1(mod n)。
费尔马小定理：如果p是一个素数，且0<a<p，则ap-1(mod p)。
二次探测定理：如果p是一个素数，且0<x<p，则方程x21(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=(n-3)+2;
result=power(a,n-1,n);
if (composite||(result!=1)) return false;
else return true;
}
算法prime是一个偏假3/4正确的蒙特卡罗算法。通过多次重复调用错误概率不超过(1/4)k。这是一个很保守的估计，实际使用的效果要好得多。
*
子集和问题的指数时间算法
int exactSubsetSum (S,t)
{
int n=|S|；
L[0]={0}；
for (int i=1；i<=n；i++) {
L[i]=mergeLists(L[i-1],L[i-1]+S[i])；
删去L[i]中超过t的元素；
}
return max(L[n])；
}
算法以集合S={x1，x2，…，xn}和目标值t作为输入。算法中用到将2个有序表L1和L2合并成为一个新的有序表的算法mergeLists(L1,L2)。
*
子集和问题的完全多项式 时间近似格式
基于算法exactSubsetSum，通过对表L[i]作适当的修整建立一个子集和问题的完全多项式时间近似格式。
在对表L[i]进行修整时，用到一个修整参数δ，0＜δ＜1。用参数δ修整一个表L是指从L中删去尽可能多的元素，使得每一个从L中删去的元素y，都有一个修整后的表L1中的元素z满足(1-δ)y≤z≤y。可以将z看作是被删去元素y在修整后的新表L1中的代表。
举例：若δ=，且L=〈10,11,12,15,20,21,22,23,24,29〉，则用δ对L进行修整后得到L1=〈10，12，15，20，23，29〉。其中被删去的数11由10来代表，21和22由20来代表，24由23来代表。
*
子集和问题的完全多项式 时间近似格式
对有序表L修整算法
List trim(L,δ)
{ int m=|L|；
L1=〈L[1]〉；
int last=L[1]；
for (int i=2；i<=m；i++) {
if (last<(1-δ)*L[i]) {
将L[i]加入表L1的尾部；
last=L[i]；
}
return L1；
}
子集和问题近似格式
int approxSubsetSum(S,t,ε)
{