中科大黄刘生算法第一次作业Word文档格式.docx

1、=0 k+; else/函数在x轴下方，积分是f与x轴之间的部分，积分值为负 if y y 0/函数在x轴上方 then return k / n * （maxx - minx） * （maxy - miny） + miny * （maxx - minx）; else if maxy 0/函数在x轴下方 then return k / n * （maxx - minx） * （maxy - miny） + maxy * （maxx - minx）; else/函数穿越x轴 then return k / n * （maxx - minx） * （maxy - miny）;运行结果如下： 可见程

2、序运行结果还是很准确的，能正常处理在x轴单侧、穿越x轴的连续函数积分。Ex.5 估计自然数子集的大小 采用了课件中介绍的概率算法。为了加快速度，程序采用红黑树处理集合相关运算，比如判断产生的随机数是否已经出现过等，效率为O（log n）。 算法伪代码如下（部分非主要算法未给出）：struct Num/红黑树节点，num为已产生的随机数 num; parent; LeftChild; RightChild; color; ;LeftRotate（Num *root, Num *x）; /红黑树root以x为支点左旋RightRotate（Num *root, Num *x）; /红黑树root以

3、x为支点右旋insertfixup（Num *root, Num *z）; /修正插入元素z后的红黑树，使其符合红黑树性质insert（Num *root, Num *z）;/将节点z插入以root为根的红黑树，同时检查待插入的节点是否在树中出现过。返回true表示元素出现过，停止生成叶子；返回false表示未出现过这个元素，正常生成叶子NumberOfSet（n） Number 0;/ 对集合数目估计10次，10次的总和 for i 1 to 10 do times 0;NumPicked uniform（1, n）; NodeOfRedBlackTree NumPicked;/将产生的随机

4、数赋给红黑树节点 while insert（ NodeOfRedBlackTree ） = false /该元素没有出现过then do NodeOfRedBlackTree NumPicked; times+; /endwhile Number Number + 2 * times2 / pai; /endfor return Number / 10; 算法运行结果如下： 从以上的运行结果可以看出，算法能够处理100到109量级的计数，计数效果随n的增大逐渐变好。当n较小时，每次运行给出的结果误差非常大，每次运行结果相差也很大；n比较大了之后对集合数目的估计渐趋稳定，与真实值正负偏差百分之十

5、几，处理实际问题效果还是可以的，而且由于运用概率算法和红黑树，算法处理非常快。计数偏差较大可能与随机数周期不够长导致随机程度不够有关，或者是因为n还不够大，导致程序的理论基础n趋近于2k2/pai不成立。Ex.7 搜索有序表，写sherwood算法C，与算法A、B、D比较。 采用改写算法B（O（n1/2）的确定性算法）的方式写sherwood算法。为简单起见，我们直接使用乱序的1.n的自然数序列。 以下是算法的伪代码：MyShuffle（val, ptr, n） /sherwood用到的随机化函数 for i 1 to do j uniform（1, n）; swap（vali, valj）;

6、 swap（ptri, ptrj）; B（x） /设x在val1.n中，O（n1/2） i head; max vali; / max初值是表val中最小值 for j 1 to do y val j ; / 的最大整数y相应的下标i if max y x then i j; max y; /endif / endfor return Search（x, i）; / 从y开始继续搜索 C（x） /设x在val1.n中，sherwood算法，以B为基础 MyShuffle（val, ptr, n）; Return B（x）; 以下是一些运行结果： 上面这三幅截屏处理的是随机序列，可见对于随机数列

7、而言，O（n1/2）的确定性算法B和以其为基础的sherwood算法C表现都很好，速度很快。而最简单的顺序搜索方法A效果要差的多。随机算法D表现时好时坏，有的时候可以和B、C媲美，可有的时候和A一样差。 下面两幅截图主要用于说明sherwood算法的优势： 上述两幅截图处理的是已经按递增顺序排好的序列，这是算法B最差的情况。可见面对这种输入，B的表现和A一样差，甚至由于之前n1/2次的比较、判断表现比A算法还要差。随机算法D表现还不错，但仍然可能出现非常差的结果。可是sherwood算法C，表现始终很好，因为C中对输入序列进行了随机化，最差情况只会以一个非常小的概率出现，消除了算法对输入实例的

