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

算法分析与设计实验报告第八次实验姓名学号班级时间12.26上午地点工训楼309实验名称随机化算法实验(Sherwood型线性时间选择)实验目的1.通过上机实验，要求掌握Sherwood型线性时间选择算法的问题描述、算法设计思想、程序设计。2.使用舍伍德型选择算法，根据不同的输入用例，能准确的输出用例中的中值，并计算出程序运行所需要的时间。实验原理问题描述：给定任意几组数据，利用舍伍德型选择算法，找出数组中的中值并输出（若数组为奇数个则输出中值，若数组为偶数个则输出第n/2小元素）。基本思想：设A是一个确定性算法，当它的输入实例为x时所需的计算时间记为tA(x)。设Xn是算法A的输入规模为n的实例的全体，则当问题的输入规模为n时，算法A所需的平均时间为。这显然不能排除存在x∈Xn使得的可能性。希望获得一个随机化算法B，使得对问题的输入规模为n的每一个实例均有。这就是舍伍德算法设计的基本思想。当s(n)与tA(n)相比可忽略时，舍伍德算法可获得很好的平均性能。实验步骤（1）先判断是否需要进行随机划分即（k∈(1,n)?n1?）；（2）产生随机数j,选择划分基准，将a[j]与a[l]交换；（3）以划分基准为轴做元素交换，使得一侧数组小于基准值，另一侧数组值大于基准值；（4）判断基准值是否就是所需选择的数，若是，则输出；若不是对子数组重复步骤(2)(3)(4)。关键代码//计算a[l:r]中第k小元素templateclassTypeTypeselect(Typea[],intl,intr,intk){while(true){if(l=r)//此种情况表示只有一个元素{returna[l];}inti=l;intj=r+1;Typepivot=a[l];//轴值每次都选择最左边的元素//以划分基准为轴做元素交换while(true){//将pivot的元素换到轴值左边//将pivot的元素换到轴值右边while(a[++i]pivot);while(a[--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+1k)//第k小在pivot的右边部分{k=k-j+l-1;//右侧：k-(j-l+1)=k-j+l-1l=j+1;}else//第k小在pivot的左边部分{r=j-1;}}}测试结果输入较小的序列数：输入较大的序列数：不输出数组数只输出结果比较：附录：完整代码（随机化算法）Sherwood.cpp//随机化算法线性时间选择输入预处理洗牌#includeRandomNumber.h#includeiostream#includetime.h#includeiomanipusingnamespacestd;templateclassType实验分析在Sherwood型线性时间选择算法中，有两种实现方法，一种是随机划分基准；一种是随机洗牌预处理。随机划分基准处理如下：随机洗牌预处理如下：if(l=r)templateclassType{returna[l];}voidShuffle(Typea[],intn)inti=l,{//随机数类//随机选择划分基准staticRandomNumberrnd;j=l+rnd.Random(r-l+1);for(inti=0;in;i++)Swap(a[i],a[j]);{//随机生成i~n之间的整数j=r+1;intj=rnd.Random(n-i)+i;//随机选取的数作为基准值Typepivot=a[l];Swap(a[i],a[j]);}}我们可以看出一种是随机对于基准的选择，并不会影响原来的序列，可是有时所给的确定性算法无法直接改造成舍伍德型算法，所以我们就采用一种预处理的技术，将序列重新洗牌，排序，从而得到的第一种一样的结果，所以两种方法实现的功能是一样的额，都达到了使得最差情况与最好的情况的差距，在做题的时候根据不同算法的不同选择不同的方式。实验心得这一章的随机化算法其基本特点就是对所求解问题的同一实例用同一随机化算法求解两次可能得到完全不同的效果。这种算法大概是一种辅助性算法，其目的是改善其他确定性算法的性能。这种随机处理的方法，在平时的算法的设计中用到会很多次，利用随机生成函数，可是之前并没有怎么在意过，也没有具体去了解它的实现怎样的样，不过通过这一种的学习，才将这种随机化算法弄明白到底是怎样的，也学到了以后再算法设计上要是想要提高算法的功能有一些什么样的改善方法。实验得分助教签名Typeselect(Typea[],intl,intr,intk);//声明选出要选择的元素的函数templateclassType//声明判断是否越界的函数Typeselect(Typea[],intn,intk);templateclassType//声明洗牌算法函数ShufflevoidShuffle(Typea[],intn);templateclassType//声明交换函数inlinevoidSwap(Type&a,Type&b);voidran(int*input,intn)//随机生成数组元素函数{inti;srand(time(0));for(i=0;in;i++)input[i]=rand()%100;//生成的数据在0~100之间input[i]='\0';}intmain(){intn;cout输入元素个数：;cinn;int*a=newint[n+1];cout原数组为：endl;ran(a,n);//随机生成数组for(inti=0;in;i++){couta[i];}coutendl;Shuffle(a,n);//洗牌，将原有的输入进行随机洗牌cout洗牌后数组为：endl;for(inti=0;in;i++){couta[i];}coutendl;clock_tstart,end,over;//计算程序运行时间的算法start=clock();end=clock();over=end-start;start=clock();//选出序列中的最大值元素cout所给数组的最大值为：select(a,n,n)endl;//选出序列中的最小值元素cout所给数组的最小值为：select(a,n,1)endl;end=clock();printf(Thetimeis%6.3f,(double)(end-start-over)/CLK_TCK);//显示运行时间coutendl;system(pause);return0;}//计算a[0:n-1]中第k小元素//假设a[n]是一个键值无穷大的元素templateclassTypeTypeselect(Typea[],intn,intk){if(k1||kn){cout请输入正确的k!endl;return0;}returnselect(a,0,n-1,k);//如果输入合法则进行选择，找出要求的解}//计算a[l:r]中第k小元素templateclassTypeTypeselect(Typea[],intl,intr,intk){while(true){if(l=r)//此种情况表示只有一个元素{returna[l];}inti=l;intj=r+1;Typepivot=a[l];//轴值每次都选择最左边的元素//以划分基准为轴做元素交换while(true){//将pivot的元素换到轴值左边//将pivot的元素换到轴值右边while(a[++i]pivot);while(a[--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+1k)//第k小在pivot的右边部分{k=k-j+l-1;//右侧：k-(j-l+1)=k-j+l-1l=j+1;}else//第k小在pivot的左边部分{r=j-1;}}}templateclassTypeinlinevoidSwap(Type&a,Type&b){Typetemp=a;a=b;b=temp;}//随机洗牌算法templateclassTypevoidShuffle(Typea[],intn){staticRandomNumberrnd;//随机数类for(inti=0;in;i++){intj=rnd.Random(n-i)+i;//随机生成i~n之间的整数Swap(a[i],a[j]);//随机选取的数作为基准值}}RandomNumber.h#includetime.hconstunsignedlongmaxshort=65536L;constunsignedlongmultiplier=1194211693L;constunsignedlongadder=12345L;classRandomNumber//定义一个随机数类{private://当前种子unsignedlongrandSeed;public://构造函数，默认值表示由系统自动生产种子RandomNumber(unsignedlongs=0);unsignedshortRandom(unsignedlongn);//产生0~n-1之间的随机整数doublefRandom(void);//产生[0,1)之间的随机实数};RandomNumber::RandomNumber(unsignedlongs)//产生种子{if(s==0){randSeed=time(0);//用系统时间产生种子}else{randSeed=s;//由用户提供种子}}//产生0~n-1之间的随机整数unsignedshortRandomNumber::Random(unsignedlongn){randSeed=multiplier*randSeed+adder;//线性同余式return(unsignedshort)((randSeed16)%n);}doubleRandomNumber::fRandom(void)//产生[0,1)之间的随机实数{returnRandom(maxshort)/double(maxshort);}