算法设计与分析自学指导书

1、算法设计与分析自学指导书习题一、填空题：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、动态规划算法的

2、主要步骤包括刻画最优解的性质和结构、递归定义最优值、以自底向上的方式计算最优值、根据计算最优值的相关信息构造最优解，在分析了最优解的性质和结构之后，一个比较至关重要的步骤是给出最优值的递归定义，请给出下面几个问题的最优值的递归定义：（1） 矩阵连乘积问题中，ai：j连乘所需的最少乘法次数定义为mi，j（1ijn），mi，j的初始值定义为0（i=j），则mi，j递归定义为：mi，j=_（2） 最长公共子序列问题中，ci，j表示序列xi和yj的最长公共子序列的长度，则ci，j可递归定义为：7、在使用回溯法考虑求解一个具体问题时，往往需要设计出约束条件和限界条件。装载问题的约束条件是_；限界条件是b

3、estw>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，请建立其最优二叉搜索树。123456799854758

4、46653、用动态规划算法求下面网络的最短路：4、求解如下递归式，已知t(1)=1，a、b、c均为常数且a=b=c=1。（1）t(n)=at(n-1)+bn（2）t(n)=at(n/2)+bnc5、有0-1背包问题如下：n=6，c=20，p=（11，8，15，18，12，6），w=（5，3，2，10，4，2）。试分别画出用回溯法或优先队列式分支限界法求解时的搜索情况。1234557213231446、有如下城市网络图：试分别画出用回溯法或优先队列式分支限界法求解时的搜索情况。三、证明题：1、若t(n2/2r)=nt(n)+bn2（其中r=0，t(2)=2）则t(n)=o(n(logn)rlog

5、logn)。2、试证明流水作业调度问题的johnson算法是满足johnson法则的最优调度。其中：流水作业调度问题的johnson算法是：（1）令n1=i|ai<bi，n2=i|aibi；（2）将n1中的作业按ai非减序排序，将n2中的作业按bi非增序排列；（3）n1中的作业接n2中的作业就构成满足johnson法则的最优调度。满足johnson法则的调度是最优调度，调度满足johnson法则，当且仅当对任意i<j，有minb(i)，a(j)minb(j)，a(i)3、试证明若在0-1背包问题中，各物品依重量递增排列时，其价值恰好依递减序排列，则用贪心算法可以找出其最优解。四、选

6、作题：1、考虑下面的用最少硬币个数找出n分钱的问题。（1） 当时用2角5分、一角、5分和1分四种硬币面值时，设计一个贪心算法找出n分钱，并证明算法能够产生一个最优解。（2） 假设可使用的硬币面值是c0，c1，ck，其中，c是一个正整数且c>1，k1。证明在这种情况下贪心算法总能产生最优解。（3） 给出一个贪心算法不能产生最优解的硬币面值组合。2、设g是一个有n个顶点的有向图，从顶点i出发的边的最小费用记为min(i)，证明图g的所有前缀为x1.i的旅行售货员回路的费用至少为，其中，a(u，v)是边(u，v)的费用。3、在一个圆形操场的四周摆放着n堆石子，现要将石子有次序地合并成一堆。规定

7、每次只能选相邻的两堆石子合并成一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分，并分析算法的计算复杂性。习题答案一、填空题1、2 logn n2/3 20n 40n2 2n 3n n!2、相同 互相独立3、递归算法 初始条件或非递归定义的初始值4、（4k-1）/3或(n2-1)/35、n或2k-1 n-1或2k-16、 7、 8、（普通）背包贪心方法或按单位重量价值降序排序后选择物品直到装满背包二、求解题1、 30 25 18 16 20 30 25 18 16 20 20 25 18 16 30 18 16 20 25 16 18 结

8、果： 16 18 20 25 302、（动态规划算法）m1,8=2.1,k=5,w18=1m1,4=0.75,k=2,w14=0.45m6,8=0.35,k=7,w68=0.25m1,1=0.1m3,4=0.2,k=4,w34=0.15m6,6=0.05m8,8=0.05m3,3=0.050ebadcgfh3、（动态规划算法）m,sj1234567i184,15,18,110,212,315,52886,26,215,411,5385,313,47,311,6488,49,49,45885,5684,678最短路：12574、a=b=c=15、最优值：53，最优解：bestx=（0，1，1，1，1，0）6、最优值：10，最优解：bestx=（1，2，5，4，3）或（1，3，4，5，2）三、证明题1、 k个bn相加，其中 =n+bnloglogn=（bloglogn+1）n=o（nloglogn）2、设i<j，分别证明：1）当时，满足johnson不等式；2）当时，满足johnson不等式；3）当时，满足johnson不等式3、分别证明：贪心选择性质；最优子结构性质四、选作题1、1）贪心算法正确性的证