欢迎来到天天文库
浏览记录
ID:51830578
大小:149.36 KB
页数:6页
时间:2020-03-16
《舍伍德线性时间选择.docx》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、算法分析与设计实验报告第8次实验姓名学号班级时间12.26下午地点四合院实验名称Sherwood型线性时间选择算法实验目的1)通过上机实验,要求掌握Sherwood型线性时间选择算法的问题描述、算法设计思想、程序设计。实验原理使用舍伍德型选择算法,根据不同的输入用例,能准确的输出用例中的中值,并计算出程序运行所需要的时间给定任意几组数据,利用舍伍德型选择算法,找出数组中的中值并输出(若数组为奇数个则输出中值,若数组为偶数个则输出第n/2小元素)。实验步骤①先判断是否需要进行随机划分即(kϵ(1,n)?n>1?);②产生随
2、机数j,选择划分基准,将a[j]与a[l]交换;③以划分基准为轴做元素交换,使得一侧数组小于基准值,另一侧数组值大于基准值;④判断基准值是否就是所需选择的数,若是,则输出;若不是对子数组重复步骤②③④。关键代码templateinlinevoidSwap(Type&a,Type&b){Typetemp=a;a=b;b=temp;}//计算a[l:r]中第k小元素templateTypeselect(Typea[],intl,intr,intk){staticRandomNumb
3、errnd;while(true){if(l>=r){returna[l];}inti=l,j=l+rnd.Random(r-l+1);//随机选择划分基准Swap(a[i],a[j]);j=r+1;Typepivot=a[l];//以划分基准为轴做元素交换while(true){while(a[++i]pivot);if(i>=j){break;}Swap(a[i],a[j]);}if(j-l+1==k){//第k小returnpivot;}//a[j]必然小于pivot,做最
4、后一次交换,满足左侧比pivot小,右侧比pivot大a[l]=a[j];a[j]=pivot;//对子数组重复划分过程if(j-l+1Typeselect(Typea[],intn,intk){if(k<1
5、
6、k>n){cout<<"请输入正确的k!"<7、elect(a,0,n-1,k);}测试结果实验心得通过这次实验,我回顾了舍伍德线性时间查找问题本次实验实现起来的代码较长,但在之前的实验中都要求使用舍伍德产生随机数,因此本次实验还是比较简单的。主要是掌握对随机数RandomNuber类的理解。在实现书上代码后,我将代码改进为随机产生序列的方式,手动选择查找的数组元素(从小到大排序后)的序号,并输出到屏幕。因此,要想找出最大元素,直接输入查找序号为数组大小即可得,同理最小元素为序号一,因此可以实现最值求解。通过本次实验发现,尽管嗯多时候实验的算法内容能在书本上找到,但是8、如果能加入自己的理解进行修改代码,也会有很大的收获,因为只有掌握了思想才能进行修改。实验得分助教签名附录:完整代码#includeusingnamespacestd;//随机数类constunsignedlongmaxshort=66536L;constunsignedlongmultiplier=1194211693L;constunsignedlongadder=12345L;classRandomNumber{private://当前种子unsignedlongrandSeed;public:Ran9、domNumber(unsignedlongs=0);//构造函数,默认值0表示由系统自动产生种子unsignedshortRandom(unsignedlongn);//产生0:n-1之间的随机整数doublefRandom(void);//产生[0,1)之间的随机实数};RandomNumber::RandomNumber(unsignedlongs){if(s==0)randSeed=time(0);elserandSeed=s;}unsignedshortRandomNumber::Random(unsigned10、longn){randSeed=multiplier*randSeed+adder;return(unsignedshort)((randSeed>16)%n);}doubleRandomNumber::fRandom(void){returnRandom(maxshort)/double(maxshort);}te
7、elect(a,0,n-1,k);}测试结果实验心得通过这次实验,我回顾了舍伍德线性时间查找问题本次实验实现起来的代码较长,但在之前的实验中都要求使用舍伍德产生随机数,因此本次实验还是比较简单的。主要是掌握对随机数RandomNuber类的理解。在实现书上代码后,我将代码改进为随机产生序列的方式,手动选择查找的数组元素(从小到大排序后)的序号,并输出到屏幕。因此,要想找出最大元素,直接输入查找序号为数组大小即可得,同理最小元素为序号一,因此可以实现最值求解。通过本次实验发现,尽管嗯多时候实验的算法内容能在书本上找到,但是
8、如果能加入自己的理解进行修改代码,也会有很大的收获,因为只有掌握了思想才能进行修改。实验得分助教签名附录:完整代码#includeusingnamespacestd;//随机数类constunsignedlongmaxshort=66536L;constunsignedlongmultiplier=1194211693L;constunsignedlongadder=12345L;classRandomNumber{private://当前种子unsignedlongrandSeed;public:Ran
9、domNumber(unsignedlongs=0);//构造函数,默认值0表示由系统自动产生种子unsignedshortRandom(unsignedlongn);//产生0:n-1之间的随机整数doublefRandom(void);//产生[0,1)之间的随机实数};RandomNumber::RandomNumber(unsignedlongs){if(s==0)randSeed=time(0);elserandSeed=s;}unsignedshortRandomNumber::Random(unsigned
10、longn){randSeed=multiplier*randSeed+adder;return(unsignedshort)((randSeed>16)%n);}doubleRandomNumber::fRandom(void){returnRandom(maxshort)/double(maxshort);}te
此文档下载收益归作者所有