舍伍德线性时间选择

1、一个算法的优劣可以用（时间复杂度）与（空间复杂度）与来衡量。

2、回溯法在问题的解空间中，按（深度优先方式）从根结点出发搜索解空间树。

3、直接或间接地调用自身的算法称为（递归算法）。

4、 记号在算法复杂性的表示法中表示（渐进确界或紧致界）。

5、在分治法中，使子问题规模大致相等的做法是出自一种（平衡(banlancing)子问题）的思想。

6、动态规划算法适用于解（具有某种最优性质）问题。

7、贪心算法做出的选择只是（在某种意义上的局部）最优选择。

8、最优子结构性质的含义是（问题的最优解包含其子问题的最优解）。

9、回溯法按（深度优先）策略从根结点出发搜索解空间树。

10、拉斯维加斯算法找到的解一定是（正确解）。

11、按照符号O的定义O(f)+O(g)等于O(max{f(n),g(n)})。

12、二分搜索技术是运用（分治）策略的典型例子。

13、动态规划算法中，通常不同子问题的个数随问题规模呈（多项式）级增长。

14、（最优子结构性质）和（子问题重叠性质）是采用动态规划算法的两个基本要素。

15、（最优子结构性质）和（贪心选择性质）是贪心算法的基本要素。

16、（选择能产生最优解的贪心准则）是设计贪心算法的核心问题。

17、分支限界法常以（广度优先）或（以最小耗费(最大效益)优先）的方式搜索问题的解空间树。

18、贪心选择性质是指所求问题的整体最优解可以通过一系列（局部最优）的选择，即贪心选择达到。

19、按照活结点表的组织方式的不同，分支限界法包括（队列式(FIFO)分支限界法）和（优先队列式分支限界法）两种形式。

20、如果对于同一实例，蒙特卡洛算法不会给出两个不同的正确解答，则称该蒙特卡洛算法是（一致的）。

21、哈夫曼编码可利用（贪心法）算法实现。

22概率算法有数值概率算法，蒙特卡罗（Monte Carlo）算法，拉斯维加斯（Las Vegas）算法和舍伍德（Sherwood）算法23以自顶向下的方式求解最优解的有（贪心算法）24、下列算法中通常以自顶向下的方式求解最优解的是（C）。

算法分析线性时间选择复杂度分析第二组：袁瑾(计科1304：201308010410)，欧阳玉峰（计科1304:201308080216），程帆瑾（物联1302:201378010206）。

一、问题描述：给一个线性序列，要求在一个平均时间线性的情况下进行第k小元素的选择。

二、方法一：模仿快速排序的方法对输入序列进行递归划分，但只对划分出的子数组之一进行递归处理。

代码如下：RandomizedSelect(a, p, r, k):if p==r :return a[p]i = RandomizedPartition(a,p,r)j = i-p+1if k<=j :return RandomizedSelect(a,p,i,k)return RandomizedSelect(a,i+1,r,k-j)三、方法一时间复杂度：先从上边的函数说起。

其实质是模拟一个快速排序的过程。

快速排序是随机选择一个轴值，然后比轴值小的排在左边，比轴值大的排在右边。

上边的函数四个参数a,p,r,k。

a是数组的参数，p是数组开始元素的下标，r的数组结束的下标。

k是找第k小的元素。

每次划分所需要的时间是O(n),此时每个元素需要和轴值进行比较一次。

所以最好的情况是选完轴值一次快排后，左边刚好有k-1个元素，则此时轴值则是第k小元素。

而一般情况是，轴值左边有m个元素，m<k时，在右边找第k-m小的元素，m>k时，在左边找第k小的元素。

平均复杂度是O(n)。

最坏的情况是轴值每次选的都是刚好最大的元素或者最小的元素，此时时间复杂度是O(n*k)。

四.方法二：能在线性时间内找到一个划分基准，使得按照这个基准所划分出的两个子数组长度都至少为元数组长度的 m 倍：Select(a, p, r, k):if r-p<MG :sort(a[p:r])return a[p+k-1]for i in 0...(r-p-4)/5 :将a[p+5*i]...a[p+5*i+4]的第3小元素与a[p+i]交换x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10)i=Partition(a,p,r,x)j=i-p+1if k<=j :return Select(a,p,i,k)return Select(a,i+1,r,k-j)五、算法及其复杂度分析：⌊3(n-5)/10⌋⌈n/5⌉<1> 将所有的数n个以每5个划分为一组共⌈n/5⌉组，将不足5个的那组忽略，然后用任意一种排序算法，因为只对5个数进行排序，所以任取一种排序法就可以了。

算法实验报告——线性时间选择问题实验五线性时间选择问题年级16 学号飞宇成绩专业信息安全实验地点C1-413 指导教师丽萍实验⽇期⼀、实验⽬的1、理解分治法的基本思想2、掌握分治法解决问题的基本步骤，并能进⾏分治算法时间空间复杂度分析。

⼆、实验容线性时间选择问题：给定线性序集中n个元素和⼀个整数k（k>=1⽽且k<=n），要求在线性时间找出这n个元素中第k⼩的元素。

1.随机快速排序2.利⽤中位数线性时间选择三、算法描述1.随机快速排序在算法Randomized_Select中执⾏Randomized_Partition，将数组分成两个⼦数组，在Randomized_Partition中调⽤Partition 函数确定⼀个基准元素，对数组进⾏划分。

