舍伍德线性时间选择.docx

舍伍德线性时间选择.docx

ID:51830578

大小:149.36 KB

页数:6页

时间:2020-03-16

舍伍德线性时间选择.docx_第1页
舍伍德线性时间选择.docx_第2页
舍伍德线性时间选择.docx_第3页
舍伍德线性时间选择.docx_第4页
舍伍德线性时间选择.docx_第5页
资源描述:

《舍伍德线性时间选择.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: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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。