8、差异，能很稳定的获得O（n1/2）的复杂度。 值得一提的是sherwood中使用的对实例的随机化函数复杂度为O（n1/2），只对前n1/2个元素随机化，这是考虑了B算法特点做出的决定。粗略估计，这样随机化之后最坏情况出现的概率为随机化之后，前n1/2个元素仍为最小的n1/2各元素的概率。粗略估计其概率为，当n为16时，上式结果为。Ex.10 求n=12.20的最优StepVegas。算法采用多次执行这种QueenLV算法（100次），求取成功率、成功时搜索的节点数和失败是搜索的节点数，然后再根据t=s+（1-p）*e/p求出平均搜索节点数。 伪代码如下：backtrace（k, try, co

9、l, diag45, diag135,success, QueenNum, NodesSearched）/回溯法 base k; i k;j1;/ 置当前行为第k行，当前列为第1列index 1; while i QueenNum do / 当前行号 QueenNum for j index to QueenNum do if （j col） and （j-i diag45） and （j+i diag135） then/从第一列向后寻找安全列 tryi j；/将j放入栈中 i +;/搜索下一行 index 1; /将列置为从1开始搜索 NodesSearched +; break; /end

10、if if j = QueenNum + 1 then /未找到可放置皇后的位置 i-； /退栈回溯到上一行 if i 0） then /nb=0时无安全位置，第k+1个皇后尚未放好 kk+1；/try1.k+1是（k+1）-promising tryk j；/放置（k+1）th个皇后 col col j ； diag45 diag45 j-k ； diag135 diag135 j+k ； /endif until nb = 0 or k = StepVegas； if （nb0）then /已随机放好stepVegas个皇后 backtrace （k, try, col, diag45,

11、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; for i 1 to 100 do /重复100次 QueenLV（success,

12、 try, QueenNum, StepVegas, NumberOfNodes）; if success = true then NumberOfSuccess +; SumSuccess += NumberOfNodes;else NumberOfFailed +; SumFailed += NumberOfNodes;/endif SuccessRate NumberOfSuccess / 100; /成功率 if SuccessRate = 0 then answer SumFailed / NumberOfFailed; else if SuccessRate = 1 then an

13、swer SumSuccess / NumberOfSuccess; else answer SumSuccess / NumberOfSuccess + （1 - SuccessRate） * SumFailed / NumberOfFailed / SuccessRate;/ t=s+（1-p）*e/p求出平均搜索节点数 return answer;SearchMin（answer, i, key, ANSWER） ANSWER answer0; for j 1 to i do if answeri 4，返回真时表示素数，假表示合数 auniform（2.n-2）; return Btes

14、t（a,n）; /测试n是否为强伪素数 RepeatMillRab（n,k） for i 1 to k do if MillRab（n） =false then return false; /一定是合数 return true； PrintPrimes（answer, num） /打印1万以内的素数 print 2，3； n 5； PrimesNumber 0; repeat if RepeatMillRab（n, ） then answerPrimesNumber n;/记录素数PrimesNumber +;/素数个数 n n+2; until n=10000; num PrimesNumb

15、er; IsPrime（n）/判断n是否为素数的确定性算法，n为奇数 for i 3 to do if n mod i = 0 return false; return true;PrintPrimesForSure（answer, num） repeat if IsPrime（n） then _Static（） PrimesForSure, PrimesRepeatMillRab ;/储存两种算法找出的素数 PrimesNumRepeatMillRab, PrimesNumForSure 0;/两种算法素数的个数 PrintPrimes（PrimesRepeatMillRab, Primes

16、NumRepeatMillRab）; PrintPrimesForSure（PrimesForSure, PrimesNumForSure）; While PrimesRepeatMillRabindex1 100 do index1 +;/找到大于100素数的下标 While PrimesForSure index2 100 do index2 +; wrong 0;/错误数归0 for i index2 to PrimesNumForSure do for j i + index1 index2 + wrong to PrimesNumRepeatMillRab do if PrimesRepeatMillRabj = PrimesForSurei then break; else wrong +; i -; break; /endif /endfor return wrong / （PrimesNumRepeatMillRab - index1）; 三次的运行结果如下： 从以上三幅截图可以看出，蒙特卡洛算法求取素数准确度还是很高的，10010000内的素数错误数目在10个左右，比例仅为0.49%0.74%，效果还是很好的。如想进一步提高准确度可增加蒙特卡洛算法中迭代的次数。