由于划分是随机产⽣的，由此导致算法Randomized_Select也是⼀个随机化算法。

2.利⽤中位数线性时间选择四、程序1.随机快速排序#include#include#includeint Randomized_Select(int a[],int p,int r,int i);int Randomized_Partition(int a[],int p,int r);int Partition(int a[],int p,int r);void swap(int *a,int *b);int Random(int p,int q);int main(){int a[] = {10,9,8,7,6,5,4,3,2,1};int i = 3;printf("第%d⼩的数是:\n%d",i,Randomized_Select(a,0,9,i));return 0;}{int temp;temp = *a;*a = *b;*b = temp;}int Random(int p,int q)//产⽣p和q之间的⼀个随机整数{int i,number;srand((unsigned)time(NULL));number = rand()%(q-p+1)+p;return number;}int Partition(int a[],int p,int r)//快排的部分{int x = a[r];int i = p- 1;int j;for(j = p;j<=r-1;j++){if(a[j] <= x){i = i + 1;swap(&a[j],&a[i]);}}swap(&a[i+1],&a[r]);return i+1;}int Randomized_Partition(int a[],int p,int r)//随机交换数字{int i = Random(p,r);swap(&a[r],&a[i]);return Partition(a,p,r);int Randomized_Select(int a[],int p,int r,int i)//选择算法核⼼{if(p == r) return a[p];int q = Randomized_Partition(a,p,r);int k = q - p + 1;if(i == k)//如果刚好等于i，输出return a[q];else if(i < k)//如果i⽐k⼩，证明要找的元素在低区return Randomized_Select(a,p,q-1,i);else //找的元素在⾼区return Randomized_Select(a,q+1,r,i-k); //因为a[q]已经是前⾯第k个⼩的，所以在后⾯就是i-k⼩}2. 利⽤中位数线性时间选择#include#include#include#includeusing namespace std;templatevoid Swap(Type &x,Type &y);inline int Random(int x, int y);templatevoid BubbleSort(Type a[],int p,int r);templateint Partition(Type a[],int p,int r,Type x);templateType Select(Type a[],int p,int r,int k);int main(){//初始化数组int a[10];//必须放在循环体外⾯srand((unsigned)time(0));for(int i=0; i<10; i++)a[i] = Random(0,50);cout<<"a["<}cout<cout<<"第3⼩元素是"<//重新排序，对⽐结果BubbleSort(a,0,9);for(int i=0; i<10; i++){cout<<"a["<}cout<}templatevoid Swap(Type &x,Type &y){Type temp = x;x = y;y = temp;}inline int Random(int x, int y){int ran_num = rand() % (y - x) + x; return ran_num;}//冒泡排序templatevoid BubbleSort(Type a[],int p,int r) {//记录⼀次遍历中是否有元素的交换bool exchange;for(int i=p; i<=r-1;i++){exchange = false ;{if(a[j]{Swap(a[j],a[j-1]);exchange = true;}}//如果这次遍历没有元素的交换,那么排序结束if(false == exchange){break ;}}}templateint Partition(Type a[],int p,int r,Type x){int i = p-1,j = r + 1;while(true){while(a[++i]while(a[--j]>x);if(i>=j){break;}Swap(a[i],a[j]);}return j;}templateType Select(Type a[],int p,int r,int k){if(r-p<75)BubbleSort(a,p,r);return a[p+k-1];}//(r-p-4)/5相当于n-5for(int i=0; i<=(r-p-4)/5; i++){//将元素每5个分成⼀组，分别排序，并将该组中位数与a[p+i]交换位置//使所有中位数都排列在数组最左侧，以便进⼀步查找中位数的中位数BubbleSort(a,p+5*i,p+5*i+4);Swap(a[p+5*i+2],a[p+i]);}//找中位数的中位数Type x = Select(a,p,p+(r-p-4)/5,(r-p-4)/10);int i = Partition(a,p,r,x);int j = i-p+1;if(k<=j){return Select(a,p,i,k);}else{return Select(a,i+1,r,k-j);}}五、测试与分析1.随机快速排序O(n)2.利⽤中位数线性时间选择O(n)。

计算机算法与设计复习题(含答案)1、一个算法的优劣可以用与与来衡量。

2、回溯法在问题的解空间中，按从根结点出发搜索解空间树。

3、直接或间接地调用自身的算法称为。

4、记号在算法复杂性的表示法中表示。

5、在分治法中，使子问题规模大致相等的做法是出自一种。

可以解决背包问题28、投点法是的一种。

29、若线性规划问题存在最优解，它一定不在30、n皇后问题可以用解决。

31、若L是一个NP完全问题，L经过多项式时间变换后得到问题l，则l是( P类问题 ).32、算法与程序在性质上有所不同，下列性质中，程序可以不满足哪个性质：。

案。

对；8）动态规划算法是用于解最优化问题，采用自顶向下的方式计算出最优解。

错；9）贪心算法和动态规划算法都要求问题必须具有最优子结构性质和贪心选择性质。

错； 10）队列式分支限界法将活结点表组织成一个优先队列，并按队列的先进现出原则选取下一个结点称为当前扩展结点。

错；四、算法设计说明：任意选择所使用的算法策略；要求：说问题）的思想。

6、动态规划算法适用于解问题。

7、贪心算法做出的选择只是最优选择。

