算法设计与分析期末综合实验试题清单分治与递归1-1 合并排序问题描述：给定n 个整数，利用合并排序思想将其调整成单调序列。
输入：整数的个数n ，以及n 个整数输出：从大到小排序的n 个整数（或从小到大排序）1-2 split 快速排序（枢点法）问题描述：给定n 个整数，利用枢点法快速排序的思想将其调整成单调序列。
输入：整数的个数n ，以及n 个整数输出：从大到小排序的n 个整数（或从小到大排序）1-3 平面最近点对问题描述：平面内有若干点，设计一算法在O （nlogn ）时间内求出直线距离最近的一对点，并输它们的距离。
输入：点对的数目n 以及n 对点的坐标输出：最近的点对坐标（x,y ）以及距离d1-4 棋盘覆盖问题问题描述：在一个2k ×2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。
在棋盘覆盖问题中，要用图示的4种不同形态的L 型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L 型骨牌不得重叠覆盖。
输入：棋盘的行列数n ，棋盘中特殊方格的行列号（x,y ）输出：棋盘的覆盖方案1-5 求k 大（小）元素（基于split 枢点法划分）问题描述：有一数列，设计一分治递归算法，以Ω(nlogn)时间找出其第k 大（小）元素。
输入：整数的个数n 、n 个整数以及k 值输出：第k 大（小）元素值以及其对应的下标i1-6 二分检索问题描述：有一单调序列，设计一分治算法检索出元素x 。
输入：整数的个数n、n个单调增（减）个整数以及需检索的元素值x输出：最近的点对坐标（x,y）以及距离d1-7 大整数乘法（10进制）问题描述：有两个10制的大整数（不少于30位），设计一分治算法，以O（nlogn）时间算出其乘积。
输入：第一个大整数的位数m、第二个大整数的位数n，以及两个大整数x,y输出：两个大整数的乘积s1-8 循环赛比赛安排问题描述：设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1天。
输入：选手的个数n、n个选手的编号输出：每天的赛事安排(共n-1天）1-9 整数的划分问题问题描述：将正整数n表示成一系列正整数之和：n=n1+n2+…+n k，其中n1≥n2≥…≥n k≥1，k≥1。
正整数n的这种表示称为正整数n的划分。
求正整数n的不同划分个数以及划分情况。
输入：正整数n输出：n的划分个数以及划分情况1-10 主元素问题问题描述：有一个整数数列，数列中元素出现次数超过一半的元素定义为主元素，设计一分治算法，求出主元素。
输入：整数的个数n以及n个整数输出：如果有主元素，输出主元素以及它们所在的位置；如果没有主元素，输出-11-11 全排列的生成问题描述：给出一个序列，生成这个序列的全排列输入：整数的个数n以及n个整数输出：生成这n个数的全排列贪婪算法2-1 加油站问题问题描述：一辆汽车加满油后,可行使n千米。
旅途中有若干个加油站。
若要使沿途加油次数最少,设计一个有效算法，对于给定的n和k个加油站位置，指出应在哪些加油站停靠加油才能使加油次数最少。
输入：汽车加满油后可行驶千米数n，加油站个数k。
以及两两加油站之间的距离。
输出：最少的加油次数m，如果无法到达目的地，则输出“No Solution”。
2-2 货币兑换问题问题描述：当前有N种面额的货币，请为M元钱找出最合理的兑换方案（要求找出的货币数目最少）输入：货币面额的种类以及各种货币的面额以及需要兑换的钱数M输出：兑换方案以及用到的货币张数。
2-3 普通背包问题问题描述：给定n种物品和一个背包。
物品i的重量是Wi，其价值为Vi，背包的容量为C。
应如何选择装入背包的物品，使得装入背包中物品的总价值最大?（物体可以分割）输入：物体的件数n，背包的容量C，每件物品的重量和价值输出：背包内物品的总价值以及装载方案。
2-4 单源最短路径问题问题描述：给定一张有向带权图，求源点到其他各个点的最短距离以及路径。
输入：顶点个数n，有向带权图的邻接表数据输出：各个点到源点的最短距离以及最短路径2-5 最小生成树（prim）问题描述：给定一张无向带权图，利用pirm算法的思想求能将图的各个顶点全部连通的最短路径和（即最小生成树）输入：无向带权图输出：最小生成树2-6 最小生成树（kruskal）问题描述：给定一张无向带权图，利用kruscal算法的思想求能将图的各个顶点全部连通的最短路径和（即最小生成树）输入：无向带权图输出：最小生成树2-7 活动安排问题问题描述：设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。
如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。
为这样的活动场所安排尽可能多的活动。
输入：活动的个数n，以及每个活动的起始时间si和一个结束时间fi,且si <fi输出：可安排的最大相容活动子集。
2-8 排队接水问题问题描述：有N个人在一个水龙头前排队接水，假如每个人接水的时间为Ti,请编程找出这N个人排队的一种顺序，使得N个人的平均等待时间最小。
输入：人数N以及每个人的接水时间T1，T2,……,Tn,输出：排队顺序，即1到N的一种排列以及这种方案下的平均等待时间。
2-8 田忌赛马问题描述：田忌和齐王赛马各有n匹马，现进行n场比赛，比赛规则如下：1、马匹不得重复参赛。
2、赢一场得2分，输一场得0分，平局各得1分请为田忌安排马匹出场次序，使其得分最高。
输入：马匹数目n, 田忌每匹马的斗争值T1，T2,……,Tn,以及齐王每匹马的斗争值Q1，Q2,……,Qn,(值大的胜值小的马）输出：田忌马的出场次序以及最后的得分。
2-9 程序存储问题问题描述：设有n个程序{1,2,3,…,n}要存放在长度为L的磁带上。
程序i存放在磁带上的长度是l i,1≤i≤n。
要求确定这n个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。
输入：先是两个正整数，分别表示程序文件个数n和磁带长度L，接下来是n个正整数，表示程序存放在磁带上的长度。
输出：最多可以存储的程序个数m，以及已存程序的编号。
2-10 数列极差问题问题描述：在黑板上写了N个正整数作成的一个数列，进行如下操作：每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的max，最小的为min，则该数列的极差定义为M=max-min，编程求解这样的极差。
输入：正整数的个数N，以及N个正整数输出：极差d动态规划3-1 导弹拦截问题问题描述：某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
某天，雷达捕捉到敌国的导弹来袭。
由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入：导弹依次飞来的高度（不大于30000 的正整数），输出：最多能拦截多少导弹数，以及被拦截的导弹飞来时候的高度。
3-2 合唱队型问题问题描述： N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K 位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2...，K，他们的身高分别为T1，T2，...，TK，则他们的身高满足T1<...<Ti>Ti+1>...>TK(1<=i<=K)。
输入：队员人数N和每个学生身高T[i]，输出：最长的合唱队形的长度和相应的合唱队员编号。
3-3 最大子段和问题问题描述：给定一个整数序列,求其连续子序列的和的最大值，如果序列中全为负数则规定最大子段和为0,长度L=0。
输入：整数的个数n以及n个整数输出：最大连续子序列之和以及序列长度。
3-4 0/1背包问题问题描述：给定n种物品和一个背包。
物品i的重量是Wi，其价值为Vi，背包的容量为C。
应如何选择装入背包的物品，使得装入背包中物品的总价值最大?（物体不可以分割）输入：物体的件数n，背包的容量C，每件物品的重量和价值。
输出：背包内物品的总价值以及装载方案。
3-5 最长公共子序列问题问题描述：最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS （Longest Common Subsequence）。
其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。
设计一算法，求解两个序列的最长公共子序列。
输入：已经序列A、B以及长度对应的长度m、n；输出：最长公共子序列以及其长度3-6 矩阵连乘加括号问题问题描述：给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2 ,…,n-1。
给矩阵加上括号以确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。
输入：矩阵个数和n，以及n个矩阵的行、列信息输出：加括号的信息以及最少的乘法次数。
3-7 金矿开采问题问题描述：现在n座金矿，每座金矿开采需要的人数以及产金量已知（假设人数多或少于金矿开采所需人数均无法开采出一块金子），现有一定数量的人员，设计算法，计算出最多可以开采出的金矿数目。
输入：金矿数目n、人数m、以及每座金矿所需人数Pi以及产金量gi输出：最多开采出的金矿数目以及人员安排方案3-8 多段图最短路径问题问题描述：给定一张有向带权图，设计一动态规划的算法，计算出所有点到最后目标点的最短距离以及路径。
输入：有向带权图的邻接表以及项点个数n输出：每点到最后目标点的最短距离以及路径。
3-9资源最优分配问题问题描述：现在有某种资源共n个单位，准备将它们分配到m个项目上，设在第i个项目上分配j个单位的资源就可以获得的收益为a[i,j],求可以获得的最大总收益。
输入：资源数n，工程数m以及第i个项目上分配j个单位的资源可以获得的收益a[i,j]输出：最优分配方案以及可以获得的最大收益。
3-10 轨道建造问题问题描述：建造滑雪场的升降轨道。
起点和终点的高度已知，x坐标分割成若干份，间隔为1，每一点都给出支架的高度。
要选择尽可能少的支架顶端建立固定点，两个固定点之间用一条直钢轨连接，当然要求中间支架的高度都不能超过钢轨在那里的高度。
而且两个相邻固定点之间的距离不能超过给定的K。
输入：起点和终点海拔高度H1，H2，支架总个数n以及每个支架的海拔高度hi，相邻固定点间的最大限度距离K输出：最少用于固定的支架数目x以及用到的支架编号3-11 乘积最大问题问题描述：向长度为N的数字串中插入r个乘号，将其分成r+1个组成部分，找出一种分法，使得这r+1个部分乘积最大。