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

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

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

3、al:r中第k小元素 template Type select(Type a,int l,int r,int k) while(true) if(l=r) /此种情况表示只有一个元素 return al; int i = l; int j = r+1; Type pivot = al; /轴值每次都选择最左边的元素 /以划分基准为轴做元素交换 while(true) /将pivot的元素换到轴值右边 while(a+ipivot); if(i=j) break; Swap(ai,aj); if(j-l+1 = k)/如果轴值是要选的元素即第k小 return pivot; /如果轴值不是要选的

4、元素 /aj必然小于等于pivot,做最后一次交换，满足左侧比pivot小，右侧比pivot大 al = aj; aj = pivot; /对子数组重复划分过程 if(j-l+1=r) template return al; void Shuffle(Type a,int n) int i = l, /随机数类/随机选择划分基准 static RandomNumber rnd; j = l + rnd.Random(r-l+1); for(int i=0; in; i+) Swap(ai,aj); /随机生成in之间的整数j = r+1; int j = rnd.Random(n-i)+i;

5、/随机选取的数作为基准值 Type pivot = al; Swap(ai,aj); 我们可以看出一种是随机对于基准的选择，并不会影响原来的序列，可是有时所给的确定性算法无法直接改造成舍伍德型算法，所以我们就采用一种预处理的技术，将序列重新洗牌，排序，从而得到的第一种一样的结果，所以两种方法实现的功能是一样的额，都达到了使得最差情况与最好的情况的差距，在做题的时候根据不同算法的不同选择不同的方式。实验心得这一章的随机化算法其基本特点就是对所求解问题的同一实例用同一随机化算法求解两次可能得到完全不同的效果。这种算法大概是一种辅助性算法，其目的是改善其他确定性算法的性能。这种随机处理的方法，在平时

6、的算法的设计中用到会很多次，利用随机生成函数，可是之前并没有怎么在意过，也没有具体去了解它的实现怎样的样，不过通过这一种的学习，才将这种随机化算法弄明白到底是怎样的，也学到了以后再算法设计上要是想要提高算法的功能有一些什么样的改善方法。实验得分助教签名附录：完整代码（随机化算法）Sherwood.cpp/随机化算法 线性时间选择 输入预处理 洗牌 #include RandomNumber.h #include #include#includeusing namespace std; template Type select(Type a,int l,int r,int k); /声明选出要选

7、择的元素的函数 template /声明判断是否越界的函数Type select(Type a,int n,int k); template /声明洗牌算法函数Shufflevoid Shuffle(Type a,int n); template /声明交换函数inline void Swap(Type &a,Type &b); void ran(int *input,int n) /随机生成数组元素函数int i;srand(time(0);for(i=0;in;i+)inputi=rand()%100; /生成的数据在0100之间inputi=0; int main() int n;cou

8、tn; int *a=new intn+1; cout原数组为：endl; ran(a,n); /随机生成数组 for(int i=0; in; i+) coutai ; coutendl; Shuffle(a,n);/洗牌，将原有的输入进行随机洗牌 cout洗牌后数组为：endl; for(int i=0; in; i+) coutai ; coutendl; clock_t start,end,over; /计算程序运行时间的算法start=clock();end=clock();over=end-start;start=clock();/选出序列中的最大值元素cout所给数组的最大值为：

9、select(a,n,n)endl;/选出序列中的最小值元素cout所给数组的最小值为：select(a,n,1)endl;end=clock();printf(The time is %6.3f,(double)(end-start-over)/CLK_TCK); /显示运行时间coutendl;system(pause); return 0; /计算a0:n-1中第k小元素 /假设an是一个键值无穷大的元素 template Type select(Type a,int n,int k) if(kn) cout请输入正确的k!endl; return 0; return select(a,

10、0,n-1,k); /如果输入合法则进行选择，找出要求的解 /计算al:r中第k小元素 template Type select(Type a,int l,int r,int k) while(true) if(l=r) /此种情况表示只有一个元素 return al; int i = l; int j = r+1; Type pivot = al; /轴值每次都选择最左边的元素 /以划分基准为轴做元素交换 while(true) /将pivot的元素换到轴值右边 while(a+ipivot); if(i=j) break; Swap(ai,aj); if(j-l+1 = k) /如果轴值是

11、要选的元素即第k小 return pivot; /如果轴值不是要选的元素 /aj必然小于等于pivot,做最后一次交换，满足左侧比pivot小，右侧比pivot大 al = aj; aj = pivot; /对子数组重复划分过程 if(j-l+1k) /第k小在pivot的右边部分 k = k-j+l-1;/右侧：k-(j-l+1)=k-j+l-1 l = j + 1; else /第k小在pivot的左边部分 r = j - 1; template inline void Swap(Type &a,Type &b) Type temp = a; a = b; b = temp; /随机洗牌算法 temp