8、最优子结构性质的含义是。

9、回溯法按策略从根结点出发搜索解空间树。

10、拉斯维加斯算法找到的解一定是。

11、按照符号O的定义O(f)+O(g)等于O(max{f(n),g(n)})。

12、二分搜索技术是运用策略的典型例子。

13、动态规划算法中，通常不同子问题的个数随问题规模呈级增长。

14、和是采用动态规划算法的两个基本要素。

15、和是贪心算法的基本要素。

16、是设计贪心算法的核心问题。

17、分支限界法常以或的方式搜索问题的解空间树。

18、贪心选择性质是指所求问题的整体最优解可以通过一系列的选择，即贪心选择达到。

19、按照活结点表的组织方式的不同，分支限界法包括和两种形式。

20、如果对于同一实例，蒙特卡洛算法不会给出两个不同的正确解答，则称该蒙特卡洛算法是。

21、哈夫曼编码可利用算法实现。

问题描述如果用有序链表来表示一个含有n个元素的有序集S，则在最坏情况下，搜索S中一个元素需要O(n)计算时间。

提高有序链表效率的一个技巧是在有序链表的部分结点处增设附加指针以提高其搜索性能。

在增设附加指针的有序链表中搜索一个元素时，可借助于附加指针跳过链表中若干结点，加快搜索速度。

这种增加了向前附加指针的有序链表称为跳跃表。

应在跳跃表的哪些结点增加附加指针以及在该结点处应增加多少指针完全采用随机化方法来确定。

这使得跳跃表可在O(logn)平均时间内支持关于有序集的搜索、插入和删除等运算。

例如：如图，(a)是一个没有附加指针的有序表，而图(b)在图(a)的基础上增加了跳跃一个节点的附加指针。

图(c)在图(b)的基础上又增加了跳跃3个节点的附加指针。

在跳跃表中，如果一个节点有k+1个指针，则称此节点为一个k级节点。

以图(c)中跳跃表为例，看如何在改跳跃表中搜索元素8。

从该跳跃表的最高级，即第2级开始搜索。

利用2级指针发现元素8位于节点7和19之间。

此时在节点7处降至1级指针进行搜索，发现元素8位于节点7和13之间。

最后，在节点7降至0级指针进行搜索，发现元素8位于节点7和11之间，从而知道元素8不在搜索的集合S中。

相关原理在一般情况下，给定一个含有n个元素的有序链表，可以将它改造成一个完全跳跃表，使得每一个k级结点含有k+1个指针，分别跳过2^k-1，2^(k-1)-1，…，2^0-1个中间结点。

第i个k级结点安排在跳跃表的位置i2^k处，i>=0。

这样就可以在时间O(logn)内完成集合成员的搜索运算。

在一个完全跳跃表中，最高级的结点是级结点。

完全跳跃表与完全二叉搜索树的情形非常类似。

它虽然可以有效地支持成员搜索运算，但不适应于集合动态变化的情况。

集合元素的插入和删除运算会破坏完全跳跃表原有的平衡状态，影响后继元素搜索的效率。

为了在动态变化中维持跳跃表中附加指针的平衡性，必须使跳跃表中k级结点数维持在总结点数的一定比例范围内。

递归分治---例题5.线性时间选择⼀.问题描述给定线性序列集中的n个元素和正整数k, 1≤ k≤ n, 求第k⼩元素的位置.⼆.解题思路该篇⽂章中我们讨论与排序问题类似的元素选择问题,元素选择问题的⼀般提法是:给定线性序集合中n个元素和⼀个整数k(1 <= k <= n),要求找出这n个元素中第k⼩的元素,即如果将这n个元素依其线性排列数时,排在第k个位置的元素即为要找的元素.①最直观的解题⽅法:先排序,然后找到第k⼩的元素即可.这样时间复杂度⾄少是: O(n), 平均: O(nlogn)时间②随机选择算法:模仿快速排序对输⼊数组A进⾏⼆分划分,使⼦数组A1的元素<=A2中的元素,分点J由随机数产⽣,若K<=J,则K为A1的第K⼩元, 若K>J,则K为A2的第K-J⼩元.与快速排序算法不同,它只对⼦数组之⼀进⾏递归处理。

按照上⾯的思路,我们先⽤上篇⽂章说到过的随机选择算法来确定基准,从⽽对数组进⾏划分.代码描述:template<class T>int randomizedPartition(vector<T> &a, int p, int r) //在p:r中随机选择⼀个数i{srand(int(time(0))); //每次以当前时间作为随机数⽣成的种⼦int i = random(p, r);swap(a[i], a[p]); //将a[i]换到左端点return Partition(a, p, r);}Type RandomizedSelect(Type a[], int p, int r, int k){if(p == r) return a[p];int i = RandumizePartition(a, p, r); //使⽤了快速排序那篇⽂章中的RandomziedPartition随机划分算法j = i-p+1; //j为a[p:i]中的元素个数if(k <= j)return RandomizedSelect(a, p, i, k);elsereturn RandomizedSelect(a, i+1, r, k-j);}时间复杂度分析:若分点总是等分点,则有: Tmin(n) = dTmin(n) = T(n/2) + cn, 计算得到T(n) = θ(n)若⼀部分总是为空,则有: Tmax(n) = O(n^2)从上⾯可以看到,我们若果使⽤随机划分的话,最坏情况下,算法RandomizedSelect时间复杂度达到了O(n^2),例如,我们在找最⼩元素时,总是在最⼤元素处划分.尽管如此,该算法的性能还是可以的.随机选择算法的最佳情况即线性选择③线性时间选择算法(证明⽐较绕,可以直接记住结论:每次选择的基准为中位数的中位数,这样可以保证我们每次递归划分问题规模缩⼩1/4.当元素个数⼩于阈值的话,我们直接⽤sort排序)我们可以通过寻找⼀个好的划分基数,可使最坏情况下时间为O(n).下⾯我们来介绍⼀下如何划分可以达到⽬标,具体步骤如下:可以按以下步骤找到满⾜要求的划分基准,(「」表⽰向下取整,符号打不出来见谅.)将n个输⼊元素划分成「n/5」个组，每组5个元素，除可能有⼀个组不是5个元素外。

