《算法设计与分析》自学指导书
习题 一、填空题：
1、按照渐近阶从低到高的顺序排列下列表达式： 20n，4n2，logn，3n，2，n2/3，n!，2n。
______________________________________________________________ 2、分治法的基本思想是将一个规模为n的问题分解为与原问题____________（相同/不相同）的k个规模较小且____________（互相独立/相关）的子问题。 3、一个直接或间接地调用自身的算法称为____________，它有两个条件，一个是要直接或间接地调用自身，另一个是必须有____________。
4、在一个n×n（n=2k）个方格组成的特殊棋盘中，需要____________个L型骨牌完成棋盘覆盖。 5、在循环赛日程表问题中，若给定的运动员数n=2k-1，则至少需要____________天完成比赛；n=2k时，则需要____________天。其中，k为自然数。
6、动态规划算法的主要步骤包括刻画最优解的性质和结构、递归定义最优值、以自底向上的方式计算最优值、根据计算最优值的相关信息构造最优解，在分析了最优解的性质和结构之后，一个比较至关重要的步骤是给出最优值的递归定义，请给出下面几个问题的最优值的递归定义：
（1） 矩阵连乘积问题中，A[i：j]连乘所需的最少乘法次数定义为m[i，j]（1≤
i≤j≤n），m[i，j]的初始值定义为0（i=j），则m[i，j]递归定义为： m[i，，j]=________________________________________________
（2） 最长公共子序列问题中，c[i，j]表示序列Xi和Yj的最长公共子序列的长
度，则c[i，j]可递归定义为：
i?0,j?0?0?c[i,j]??______________________________i,j?0;xi?yj
?______________________________i,j?0;x?yij?7、在使用回溯法考虑求解一个具体问题时，往往需要设计出约束条件和限界条
件。装载问题的约束条件是____________；限界条件是bestw>cw+r，其中，bestw是当前最优值，cw=____________，r=____________。 8、0-1背包问题的回溯法和分支限接法求界中都涉及到活结点的上界函数uProfit的计算问题，它是由两部分组成，一是该活结点已经获得的价值之和Profit，另一个则是剩余未考虑物品的价值上界rProfit，这个值可通过______________________________________________________获得。
二、求解题：
1、请用快速排序法升序排序下面实例，给出每一趟排序的结果。 ．．．．．．．．．．
（3，20，5，9，2，30，25，18，16，3）
2、已知元素a，b，…，h依次有概率0.1，0.2，0.05，0.1，0.3，0.05，0.15，0.05，其余情况的概率为0，请建立其最优二叉搜索树。 ．．．．．．．
1
3、用动态规划算法求下面网络的最短路： ．．．．．
2 4 1 5 3 8 5 7 6 6 4 9 6 8 9 4 5 5 7 4、求解如下递归式，已知T(1)=1，a、b、c均为常数且a=b=c=1。 （1）T(n)=aT(n-1)+bn （2）T(n)=aT(n/2)+bnc
5、有0-1背包问题如下：
n=6，c=20，P=（11，8，15，18，12，6），W=（5，3，2，10，4，2）。 试分别画出用回溯法或优先队列式分支限界法求解时的搜索情况。 6、有如下城市网络图：
1 5 5 2 3 4 1 3 3 4 4 7 2 2 1 试分别画出用回溯法或优先队列式分支限界法求解时的搜索情况。
三、证明题：
1、若T(n2/2r)=nT(n)+bn2（其中r=0，T(2)=2）则T(n)=O(n(logn)rloglogn)。
2、试证明流水作业调度问题的Johnson算法是满足Johnson法则的最优调度。
其中：
流水作业调度问题的Johnson算法是： （1）令N1={i|ai （2）将N1中的作业按ai非减序排序，将N2中的作业按bi非增序排列； （3）N1中的作业接N2中的作业就构成满足Johnson法则的最优调度。 满足Johnson法则的调度是最优调度，调度π满足Johnson法则，当且仅当对任意i 3、试证明若在0-1背包问题中，各物品依重量递增排列时，其价值恰好依递减序排列，则用贪心算法可以找出其最优解。 四、选作题： 1、考虑下面的用最少硬币个数找出n分钱的问题。 （1）当时用2角5分、一角、5分和1分四种硬币面值时，设计一个贪心 算法找出n分钱，并证明算法能够产生一个最优解。 （2） 假设可使用的硬币面值是c0，c1，…，ck，其中，c是一个正整数且c>1， 2 k≥1。证明在这种情况下贪心算法总能产生最优解。 （3）给出一个贪心算法不能产生最优解的硬币面值组合。 2、设G是一个有n个顶点的有向图，从顶点i出发的边的最小费用记为min(i)，证明图G的所有前缀为x[1..i]的旅行售货员回路的费用至少为 ?a?xj?2ij?1，xj???min?xj?，其中，a(u，v)是边(u，v)的费用。 j?in3、在一个圆形操场的四周摆放着n堆石子，现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆石子合并成一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分，并分析算法的计算复杂性。 习题答案 一、填空题 1、2 logn n2/3 20n 40n2 2n 3n n! 2、相同 互相独立 3、递归算法 初始条件或非递归定义的初始值 4、（4k-1）/3或(n2-1)/3 5、n或2k-1 n-1或2k-1 6、 min?m[i,k]?m[k?1,j]?pi?k?ji?1pkpj?i?j c[i?1,j?1]?1 max?c[i,j?1],c[i?1,j]? ?xwii?1kki7、 ?C ?xci?1nii i?k?1?wi 8、（普通）背包贪心方法或按单位重量价值降序排序后选择物品直到装满背包 二、求解题 1、２ ３ ３ ９ ５ 30 25 18 16 20 ２ ３ ↑ ５ ９ 30 25 18 16 20 3 ↑ 20 25 18 16 30 18 16 20 25 ↑ 16 18 ↑ 结果： ２ ３ ３ ５ ９ 16 18 20 25 30 2、（动态规划算法） 0i?j??m[i,j]??w??m[i,k?1]?m[k?1,j]?i?j ijmin?i?k?j?wij?ai?1???bk?ak? k?ijai是x??xi,xi?1?的概率,其中0?i?n且x0???,xn?1??? bj是x?xj的概率,其中1?j?n m[1,8]=2.1,k=5,w18=1 m[1,4]=0.75,k=2,w14=0.45 M[1,1]=0.1 m[3,4]=0.2,k=4,w34=0.15 m[3,3]=0.05 0 e m[6,8]=0.35,k=7,w68=0.25 m[6,6]=0.05 m[8,8]=0.05 b g a d f h c 3、（动态规划算法） ?i?j??m?i,j????m?i,k??m?i,k??i?j min??i?k?jj m,s 1 i 1 2 3 8 2 4,1 8 3 5,1 8 8 4 8,1 6,2 5,3 5 6 7 10,2 12,3 15,5 6,2 13,4 15,4 11,5 7,3 11,6 4 最短路：1→2→5→7 4、a=b=c=1 4 5 6 7 8,4 8 9,4 8 9,4 5,5 4,6 8 T?n??T?n?1??n?1?2?3?...?n?n?n?1??On2 2?n?T?n??T???n?1?2?21?...?2k?2k?1?1?2n?1?O?n?,其中n?2k ?2?5、最优值：53，最优解：bestx=（0，1，1，1，1，0） 6、最优值：10，最优解：bestx=（1，2，5，4，3）或（1，3，4，5，2） 8 8 ??三、证明题 1、 T?2??2 T?4??2T?2??b4?4?b4 T?4??4T?4??b16?16?b16?b16 …… T?n??nT?n??bn?n?bn?...?bn k k个bn相加，其中n?22即k?loglogn =n+bnloglogn=（bloglogn+1）n=O（nloglogn） 2、设i 四、选作题 1、 1）贪心算法正确性的证明，贪心选择性质+最优子结构性质； 2）同上； 5
算法设计与分析自学指导书
