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

1、算法设计与分析自学指导书习题一、填空题：1、按照渐近阶从低到高的顺序排列下列表达式：20n，4n2，logn，3n，2，n2/3，n!，2n。2、 分治法的基本思想是将一个规模为 n的问题分解为与原问题 (相同/不相同)的 k 个规模较小且 (互相独立 /相关)的子问题。3、 一个直接或间接地调用自身的算法称为 ，它有两个条件，一个是要直接或间接地调用自身，另一个是必须有 。4、 在一个nxn (n=2k)个方格组成的特殊棋盘中，需要 个L型骨 牌完成棋盘覆盖。5、在循环赛日程表问题中，若给定的运动员数n=2k-1,则至少需要天完成比赛；n=2k时，则需要。其中，k为自然数。6、动态规划算法的

2、主要步骤包括刻画最优解的性质和结构、递归定义最优值、 以自底向上的方式计算最优值、 根据计算最优值的相关信息构造最优解， 在分析 了最优解的性质和结构之后，一个比较至关重要的步骤是给出最优值的递归定 义，请给出下面几个问题的最优值的递归定义：(1) 矩阵连乘积问题中，Ai : j连乘所需的最少乘法次数定义为 mi，j ( Ki < j < n)，mi，j的初始值定义为0 (i=j),则mi，j递归定义为： mi ， j=(2) 最长公共子序列问题中，ci，j表示序列Xi和Yj的最长公共子序列的长 度，则ci，j可递归定义为：0i0, j0ci, j _ i, j0;xiy i, j

3、0;xiy7、在使用回溯法考虑求解一个具体问题时，往往需要设计出约束条件和限界条件。装载问题的约束条件是 ;限界条件是bestw>cw+r，其中，bestw是当前最优值， cw=， r=。8、 0-1 背包问题的回溯法和分支限接法求界中都涉及到活结点的上界函数 uProfit 的计算问题，它是由两部分组成，一是该活结点已经获得的价值之和 Profit，另 一个 则 是剩 余未 考 虑物 品 的 价 值上界 rProfit ， 这 个 值可 通过获_得。二、求解题：1 、请用快速排序法升序排序下面实例，给出每一趟排序的结果 。( 3， 20， 5， 9， 2， 30， 25， 18， 16

4、， 3)2、已知元素 a, b，h依次有概率 0.1, 0.2, 0.05, 0.1, 0.3, 0.05, 0.15, 0.05, 其余情况的概率为 0，请建立其最优二叉搜索树。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)。试分别画出用回溯法或优先队列式分支限界法求解时的搜索情况。&有如下城市网络图：试分别画出用回溯法或优先队列式分支限界法求解时的搜索情

5、况。三、证明题：1、若 T(n2/2r)=nT(n)+bn 2 (其中 r=0，T(2)=2 )则 T(n)=0(n(logn) r|oglogn)。2、试证明流水作业调度问题的Johnson算法是满足Johnson法则的最优调度。 其中：流水作业调度问题的 Joh nson算法是：(1 )令 N1=i|ai<bi，N2=i|ai > bi;(2) 将N1中的作业按ai非减序排序，将 N2中的作业按bi非增序排列；(3) N1中的作业接N2中的作业就构成满足 Johnson法则的最优调度。满足Johnson法则的调度是最优调度，调度n满足Johnson法则，当且仅当对任意 i<

6、;j，有 minb w ， a询 >minb n °)， an3、试证明若在0-1背包问题中，各物品依重量递增排列时，其价值恰好依递减 序排列，则用贪心算法可以找出其最优解。四、选作题：1、考虑下面的用最少硬币个数找出n分钱的问题。(1)当时用2角5分、一角、5分和1分四种硬币面值时，设计一个贪心算法找出n分钱，并证明算法能够产生一个最优解。(2)假设可使用的硬币面值是c°, c1,，ck,其中，c是一个正整数且c>1,k > 1。证明在这种情况下贪心算法总能产生最优解。（3）给出一个贪心算法不能产生最优解的硬币面值组合。2、设G是一个有n个顶点的有向图，

7、从顶点i出发的边的最小费用记为 min（i）, 证 明 图 G 的 所 有 前 缀 为 x1.i 的 旅 行 售 货 员 回 路 的 费 用 至 少 为ina Xj !，Xjmin Xj，其中，a（u，v）是边（u，v）的费用。j 2j i3、在一个圆形操场的四周摆放着 n 堆石子，现要将石子有次序地合并成一堆。 规定每次只能选相邻的两堆石子合并成一堆， 并将新的一堆石子数记为该次合并 的得分。试设计一个算法， 计算出将 n 堆石子合并成一堆的最小得分和最大得分， 并分析算法的计算复杂性。习题答案一、填空题1、2 logn n2/3 20n 40n2 2n 3n n!2、相同互相独立3、递归算

8、法初始条件 或非递归定义的初始值4、（ 4k-1）/3 或（n2-1）/35、n 或 2k-1n-1 或 2k-1ij6、min mi,k mk 1, j pi 1pk pjci 1, j 1 1 maX ci, j 1,ci 1, jk7、Xiwii1CkXicii1nwiik18、（普通）背包贪心方法或按单位重量价值降序排序后选择物品直到装满背包、求解题1、2339530 25 18 16 2023f5930 25 18 16 20f 20 25 18 16 3018 16 20 25 f16 18 f结果： 23359 16 18 20 25 302、（动态规划算法）0i jmi, jW

9、jmJnmi,k 1mk 1,j i jWjaij1k ibkakai是xXi, Xi1的概率，其中0in 且 X0,Xn 1bj是xXj的概率，其中1 j nm1,8=2.1,k=5,w 18=1m1,4=0.75,k=2,w 14=0.45m6,8=0.35,k=7,w 68=0.25M1,1=0.1m3,4=0.2,k=4,w 34=0.15m6,6=0.05m8,8=0.05m3,3=0.050ebgdfham i, j厲卩m i，km i,k3、（动态规划算法）m,s1234567i184,15,18,110,212,315,528 86,26,215,411,5385,313,47

10、,311,6488,49,49,45885,5684,678最短路：1f 2f 5 f 74、 a=b=c=1n n1 2Tn T n 1 n1 23 .nO n2Tn T n n 12 21.2k 2k 112n 1O n，其中n 2k25、最优值：53,最优解：bestx= (0,1,1, 1, 1, 0)6、最优值：10,最优解：bestx= (1 ,2,5, 4, 3)或(1 , 3, 4, 5, 2)三、证明题1、T 22T 42T 2 b4 4 b4T 4 4T 4b1616b16b16Tn . nT n b_n n bn bn2kk个bn相加，其中n 2 即klog log n= n+bnloglogn= (bloglogn+1) n=O (nloglogn )2、设i<j，分别证明：1) 当2) 当当i, j当i,jN1时，满足Johnson不等式；N 2时，满足Johnson不等式；3)当当iN1,jN2时，满足Johnson不等式3、分别证明: 贪心选择性质； 最优子结构