算法：线性时间选择（CC++）Description给定线性序集中n个元素和⼀个整数k，n<=2000000，1<=k<=n，要求找出这n个元素中第k⼩的数。

Input第⼀⾏有两个正整数n,k. 接下来是n个整数（0<=ai<=1e9）。

Output输出第k⼩的数Sample Input6 31 3 52 4 6Sample Output3利⽤快速排序可以找出第k⼩的，加上随机函数改进⼀下：#include <cstdio>#include <cstdlib>#include <ctime>#include <iostream>int num[2000001];void quictSort(int, int, int);int partition(int, int);int main(){int n, m, i;srand(unsigned(time(NULL))); // 随机函数种⼦while (~scanf("%d%d", &n, &m)){for (i = 0; i < n; i++)scanf("%d", &num[i]);quictSort(0, n - 1, m - 1);printf("%d\n", num[m - 1]);}return 0;}// 快速排序void quictSort(int left, int right, int mTop){if (left < right){int p = partition(left, right); // 分为两段if (p == mTop) // 如果随机找到第mTop⼩就直接返回return;if (p < mTop)quictSort(p + 1, right, mTop); // 找到的位置⽐mTop⼩就在[p + 1, right]区间找if (p > mTop)quictSort(left, p - 1, mTop); // 找到的位置⽐mTop⼤就在[left, p - 1]区间找}}// 从⼩到⼤排int partition(int left, int right){int r = rand() % (right - left + 1) + left; // 随机选择⼀个数int key = num[r];std::swap(num[r], num[left]); // 交换到数组⾸位while (left < right){// 从数组后⾯开始, 找⽐随机选择的数⼩的, 然后从前找⽐随机选择的数⼤的while (left < right && num[right] >= key)right--;if (left < right)num[left] = num[right];while (left < right && num[left] <= key)left++;if (left < right)num[right] = num[left];}num[left] = key; // 将随机选择的数存回return left; // 返回随机选择的数分割数组的下标, 左边都是⽐它⼩的, 右边都是⽐它⼤的}中位数法线性时间选择划分：AC代码：#include <cstdio>#include <cstdlib>int num[2000001];int select(int low, int high, int top);int partition(int low, int high, int median); void selectSort(int low, int high);void swap(int &a, int &b);int main(){int n, m, i;while (~scanf("%d%d", &n, &m)){for (i = 0; i < n; i++)scanf("%d", &num[i]);printf("%d\n", select(0, n - 1, m - 1));/*for (i = 0; i < n; i++)printf("%d%c", num[i], i < n - 1 ? ' ' : '\n'); */}return 0;}// 中位数法线性时间选择int select(int low, int high, int top){// ⼩于75个数据随便⽤⼀个排序⽅法if (high - low < 74){selectSort(low, high); // 选择排序return num[low + top]; // 排完序直接返回第low + top的数}int groupNum = (high - low - 4) / 5; // 每组5个数, 计算多少个组, 从0开始计数for (int i = 0; i <= groupNum; i++){int start = low + 5 * i; // 每组的起始位置int end = start + 4; // 每组的结束位置for (int j = 0; j < 3; j++) // 从⼩到⼤冒3个泡for (int k = start; k < end - j; k++)if (num[k] > num[k + 1])swap(num[k], num[k+1]);swap(num[low + i], num[start + 2]); // 每组的中位数交换到前⾯第low + i的位置}// 上⾯排完后, 数组low + 0 到 low + groupNum都是每⼀组的中位数int median = select(low, low + groupNum, (groupNum + 1) / 2); // 找中位数的中位数int p = partition(low, high, median); // 将数组分为两段, 左边的⼩于中位数的中位数, 右边的⼤于中位数的中位数 int n = p - low; // 计算p到low之间有多少个数, 后⾯得减掉if (n == top)return num[p]; // 如果运⽓好, 刚好要找的就是中位数if (n > top)return select(low, p - 1, top); // n⽐top⼤就在左边找if (n < top)return select(p + 1, high, top - n - 1); // n⽐top⼩就在右边找, 并且top要减去已经⼤的个数}// 以中位数进⾏分割, 分成两半int partition(int low, int high, int median){int p;for (int i = low; i <= high; i++)if (num[i] == median){p = i;break;}// 将中位数交换到最前⾯swap(num[p], num[low]);// 记下最前⾯的数int key = num[low];// 把⼩于key的放前⾯, ⼤于key的放后⾯while (low < high){while (num[high] >= key && low < high)high--;if (low < high)num[low] = num[high];while (num[low] <= key && low < high)low++;if (low < high)num[high] = num[low];}// 分别从两头开始, 找到中间时, 把key存回num[low] = key;return low;}// 选择排序void selectSort(int low, int high){for (int i = low; i <= high; i++){int MIN = i;for (int j = i + 1; j <= high; j++)if (num[MIN] > num[j])MIN = j;swap(num[i], num[MIN]);}}// 交换两个元素void swap(int &a, int &b){int temp = a;a = b;b = temp;}。

