计算机算法设计与分析练习题
一． 最大子段和问题：给定整数序列 a1,a2,?,an，求该序列形如?ak的子
k?ij??段和的最大值： max?0,max?ak?
?1?i?j?nk?i?j1. 一个简单算法如下：
int Maxsum(int n,int a,int& besti,int& bestj) {
int sum = 0;
for(int i=1;i<=n;i++){ int suma = 0;
for(int j=i;j<=n;j++){ suma + = a[j]; if(suma > sum){ sum = suma; besti = i; bestj = j; } }
}
return sum;
}
试分析该算法的时间复杂性。
2. 试用分治算法解最大子段和问题，并分析算法的时间复杂性。
3. 试说明最大子段和问题具有最优子结构性质，并设计一个动态规划算法解最大子段和问题。分析算法的时间复杂度。
二．设x1,x2,?,xn是n个互不相同的元素，每个元素xi有一个正实数权值
wi，且满足?wi?1。n个元素x1,x2,?,xn的带权wi(1?i?n)的中位数是
i?1n满足下面不等式的元素xk：
1?w??i2??xi?xk ? (1)
1??wi?2??xi?xk1). 证明x1,x2,?,xn的（不带权的）中位数是带权wi?1/n （i?1,2, ?,n）的带权中位数（不带权的中位数是指按照大小排在中间位置的数，如果有两个，
则取小者）。 2). 说明如何通过排序，在最坏情况下用O(nlogn)时间求出n个元素的带权中位数。
3). 说明如何利用一个线性时间选择算法，在最坏情况下用O(n)时间求出n个元素的带权中位数。
4). 邮局位置问题是：已知
n个点
p1,p2,?,pn以及与它们相联系的权
n，使和式?wid(p,pi)达到最w1,w2,?,wn，要求确定一点p（未必是输入的点）
i?1小，其中d(a,b)表示a与b之间的距离。试论证带权的中位数是一维邮局问题的最优解，此时d(a,b)?|a?b|。
三．设p1,p2,?,pn是准备存放到长为L的磁带上的n个程序，程序pi需要的带长为ai。设?ai?L，要求选取一个能放在带上的程序的最大子集合（即其中
i?1n含有最多个数的程序）Q。构造Q的一种贪心策略是按ai的非降次序将程序计入集合。
1). 证明这一策略总能找到最大子集Q，使得?ai?L。
pi?Q 2). 设Q是使用上述贪心算法得到的子集合，磁带的利用率
pi?Q?a/L可以小到
i何种程度？
3). 试说明1)中提到的设计策略不一定得到使?ai/L取最大值的子集合。
pi?Q四．电路布线问题：在一块电路板的上、下两段分别有n个接线柱，如下 图。根据电路设计，要求用导线(i,?(i))将上端接线柱i与下端接线柱?(i)相连，
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
导线(i,?(i))称为电路板上的第i条连线。对于任何1?i?j?n,连线i,j相交的充分必要条件是?(i)??(j)。在制作电路板时，要求将这n条连线分布到若干个绝缘层上，使得在同一层上的连线不相交。电路布线问题就是要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。该问题等价于确定布线集
Nets??(i,?(i)),1?i?n?的最大不相交子集。
如果记N(i,j)??t|(t,?(t))?Nets,t?i,?(t)?j?，N(i,j)的最大不相交子集为
Mns(i,j)，试证明电路布线问题具有最优子结构性质。构造一个动态规划算法解
电路布线问题（写出算法的基本步骤即可），并说明你的算法的时间复杂度。 五．给定n件物品和一个背包，物品i的重量是wi，体积是vi，价值是pi； 背包的容量为C，容积为D。一件物品只能整个放进背包中或不放进背包中，也不允许重复放入。试设计一个求解此问题的算法，并计算其时间复杂度。 六．设计一个O(n2)时间的算法，找出n个数组成的序列的最长单调递增子 序列。
七． 字符a~h出现的频率恰好是前8个Fibonacci数，它们的Huffman编码是什么？将结果推广到n个字符的频率恰好是前n个Fibonacci数的情形。Fibonacci数的定义为：F0?1,F1?1,Fn?Fn?2?Fn?1ifn?1。
八． （双机调度问题）用两台处理机A和B处理n个作业。设第i个作业交给机器A处理时所需要的时间是ai，若由机器B来处理，则所需要的时间是bi。现在要求每个作业只能由一台机器处理，每台机器都不能同时处理两个作业。设计一个动态规划算法，使得这两台机器处理完这n个作业的时间最短（从任何一台机器开工到最后一台机器停工的总的时间）。以下面的例子说明你的算法：
n?6,(a1,a2,a3,a4,a5,a6)?(2,5,7,10,5,2),(b1,b2,b3,b4,b5,b6)?(3,8,4,11,3,4) 九．考虑下面特殊的整数线性规划问题
max?cixii?1n?axii?1n
i?b,xi?{0,1,2},1?i?n试设计一个解此问题的动态规划算法，并分析算法的时间复杂度。 十．考虑下列问题
i. 在一个由元素组成的表中，出现次数最多的元素称为众数。试写出一个 求众数的算法，并分析其时间复杂性。
ii. 主元素问题：数组T[1:n]中的元素x称为该数组的主元素，如果该数组
n。主元素问题是确定已2知数组中是否存在主元素。设计一个线性时间算法求解主元素问题。
中有多于一半的元素等于x，即?i|T[i]?x,1?i?n??十一． 分派问题一般陈述为：给n个人分派n件工作，把工作j分派给第i个人的成本为Cost(i,j)。设计一个回溯算法，在给每个人分派一件不同工作的情况下，使得总成本最小。
十二． 已知一个无向连通图G(V,E)用它的邻接矩阵T[1:n,1:n]表示，试设计一个回溯算法HamiltonCycle，判定该图是否有Hanmilton圈，如果有将所有不同的Hanmilton圈都打印出来。
十三． 设W?(5,7,10,12,15,18,20)和M?35，使用求定和子集问题的回溯算法找出W中所有和数为M的子集，并画出所生成的部分状态空间树。 十四． 画出优先队列式算法对于下列0/1背包问题实例所生成的部分状态 空间树：
n?5,(p1,p2,p3,p4,p5)?(10,15,6,8,4),(w1,w2,w3,w4,w5)?(4,6,3,4,2),M?12n?5,(p1,p2,p3,p4,p5)?(w1,w2,w3,w4,w5)?(4,4,5,8,9),M?15
十五．栈式分枝限界法将活结点表以后进先出(LIFO)的方式存储于一个栈中。试设计一个解0/1背包问题的栈式分枝限界算法，并说明栈式分枝限界算法与回溯法的区别。
部分问题提示：
问题一．1.3个for循环，时间复杂度为O(n3);
2. 将序列a[1:n]分成两部分：a[1:n/2]和a[n/2?1:n]，此时有三种可能情
况：
(1) a[1:n]的最大子段和与a[1:n/2]的最大子段和相同； (2) a[1:n]的最大子段和与a[n/2?1:n]的最大子段和相同；
(3) a[1:n]的最大子段和为?ak，其中1?i?n/2,n/2?1?j?n；
k?ij注意到上述三种情况，就可以设计出求最大子段和问题的分治算法。该算法的时间复杂度函数T(n)满足如下递推关系式
n?c?O(1), T(n)??2T(n/2)?O(n),n?c?其中c是一个固定正整数。直接推得可得时间复杂度为T(n)?O(nlogn)。
?j?3．若记b[j]?max??a[k]?,1?j?n，所求的最大子段和为
1?i?j?k?i?max?a[k]?maxmax?a[k]?maxb[j]
k?i1?j?n1?i?jk?i1?j?njj1?i?j?n注意到
jj?j?b[j]?max??a[k],?a[k],?,?a[k],a[j]?k?2k?j?1?k?1?j?1j?1???max?a[j]??a[k],a[j]??a[k],?,a[j]?a[j?1],a[j]?k?1k?2?? j?1?j?1??a[j]?max??a[k],?a[k],?,a[j?1],0?k?2?k?1??max?a[j]?b[j?1],a[j]?可以证明最大子段和问题具有最优子结构性质，并且设计出求解该问题的动态规划算法。该算法的时间复杂度为O(n)。
问题二3.对线性选择算法进行改进：首先同线性选择算法一样找到划分子程序（Partition）所用的“标竿”xj（即用来作为标尺的数，比该数大的数向后移，比该数小的向前移，通过交换完成），在Partition程序中加一句：计算比xj的元素的权和s(xj)；在线性选择算法的递归过程中，将判断j?k?改为
s(xj)?1?，这样就构造出线性时间的求带权中位数算法。 2
