随机化算法实验(Sherwood型线性时间选择)

《随机化算法实验(Sherwood型线性时间选择)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法分析与设计实验报告第八次实验姓名学号班级时间12.26上午地点工训楼309实验名称随机化算法实验(Sherwood型线性时间选择)实验目的1.通过上机实验，要求掌握Sherwood型线性时间选择算法的问题描述、算法设计思想、程序设计。2.使用舍伍德型选择算法，根据不同的输入用例，能准确的输出用例中的中值，并计算出程序运行所需要的时间。实验原理问题描述：给定任意几组数据，利用舍伍德型选择算法，找出数组中的中值并输出（若数组为奇数个则输出中值，若数组为偶数个则输出第n/2小元素）。基本思想： 设A是一个确定性算法，当它的输入实例为x时所需的计算时间记为tA(

2、x)。设Xn是算法A的输入规模为n的实例的全体，则当问题的输入规模为n时，算法A所需的平均时间为。这显然不能排除存在x∈Xn使得的可能性。希望获得一个随机化算法B，使得对问题的输入规模为n的每一个实例均有。这就是舍伍德算法设计的基本思想。当s(n)与tA(n)相比可忽略时，舍伍德算法可获得很好的平均性能。实验步骤（1）先判断是否需要进行随机划分即（k∈(1,n)?n>1?）；（2）产生随机数j,选择划分基准，将a[j]与a[l]交换；（3）以划分基准为轴做元素交换，使得一侧数组小于基准值，另一侧数组值大于基准值；（4）判断基准值是否就是所需选择的数，若是，则

3、输出；若不是对子数组重复步骤(2)(3)(4)。关键代码//计算a[l:r]中第k小元素templateTypeselect(Typea[],intl,intr,intk){while(true){if(l>=r)//此种情况表示只有一个元素{returna[l];}inti=l;intj=r+1;Typepivot=a[l];//轴值每次都选择最左边的元素//以划分基准为轴做元素交换while(true){//将pivot的元素换到轴值右边while(a[++i]

4、-j]>pivot);if(i>=j){break;}Swap(a[i],a[j]);}if(j-l+1==k)//如果轴值是要选的元素即第k小{returnpivot;}//如果轴值不是要选的元素//a[j]必然小于等于pivot,做最后一次交换，满足左侧比pivot小，右侧比pivot大a[l]=a[j];a[j]=pivot;//对子数组重复划分过程if(j-l+1

5、较小的序列数：输入较大的序列数：不输出数组数只输出结果比较：实验分析在Sherwood型线性时间选择算法中，有两种实现方法，一种是随机划分基准；一种是随机洗牌预处理。随机划分基准处理如下：随机洗牌预处理如下：if(l>=r)template{returna[l];}voidShuffle(Typea[],intn)inti=l,{//随机数类//随机选择划分基准staticRandomNumberrnd;j=l+rnd.Random(r-l+1);for(inti=0;i

6、之间的整数j=r+1;intj=rnd.Random(n-i)+i;//随机选取的数作为基准值Typepivot=a[l];Swap(a[i],a[j]);}}我们可以看出一种是随机对于基准的选择，并不会影响原来的序列，可是有时所给的确定性算法无法直接改造成舍伍德型算法，所以我们就采用一种预处理的技术，将序列重新洗牌，排序，从而得到的第一种一样的结果，所以两种方法实现的功能是一样的额，都达到了使得最差情况与最好的情况的差距，在做题的时候根据不同算法的不同选择不同的方式。实验心得这一章的随机化算法其基本特点就是对所求解问题的同一实例用同一随机化算法求解两次可能

7、得到完全不同的效果。这种算法大概是一种辅助性算法，其目的是改善其他确定性算法的性能。这种随机处理的方法，在平时的算法的设计中用到会很多次，利用随机生成函数，可是之前并没有怎么在意过，也没有具体去了解它的实现怎样的样，不过通过这一种的学习，才将这种随机化算法弄明白到底是怎样的，也学到了以后再算法设计上要是想要提高算法的功能有一些什么样的改善方法。实验得分助教签名附录：完整代码（随机化算法）Sherwood.cpp//随机化算法线性时间选择输入预处理洗牌#include"RandomNumber.h"#include#include

8、.h>#includeusingn