【算法导论】排序（四）：决策树、线性时间排序（计数、基数、桶排序）到⽬前为⽌，⼀共整理总结了五⼤排序算法：1、插⼊排序2、冒泡排序、选择排序、交换排序（把这三种⽅法归为⼀种，因为他们的思想本质上都是⼀样的）3、归并排序4、堆排序5、快速排序以上五种排序都可以称为“⽐较排序”，顾名思义，因为他们都是基于⽐较元素来决定其相对位置的。

其中前两种的时间为O（n^2），归并排序和堆排序最坏O( n lg n )，快排平均O( n lg n )定理：任意⼀种⽐较排序算法最坏情况下，都需要做Ω( n lg n )次的⽐较。

我们通过决策树来证明：●决策树（decision tree）⽐较排序可以被抽象的视为决策树。

撒⼀颗决策树是⼀颗满⼆叉树，表⽰某排序算法作⽤于给定输⼊元素所作的所有⽐较，⽽其它因素忽略。

假设有⼀组三个元素的序列,我们⽤1，2，3来分别表⽰这三个元素，我们基于⽐较来对它排序，可以有下列决策树：不难发现，判定树的叶⼦表⽰了三个元素的所有可能排列。

另外，⽤⽐较排序对这三个元素进⾏排序的话，你总可以找到⼀条路径来表⽰它的整个⽐较过程。

（需要注意的是，1并不表⽰它代表第⼀个元素，它可以代表三个元素中任意⼀个。

2，3也相同。

但是1，2，3不指向相同元素）。

显然最坏情况下的复杂度即是判定树的⾼。

对于⼀颗⾼度为H的、具有L个可达叶节点的决策树，它对应于对N个元素所作的⽐较排序。

因为N个元素有N！种排列（排列组合知识），每⼀种都作为⼀个叶⼦出现在书中，故有N!<=L(重要,注：)有⼜由于在⼀颗⾼为H的⼆叉树中，叶⼦的数⽬不多于2^H,则有N! <= L <= 2^H对该式⼦取对数,得到：H>=lg(N！) (因为lg函数时单调递增的)=Ω(N lg N)注：⼀开始我以为应该是等于的关系，后来百度了⼀下，原⽂有这⼀句：Because each of the N! permutation appears as areachable leaf. 作者的意思着重于⽤N！来表⽰N个元素的所有可能排列，但是N个元素的所有可能排列实际上是⼩于等于N！的，因为在N个元素中有可能有相等的元素。

线性时间选择一．实验目的：1.理解算法设计的基本步骤和各步的主要内容、基本要求；2.加深对递归设计方法基本思想的理解，并利用其解决现实生活中的问题；3.通过本次试验初步掌握将算法转化为计算机上机程序的方法。

二．实验内容：1.编写实现算法：给定n个元素，在这n个元素中找到第key小的元素；2.将输入的数据存储到指定的文本文件中，而输出数据存放到另一个文本文件中，包括结果和具体的运行时间；3.对实验结果进行分析。

三．实验操作：1.线性时间选择的思想：首先将这n个元素分成5组，利用排序算法找到其中的中位数，再将这些中位数排序找到整个数组的中位数median，以这个中位数median为界限，将整个数组划分为三部分，小于median，等于median和大于median三部分，判断key在哪部分中，对那部分进行递归调用，直到找到等于key的元素为止。

综上判断，其时间复杂度为：T(n)<=cn（n为实验数据的个数），故为线性时间。

2.快速排序：本次排序使用的是快速排序，快速排序是一种相对较快的排序方式，能够减少一定的时间开销。

代码实现：void quickSort(int List[],int low,int high){if(low>=high) return;int first=low;int last=high;int key=List[first];while(first<last){while(first<last&&List[last]>=key) --last;List[first]=List[last];while(first<last&&List[first]<=key) ++first;List[last]=List[first];}List[first]=key;quickSort(List,low,first-1);quickSort(List,last+1,high);}3.实验数据的输入：为了保证实验数据的随机性，本实验采用随机生成的方式提供数据，并将输入输出数据存储到指定的文本文件中，需要采用C++文件流操作，对于数据的输入，由于cin对数据的读取会忽略空格和换行操作，故使用cin流来控制数据的输入。

《算法分析与设计》作业（一）本课程作业由两部分组成。

第一部分为“客观题部分”，由15个选择题组成，每题1分，共15分。

第二部分为“主观题部分”，由简答题和论述题组成，共15分。

作业总分30分，将作为平时成绩记入课程总成绩。

