中科大黄刘生算法第一次作业Word文档格式.docx
《中科大黄刘生算法第一次作业Word文档格式.docx》由会员分享，可在线阅读，更多相关《中科大黄刘生算法第一次作业Word文档格式.docx（18页珍藏版）》请在冰点文库上搜索。
=0
k++;
else//函数在x轴下方，积分是f与x轴之间的部分，积分值为负
ify>
y<
=0
k--;
ifminy>
0//函数在x轴上方
thenreturnk/n*（maxx-minx）*（maxy-miny）+miny*（maxx-minx））;
elseifmaxy<
0//函数在x轴下方
thenreturnk/n*（maxx-minx）*（maxy-miny）+maxy*（maxx-minx）;
else//函数穿越x轴
thenreturnk/n*（maxx-minx）*（maxy-miny）;
}
运行结果如下：
可见程序运行结果还是很准确的，能正常处理在x轴单侧、穿越x轴的连续函数积分。
Ex.5估计自然数子集的大小
采用了课件中介绍的概率算法。
为了加快速度，程序采用红黑树处理集合相关运算，比如判断产生的随机数是否已经出现过等，效率为O（logn）。
算法伪代码如下（部分非主要算法未给出）：
structNum{//红黑树节点，num为已产生的随机数
num;
parent;
LeftChild;
RightChild;
color;
};
LeftRotate（Num**root,Num*x）;
//红黑树root以x为支点左旋
RightRotate（Num**root,Num*x）;
//红黑树root以x为支点右旋
insertfixup（Num**root,Num*z）;
//修正插入元素z后的红黑树，使其符合红黑树性质
insert（Num**root,Num*z）;
//将节点z插入以root为根的红黑树，同时检查待插入的节点是否在树中出现过。
返回true表示元素出现过，停止生成叶子；
返回false表示未出现过这个元素，正常生成叶子
NumberOfSet（n）
Number←0;
//对集合数目估计10次，10次的总和
fori←1to10do{
times←0;
NumPicked←uniform（1,n）;
NodeOfRedBlackTree←NumPicked;
//将产生的随机数赋给红黑树节点
while[insert（NodeOfRedBlackTree）]=false//该元素没有出现过
thendo{
NodeOfRedBlackTree←NumPicked;
times++;
}//endwhile
Number←Number+2*times^2/pai;
}//endfor
returnNumber/10;
算法运行结果如下：
从以上的运行结果可以看出，算法能够处理100到10^9量级的计数，计数效果随n的增大逐渐变好。
当n较小时，每次运行给出的结果误差非常大，每次运行结果相差也很大；
n比较大了之后对集合数目的估计渐趋稳定，与真实值正负偏差百分之十几，处理实际问题效果还是可以的，而且由于运用概率算法和红黑树，算法处理非常快。
计数偏差较大可能与随机数周期不够长导致随机程度不够有关，或者是因为n还不够大，导致程序的理论基础n趋近于2k^2/pai不成立。
Ex.7搜索有序表，写sherwood算法C，与算法A、B、D比较。
采用改写算法B（O（n^1/2）的确定性算法）的方式写sherwood算法。
为简单起见，我们直接使用乱序的[1..n]的自然数序列。
以下是算法的伪代码：
MyShuffle（val,ptr,n）{//sherwood用到的随机化函数
fori←1todo{
j←uniform（1,n）;
swap（val[i],val[j]）;
swap（ptr[i],ptr[j]）;
}
B（x）{//设x在val[1..n]中，O（n^1/2）
i←head;
max←val[i];
//max初值是表val中最小值
forj←1todo{
y←val[j];
//的最大整数y相应的下标i
ifmax<
y≤xthen{
i←j;
max←y;
}//endif
}//endfor
returnSearch（x,i）;
//从y开始继续搜索
}
C（x）{//设x在val[1..n]中，sherwood算法，以B为基础
MyShuffle（val,ptr,n）;
ReturnB（x）;
以下是一些运行结果：
上面这三幅截屏处理的是随机序列，可见对于随机数列而言，O（n^1/2）的确定性算法B和以其为基础的sherwood算法C表现都很好，速度很快。
而最简单的顺序搜索方法A效果要差的多。
随机算法D表现时好时坏，有的时候可以和B、C媲美，可有的时候和A一样差。
下面两幅截图主要用于说明sherwood算法的优势：
上述两幅截图处理的是已经按递增顺序排好的序列，这是算法B最差的情况。
可见面对这种输入，B的表现和A一样差，甚至由于之前n^1/2次的比较、判断表现比A算法还要差。
随机算法D表现还不错，但仍然可能出现非常差的结果。
可是sherwood算法C，表现始终很好，因为C中对输入序列进行了随机化，最差情况只会以一个非常小的概率出现，消除了算法对输入实例的差异，能很稳定的获得O（n^1/2）的复杂度。
值得一提的是sherwood中使用的对实例的随机化函数复杂度为O（n^1/2），只对前n^1/2个元素随机化，这是考虑了B算法特点做出的决定。
粗略估计，这样随机化之后最坏情况出现的概率为随机化之后，前n^1/2个元素仍为最小的n^1/2各元素的概率。
粗略估计其概率
为
，当n为16时，上式结果为
。
Ex.10求n=12..20的最优StepVegas。
算法采用多次执行这种QueenLV算法（100次），求取成功率、成功时搜索的节点数和失败是搜索的节点数，然后再根据t=s+（1-p）*e/p求出平均搜索节点数。
伪代码如下：
backtrace（k,try,col,diag45,diag135,success,QueenNum,NodesSearched）{//回溯法
base←k;
i←k;
j←1;
//置当前行为第k行，当前列为第1列
index←1;
whilei≤QueenNumdo{//当前行号≤QueenNum
forj←indextoQueenNumdo{
if（j∉col）and（j-i∉diag45）and（j+i∉diag135）then{
//从第一列向后寻找安全列
try[i]←j；
//将j放入栈中
i++;
//搜索下一行
index←1;
//将列置为从1开始搜索
NodesSearched++;
break;
}//endif
ifj=QueenNum+1then{//未找到可放置皇后的位置
i--；
//退栈回溯到上一行
ifi<
basethensuccess←false;
//超过回溯的界限，失败
index←try[i]+1;
//移去该行已放置的皇后，从下一列开始继续搜索
}//endif
}//endwhile
success←true;
QueensLv（success,try,QueenNum,StepVegas,NodesSearched）{//折中的LV算法
col,diag45,diag135←Φ；
//列及两对角线集合初值为空
k←0；
//行号
repeat//try[1..k]是k-promising，考虑放第k+1个皇后
nb←0；
//计数器，nb值为（k+1）th皇后的open位置总数
fori←1toQueenNumdo{//i是列号
if（i∉col）and（i-k-1∉diag45）and（i+k+1∉diag135）then{
//列i对（k+1）th皇后可用，但不一定马上将其放在第i列
nb←nb+1；
ifuniform（1..nb）=1then//或许放在第i列
j←i；
//注意第一次uniform一定返回1，即j一定有值1
}//endif
}//endfor，在nb个安全的位置上随机选择1个位置j放置之
if（nb>
0）then{//nb=0时无安全位置，第k+1个皇后尚未放好
k←k+1；
//try[1..k+1]是（k+1）-promising
try[k]←j；
//放置（k+1）th个皇后
col←col∪{j}；
diag45←diag45∪{j-k}；
diag135←diag135∪{j+k}；
}//endif
untilnb=0ork=StepVegas；
if（nb>
0）then//已随机放好stepVegas个皇后
backtrace（k,try,col,diag45,diag135,success,QueenNum,NodesSearched）;
else
success←false；
StaticNodesSearched（QueenNum,StepVegas）{//统计有QueenNum个皇后，StepVegas给定条件下搜索的节点数目
try←∅
success←false;
NumberOfNodes←1;
SumSuccess←0;
//算法成功时搜索节点数
SumFailed←0;
NumberOfSuccess←0;
//算法成功次数
NumberOfFailed←0;
fori←1to100do{//重复100次
QueenLV（success,try,QueenNum,StepVegas,NumberOfNodes）;
ifsuccess=truethen{
NumberOfSuccess++;
SumSuccess+=NumberOfNodes;
else{
NumberOfFailed++;
SumFailed+=NumberOfNodes;
}//endif
SuccessRate←NumberOfSuccess/100;
//成功率
ifSuccessRate=0then{
answer←SumFailed/NumberOfFailed;
elseifSuccessRate=1then{
answer←SumSuccess/NumberOfSuccess;
else{
answer←SumSuccess/NumberOfSuccess+（1-SuccessRate）*SumFailed/NumberOfFailed/SuccessRate;
//t=s+（1-p）*e/p求出平均搜索节点数
returnanswer;
SearchMin（answer,i,key,ANSWER）{
ANSWER←answer[0];
forj←1toido{
ifanswer[i]<
ANSWERthen{
key←i;
ANSWER←answer[i];
StepVegasCalculate（key,ANSWER）{
//key储存最优的StepVegas,ANSWER储存最优的搜索节点数
answer[21]←{10000};
fori←12to20do{
forj←1toido{
answer[j]←StaticNodesSearched（i,j）;
key←0;
ANSWER←0;
SearchMin（answer,i+1,key,ANSWER）;
给出三次的运行结果：
从以上三幅截图我们可以看出，最优步数基本在皇后数目的一半附近。
具体结果请参见截图。
EX.11打印10000以内的素数，与确定性算法比较，并给出100~10000内错误的比例。
Btest（a，n）{//n为奇数，
返回
即返回真说明n是强伪素数或素数
s←0；
t←n-1；
//t开始为偶数
repeat
s++；
t←t÷
2；
untiltmod2=1；
//n-1=2st，t为奇数
x←atmodn；
ifx=1orx=n-1thenreturntrue；
//满足①or②，
fori←1tos-1do{//验证
x←x2modn；
ifx=n-1thenreturntrue；
//满足②，
}
returnfalse；
MillRab（n）{//奇n>
4，返回真时表示素数，假表示合数
a←uniform（2..n-2）;
returnBtest（a,n）;
//测试n是否为强伪素数
RepeatMillRab（n,k）{
fori←1tokdo
ifMillRab（n）=falsethen
returnfalse;
//一定是合数
returntrue；
PrintPrimes（answer,num）{//打印1万以内的素数
print2，3；
n←5；
PrimesNumber←0;
repeat
ifRepeatMillRab（n,
）then{
answer[PrimesNumber]←n;
//记录素数
PrimesNumber++;
//素数个数
}
n←n+2;
untiln=10000;
num←PrimesNumber;
IsPrime（n）{//判断n是否为素数的确定性算法，n为奇数
fori←3to
do{
ifnmodi=0returnfalse;
returntrue;
PrintPrimesForSure（answer,num）{
repeat
ifIsPrime（n）then{
_Static（）{
PrimesForSure,PrimesRepeatMillRab←∅;
//储存两种算法找出的素数
PrimesNumRepeatMillRab,PrimesNumForSure←0;
//两种算法素数的个数
PrintPrimes（PrimesRepeatMillRab,PrimesNumRepeatMillRab）;
PrintPrimesForSure（PrimesForSure,PrimesNumForSure）;
WhilePrimesRepeatMillRab[index1]<
100doindex1++;
//找到大于100素数的下标
WhilePrimesForSure[index2]<
100doindex2++;
wrong←0;
//错误数归0
fori←index2toPrimesNumForSuredo{
forj←i+index1–index2+wrongtoPrimesNumRepeatMillRabdo{
ifPrimesRepeatMillRab[j]=PrimesForSure[i]thenbreak;
else{
wrong++;
i--;
break;
}//endif
}//endfor
returnwrong/（PrimesNumRepeatMillRab-index1）;
三次的运行结果如下：
从以上三幅截图可以看出，蒙特卡洛算法求取素数准确度还是很高的，100~10000内的素数错误数目在10个左右，比例仅为0.49%~0.74%，效果还是很好的。
如想进一步提高准确度可增加蒙特卡洛算法中迭代的次数。
升级会员 