adai123

递归与分治一章：

        给定一个由n个互不相同的数组成的集合S，及一个正整数k<=n，试设计
        一个O(n)时间算法找出S中最接近S的中位数的k个数

动态规划一章：

        设有n种不同面值的硬币，各硬币的面值存于数组T[1:n]中。现要用这些
        面值的硬币来找钱。可以使用的各种面值的硬币个数不限。

        1）当只用硬币面值T[1],T[2],……T[i]时，可找出钱数j的最少硬币个数
        记为C(i,j)。若只用这些硬币面值，找不出钱数j时，记C(i,j)=无穷。给
        出C(i,j)的递归表达式，及其初始条件。1<=i<=n,1<=j<=L

        2）设计一个动态规划算法，对1<=j<=L，计算出所有的C(n,j)。算法中只
        允许使用一个长度为L的数组。用L和n作为变量来表示算法的计算时间复杂
        性。

        3）在C(n,j)，1<=j<=L，已计算出的情况下，设计一个贪心算法，对任意
        钱数m<=L,给出用最少硬币找钱m的方法。当C(n,m)不等于无穷时，算法的
        计算时间应为O(n+C(n,m))。

贪心算法一章：

        在黑板上写了n个正数组成的一个数列，进行如下操作：每一次擦去其中两
        个数设为a和b,然后在数列中加入一个数a*b+1，如此下去直至黑板上只剩
        下一个数。在所有按这种操作方式最后得到的数中，最大的数记为max,最
        小的数记为min，则该数列的极差M定义为M=max-min。对于给定的数列，设
        计一个有效算法计算出其极差M。并说明算法的正确性。

回溯法一章：
      
        运动员最佳配对问题。一个羽毛球队有男女运动员各n人，给定2个n*n矩阵P
        和Q。P[i][j]是男运动员i和女运动员j配对组成混合双打时的竞赛优势；
        Q[i][j]则是女运动员i和男运动员j配合时的竞赛优势。显然，由于技术的
        配合和心理状态等各种因素的影响，P[i][j]不一定等于Q[i][j]。设计一个
        算法，计算出男女运动员的最佳配对法，使各组男女双方竞赛优势乘积达到
        最大。

分支界限法一章：

        栈式分支界限法将活结点表以后进先出（LIFO）的方式存储于一个栈中。
        试设计一个解0-1背包问题的分支界限法，并说明栈式分支界限法与回溯
        法的区别。

        试设计一个解n后问题的优先队列式分支界限法。