客观题部分：一、选择题（每题1分，共15题）1、递归算法：（C ）A、直接调用自身B、间接调用自身C、直接或间接调用自身D、不调用自身2、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题，这些子问题：（D ）A、相互独立B、与原问题相同C、相互依赖D、相互独立且与原问题相同3、备忘录方法的递归方式是：（C ）A、自顶向下B、自底向上C、和动态规划算法相同D、非递归的4、回溯法的求解目标是找出解空间中满足约束条件的：（A ）A、所有解B、一些解C、极大解D、极小解5、贪心算法和动态规划算法共有特点是：（ A ）A、最优子结构B、重叠子问题C、贪心选择D、形函数6、哈夫曼编码是：（B）A、定长编码B、变长编码C、随机编码D、定长或变长编码7、多机调度的贪心策略是：（A）A、最长处理时间作业优先B、最短处理时间作业优先C、随机调度D、最优调度8、程序可以不满足如下性质：（D ）A、零个或多个外部输入B、至少一个输出C、指令的确定性D、指令的有限性9、用分治法设计出的程序一般是：（A ）A、递归算法B、动态规划算法C、贪心算法D、回溯法10、采用动态规划算法分解得到的子问题：（ C ）A、相互独立B、与原问题相同C、相互依赖D、相互独立且与原问题相同11、回溯法搜索解空间的方法是：（A ）A、深度优先B、广度优先C、最小耗费优先D、随机搜索12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法：（ C ）A、所需时间变化B、一定找到解C、找不到所需的解D、性能变差13、贪心算法能得到：（C ）A、全局最优解B、0-1背包问题的解C、背包问题的解D、无解14、能求解单源最短路径问题的算法是：（A ）A、分支限界法B、动态规划C、线形规划D、蒙特卡罗算法15、快速排序算法和线性时间选择算法的随机化版本是：（ A ）A、舍伍德算法B、蒙特卡罗算法C、拉斯维加斯算法D、数值随机化算法主观题部分：二、写出下列程序的答案（每题2.5分，共2题）1、请写出批处理作业调度的回溯算法。

