舍伍德线性时间选择

1、算法分析与设计实验报告第8次实验姓名学号班级时间12.26下午地点四合院实验名称Sherwood型线性时间选择算法实验目的1）通过上机实验，要求掌握Sherwood型线性时间选择算法的问题描述、算法设计思想、程序设计。实验原理使用舍伍德型选择算法，根据不同的输入用例，能准确的输出用例中的中值，并计算出程序运行所需要的时间给定任意几组数据，利用舍伍德型选择算法，找出数组中的中值并输出（若数组为奇数个则输出中值，若数组为偶数个则输出第n/2小元素）。实验步骤先判断是否需要进行随机划分即（k（1,n）?n1?）;产生随机数j,选择划分基准，将aj与al交换；以划分基准为轴做元素交换，使得一侧数组小于

2、基准值，另一侧数组值大于基准值；判断基准值是否就是所需选择的数，若是，则输出；若不是对子数组重复步骤。关键代码templateclassTypeinlinevoidSwap(Type&a,Type&b)Typetemp=a;a=b;b=temp;计算al:r中第卜小元素templateclassTypeTypeselect(Typea,intl,intr,intk)staticRandomNumberrnd;while(true)if(l=r)returnal;inti=l,j=l+rnd.Random(r-l+1);/随机选择划分基准Swap(ai,aj);j=r+1；Typepivot=a

3、l;以划分基准为轴做元素交换while(true)while(a+ipivot);if(i=j)break;Swap(ai,aj);if(j-l+1=k)第k小returnpivot;aj必然小于pivot,做最后一次交换，满足左侧比pivot小，右侧比pivot大al=aj;aj=pivot;对子数组重复划分过程if(j-l+1k)k=k-j+l-1;/右侧：k-(jT+1)=k-j+lTl=j+1;elser=j-1;计算a0:n-1中第k小元素假设an是一个键值无穷大的元素templateTypeselect(Typea,intn,intk)if(kn)cout请输入正确的k!”endl

4、;return0;returnselect(a,0,n-1,k);请输入数组元素个数18请输入需要查找第几个元素：5原数组为:3479269998556139所给数组第5小元素为：61rocessexitedwithreturnvalue0ressanykeytocontinue.测试结果通过这次实验，我回顾了舍伍德线性时间查找问题本次实验实现起来的代码较长，但在之前的实验中都要求使用舍伍德产生随机数，因此本次实验还是比较简单的。主要是掌握对随机数RandomNuber类实验心得的理解。在实现书上代码后，我将代码改进为随机产生序列的方式，手动选择查找的数组元素（从小到大排序后）的序号，并输出到

5、屏幕。因此，要想找出最大元素，直接输入查找序号为数组大小即可得，同理最小元素为序号一，因此可以实现最值求解。通过本次实验发现，尽管嗯多时候实验的算法内容能在书本上找到，但是如果能加入自己的理解进行修改代码，也会有很大的收获，因为只有掌握了思想才能进行修改。实验得分助教签名附录：完整代码#includeusingnamespacestd;/随机数类constunsignedlongmaxshort=66536L;constunsignedlongmultiplier=1194211693L;constunsignedlongadder=12345L;classRandomNumberprivat

6、e:/当前种子unsignedlongrandSeed;public:RandomNumber(unsignedlongs=0);/构造函数，默认值0表示由系统自动产生种子unsignedshortRandom(unsignedlongn);产生0：nT之间的随机整数doublefRandom(void);/产生0，1)之间的随机实数;RandomNumber:RandomNumber(unsignedlongs)if(s=0)randSeed=time(0);elserandSeed=s;unsignedshortRandomNumber:Random(unsignedlongn)randS

7、eed=multiplier*randSeed+adder;return(unsignedshort)(randSeed16)%n);doubleRandomNumber:fRandom(void)returnRandom(maxshort)/double(maxshort);templateinlinevoidSwap(Type&a,Type&b)Typetemp=a;a=b;b=temp;计算al:r中第k小元素templateTypeselect(Typea,intl,intr,intk)staticRandomNumberrnd;while(true)if(l=r)returnal;i

8、nti=l,j=l+rnd.Random(r-l+1);/随机选择划分基准Swap(ai,aj);j=r+1;Typepivot=al;/以划分基准为轴做元素交换while(true)while(a+ipivot);if(i=j)break;Swap(ai,aj);if(j-l+1=k)第k小returnpivot;aj必然小于pivot,做最后一次交换，满足左侧比pivot小，右侧比pivot大al=aj;aj=pivot;/对子数组重复划分过程if(j-l+1k)k=k-j+l-1;/右侧：k-(j-l+1)=k-j+l-1l=j+1;elser=j-1;计算a0:n-1中第k小元素假设an是一个键值无穷大的元素templateTypeselect(Typea,intn,intk)if(kn)cout请输入正确的k!”endl;return0;returnselect(a,0,n-1,k);intmain()inta100=0;intm,k