一、算法设计实例1、快速排序（分治法）int partition(float a[],int p,int r) {int i=p,j=r+1;float x=a[p];while(1){while(a[++i]<x);while(a[--j]<x);if(i>=j)break;swap(a[i],a[j]);}a[p]=a[j];a[j]=x;return j;}void Quicksort(float a[],int p,int r){//快速排序if(p<r){int q=partition(a,p,r);Quicksort(a,p,q-1);Quicksort(a,p+1,r);}}2、归并排序（分治法）void mergesort(Type a[],int left,int right) {if(left<rigth){int mid=(left+right)/2;//取中点mergesort(a,left,mid);mergesort(a,mid+1,right);mergesort(a,b,left,right);//合并到数组bmergesort(a,b,left,right);//复制到数组a}}3、背包问题（贪心算法）void knapsack(int n,float m,float v[],float w[],float x[]) {sort(n,v,w)//非递增排序int i;for(i=1;i<=n;i++)x[i]=0;float c=m;for(i=1;i<=n;i++){if(w[i]>c)break;x[i]=1;c-=w[i];}if(i<=n)x[i]=c/w[i];}4、活动安排问题（贪心算法）void Greadyselector(int n,Type s[],Type f[],bool A[]) {//s[i]为活动结束时间，f[j]为j活动开始时间A[i]=true;int j=1;for(i=2;i<=n;i++){if(s[i]>=f[j]){A[i]=true;j=i;}elseA[i]=false;}}5、喷水装置问题（贪心算法）void knansack(int w,int d,float r[],int n){//w为草坪长度d为草坪宽度r[]为喷水装置的喷水半径，//n为n种喷水装置，喷水装置的喷水半径>=d/2sort(r[],n);//降序排序count=0;//记录装置数for(i=1;i<=n;i++)x[i]=0;//初始时，所有喷水装置没有安装x[i]=0for(i=1;w>=0;i++){x[i]=1;count++;w=w-2*sqart(r[i]*r[i]-1);}count<<装置数:<<count<<end1;for(i=1;i<=n;i++)count<<喷水装置半径：<<r[i]<<end1;}6、最优服务问题（贪心算法）double greedy(rector<int>x,int s){rector<int>st(s+1,0);rector<int>su(s+1,0);int n=x.size();//st[]是服务数组，st[j]为第j个队列上的某一个顾客的等待时间//su[]是求和数组，su[j]为第j个队列上所有顾客的等待时间sort(x.begin(),x.end());//每个顾客所需要的服务时间升序排列int i=0,j=0;while(i<n){st[j]+=x[i];//x[i]=x.begin-x.endsu[j]+=st[j];i++;j++;if(j==s)j=0;}double t=0;for(i=0;i<s;i++)t+=su[i];t/=n;return t;}7、石子合并问题（贪心算法）float bebig(int A[],int n) {m=n;sort(A,m);//升序while(m>1){for(i=3;i<=m;i++)if(p<A[i])break;elseA[i-2]=A[i];for(A[i-2]=p;i<=m;i++){A[i-1]=A[i];m--;}}count<<A[1]<<end1}8、石子合并问题（动态规划算法）best[i][j]表示i-j合并化最优值sum[i][j]表示第i个石子到第j个石子的总数量|0f(i,j)=||min{f(i,k)+f(k+1,j)}+sum(i,j)int sum[maxm]int best[maxm][maxn];int n,stme[maxn];int getbest();{//初始化，没有合并for(int i=0;i<n;i++)best[i][j]=0;//还需要进行合并for(int r=1;r<n;r++){for(i=0;i<n-r;i++){int j=i+v;best[i][j]=INT-MAX;int add=sum[j]-(i>0!sum[i-1]:0);//中间断开位置，取最优值for(int k=i;k<j;++k){best[i][j]=min(best[i][j],best[i][k]+best[k+1][j])+add;}}}return best[0][n-1];}9、最小重量机器设计问题（回溯法）typedef struct Qnode{float wei;//重量float val;//价格int ceng;//层次int no;//供应商struct Qnode*Parent;//双亲指针}Qnode;float wei[n+1][m+1]=;float val[n+1][m+1]=;void backstack(Qnode*p){if(p->ceng==n+1){if(bestw>p->wei){testw=p->wei;best=p;}}else{for(i=1;i<=m;i++)k=p->ceng;vt=p->val+val[k][i];wt=p->wei+wei[k][i];if(vt<=d&&wt<=bestw){s=new Qnode;s->val=vt;s->wei=wt;s->ceng=k+1;s->no=1;s->parent=p;backstrack(S);}}}10、最小重量机器设计问题（分支限界法）typedef struct Qnode{float wei;//重量float val;//价格int ceng;//层次int no;//供应商struct Qnode*Parent;//双亲指针}Qnode;float wei[n+1][m+1]=;float val[n+1][m+1]=;void minloading(){float wt=0;float vt=0;float bestw=Max;//最小重量Qnode*best;s=new Qnode;s->wei=0;s->val=0;s->ceng=1;s->no=0;s->parent=null;Iinit_Queue(Q); EnQueue(Q,S);do{p=OutQueue(Q);//出队if(p->ceng==n+1){if(bestw>p->wei){bestw=p->wei;best=p;}}else{for(i=1;i<=m;i++){k=p->ceng;vt=p->val+val[k][i];wt=p->wei+wei[k][i];if(vt<=d&&wt<=bestw){s=new Qnode;s->ceng=k+1;s->wt=wt;s->val=val;s->no=i;s->parent=p;EnQueue(Q,S);}}}}while(!empty(Q));p=best;while(p->parent){count<<部件：<<p->ceng-1<<end1;count<<供应商：<<p->no<<end1;p=p->parent;}}11、快速排序（随机化算法—舍伍德算法）int partion(int a[],int l,int r){key=a[l];int i=l,j=r;while(1){while(a[++i]<key&&i<=r);while(a[--j]>key&&j>=l);if(i>=j)break;if(a[i]!=a[j])swap(a[i],a[j]);}if((j!=l)&&a[l]!=a[j])swap(a[l],a[j]);return j;}int Ranpartion(int a[],int l,int r) {k=rand()%(r-1+l)+1;swap(a[k],a[l]);int ans=partion(a,l,r);return ans;}int Quick_sort(int a[],int l,int r,int k){int p=Randpartion(a,l,r);if(p==k)return a[k];else if(k<p)return Quick_sort(a,l,p-1,k);else{int j=0;for(int i=p+1;i<=r;i++)b[j++]=a[i]return Quick_sort(b,1,j,k-p);}}12、线性选择（随机化算法—舍伍德算法）二、简答题1．分治法的基本思想分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。

线性时间选择问题的教学探讨作者：陈晓梅胡春花来源：《电脑知识与技术》2016年第23期摘要：针对线性时间选择问题，分别对一般情况下的算法思路和最坏情况下的算法思路进行介绍，结合教学过程和特点，通过增加递归调用的结束条件、无需改造划分函数而直接调用以及对相同划分元素进行集中排列等，对算法进行了优化和改进，增强了算法的连贯性和适用性，使学生更加直观深刻地理解和应用线性时间选择问题的算法，收到较好的教学效果。

关键词：线性时间选择；最坏情况；基准元素；划分中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2016）21-0087-021 线性时间选择问题描述给定 n 个元素的集合，集合中的第 k 个顺序统计量是指集合中的第k 个（1≤k≤n）最小元素。

当k=1时，指集合中的最小元素；当k=n时，指集合中的最大元素。

如何从给定的集合中找出第 k 个最小元素，被称为元素选择问题。

线性时间选择问题是指在线性时间内实现元素选择。

该问题在大规模数据检索和人工智能搜索方面有广泛的应用。

同时该问题也是分治算法教学中的一个典型例子。

2 实现线性时间选择的典型分治算法2.1 一般性选择问题的分治算法对于一般的选择问题，可使用RandomizedSelect（a，p，r，k）实现在期望情况下对数组a[p：r]在线性时间内选出第k小的元素。

教材中的函数描述如下：RandomizedSelect（）函数中引入随机划分函数RandomizedPartition（p，r）对数组a[p：r]进行划分，该函数以a[p：r]中的一个随机元素作为划分基准，将原数组划分为两个子数组a[p：i]和a[i+1：r]，使得第一个子数组中的所有元素全小于等于第二个子数组中的所有元素。

通过RandomizedPartition（）函数的返回值i可以计算出第一个子数组的元素个数j，根据j值与k值的大小比较，可以判断出所要求的第k小的元素是落在哪个子数组，从而继续递归调用RandomizedSelect（）函数对缩小了查找范围的子数组进行查找。

经典算法总结之线性时间做选择问题：输⼊：⼀个包含n个(不同的)数的集合A和⼀个数i， 1 <= I <= n。

输出：元素x∈A，它恰⼤于A中其他的I – 1个元素（即求第k⼩数）。

本博⽂中这篇⽂章也⽤了本⽂中的算法，⼤家可以参考。

三种算法：1、直接排序，输出数组第i个元素即可, 时间复杂度为O(nlgn)2、这种算法，利⽤“快排的或者类似⼆分”的思想，每次以枢纽为界，分两边，每次只需处理⼀边即可（抛弃另⼀边），平均情况下的运⾏时间界为O(n)，这种算法以期望时间做选择。

《算法都论》⾥是，在分治时⽤随机数来选取枢纽（算法导论中伪代码见图），好吧，这是理论上的算法，它没有考虑实际产⽣随机数的开销，事实上，效率⼀点也不⾼，已经测试过，产⽣随机数花费的开销真的很⼤，后边我⽤更快的三数中值⼜实现了⼀遍，思想是⼀样的，只是效率提⾼了。

C++完整代码：#include <iostream>#include <vector>#include <algorithm>using namespace std;int partition(vector<int> &A,int p,int r){int x = A[r];int i=p-1;int temp;for(int j = p;j<r;++j){if(A[j]<=x){++i;swap(A[i],A[j]);}}swap(A[i+1],A[r]);return i+1;}inline int Random(int low, int high) {return (rand() % (high - low + 1)) + low;}int Randomized_Partition(vector<int> &kp, int low, int high) {int i = Random(low, high);swap(kp[high], kp[i]);return partition(kp, low, high);}void randomized_quickSort(vector<int> &A,int p,int r){if(p<r){int q = Randomized_Partition(A,p,r);randomized_quickSort(A,p,q-1);randomized_quickSort(A,q+1,r);}}int randomized_select(vector<int> A,int p,int r,int i){if(p==r)return A[p];if(p>r) return -1;int q = Randomized_Partition(A,p,r);int k = q-p+1;if(i==k)return A[q];else if(i<k)return randomized_select(A,p,q-1,i);else return randomized_select(A,q+1,r,i-k);}void main(){int a[10] = {9,10,8,7,6,5,4,3,2,1};vector<int> A(a,a+10);cout<<randomized_select(A,0,9,5)<<endl;}3、第三种算法以最坏情况线性时间做选择，最坏运⾏时间为O(n)，这种算法基本思想是保证每个数组的划分都是⼀个好的划分，以5为基，五数取分，这个算法，算法导论没有提供伪代码，额，利⽤它的思想，可以快速返回和最终中位数相差不超过2的数，这样的划分接近最优，基本每次都⼆分了（算法导论中步骤见图)/*利⽤中位数来选取枢纽元,这种⽅法最坏情况下运⾏时间是O(n)这⾥求的中位数是下中位数算法导论⾥没有伪代码，写起来很⿇烦注意这⾥的查找到的中位数，并不是真正意义上的中位数⽽是和真正中位数相差不超过2的⼀个数开始以为我写错了，⼜看了算法导论，应该就是这个意思返回的是[x - 1, x + 2]的⼀个数，中位数是x从下边的输出中也可以看出：*/ #include<iostream>#include<cstdio>using namespace std;const int maxn = 14;//kp -> sizeconst int maxm = maxn / 5 + 1;//mid -> sizeint kp[maxn];int mid[maxm]; //插⼊排序void InsertionSort(int kp[], int n) {for (int j, i = 1; i < n; i++) {int tmp = kp[i];for (j = i; j > 0 && kp[j - 1] > tmp; j--) {kp[j] = kp[j - 1];}kp[j] = tmp;}} //查找中位数, 保证每⼀个划分都是好的划分int FindMedian(int kp[], int low, int high) {if (low == high) {return kp[low];}int index = low;//index初始化为low//如果本⾝⼩于5个元素，这⼀步就跳过if (high - low + 1 >= 5) { //储存中位数到mid[]for (index = low; index <= high - 4; index += 5) {InsertionSort(kp + index, 5);int num = index - low;mid[num / 5] = kp[index + 2];}} //处理剩下不⾜5个的元素int remain = high - index + 1;if (remain > 0) {InsertionSort(kp + index, remain);int num = index - low;mid[num / 5] = kp[index + (remain >> 1)];//下中位数}int cnt = (high - low + 1) / 5;if ((high - low + 1) % 5 == 0) {cnt--;//下标是从0开始，所以需要-1}//存放在[0…tmp]if (cnt == 0) {return mid[0];} else {return FindMedian(mid, 0, cnt);}} int Qselect(int kp[], int low, int high, int k) {int pivotloc = FindMedian(kp, low, high); //这⾥有点不⼀样，因为不知道pivotloc下标，所以全部都要⽐较int i = low - 1, j = high + 1;for (; ;) {while (kp[++i] < pivotloc) {}while (kp[--j] > pivotloc) {}if (i < j) swap(kp[i], kp[j]);else break;} int num = i - low + 1;if (k == num) return kp[i];if (k < num) {return Qselect(kp, low, i - 1, k);} else {return Qselect(kp, i + 1, high, k - num);}}int main() {int kp[maxn] = {10, 14, 8, 11, 7, 1, 2, 13, 3, 12, 4, 9, 6, 5};for (int i = 0; i < maxn; i++) {printf("中位数是: %d\n", FindMedian(kp, 0, maxn - 1));printf("第%d⼩的数是: ", i + 1);cout << Qselect(kp, 0, maxn - 1, i + 1) << endl << endl;}return 0;}。