算法导论第三次习题课.

Presentation on theme: "算法导论第三次习题课."— Presentation transcript:

1 算法导论第三次习题课

2 16.1-1 动态规划时间复杂度为 ，贪心算法时间复杂度为 。

3 略 16.1-3 用两个链表分别存放空闲教室和繁忙教室，把活动按开始时间递增排序，依次调度教室，就可以获得最少教室数。调度方案是在繁忙教室队列中寻找是否有教室已经空闲，再在空闲教室队列中寻找空闲教室，如果都没有，就再增加一个教室。 说明：本题直接调用书上的算法GREDDY-ACTIVITYSELECTOR( )来求是不对的，如下实例，按GREDDYACTIVITY-SELECTOR( )求得需要3个教室，实际上只要2个教室 i 1 2 3 4 5 6 7 s 8 f 9

4 略 略 16.3-5 用2n-1位表示树的结构，内部结点用1表示，叶子结点用0表示，以树的遍历为序。用nlog(n)位表示字母序列，每个字母的二进制编码长度为log(n)，总共需要nlog(n)位。

5 17.1-1 不能保持，如执行n次MULTIPUSH(s,n) 17.1-3 O(n) 平摊开销为O(1)。

6 17.2-2 每个操作都支付3元费用，若i不是2的幂次，则只用1元，剩下的2元用于支付那些是2的幂次的操作。 17.2-3 当某位被置为1时，用1元支付置位的实际代价，2元作为存款，其中1元将来该位变为0时使用，另外1元RESET此位时使用

7 17.3-2 总代价为O(n)，平摊代价为O(1) 17.3-6 设有两个栈A，B ENQUEUE操作为：push A DEQUEUE操作为： if B is empty 将A中元素导入B中 if B is not empty pop B 平摊代价为O(1)

8 略 30.2-4对FFT算法作如下修改即可：用 代替ω，并且将最后结果的每个元素除以n。

9 30.2-5

10 略 略 22.2-7 先对T 中任意一顶为根做BFS，记录最后遍历的顶点u，再以u 为根做BFS，记录最后遍历的顶点v，d(u,v)为T 的直径。时间复杂度O(V+E)。

11 略 略

12 略 22.4-2 先对图进行拓扑排序，然后从t到s依次计算Pu（以u为起点t为终点的路径数） Pu=ΣPv，v∈Adj(u) Pt=1， Pu=0，出度为0或在t的右边 22.4-3 方法很多，有些方法需要对每个连通片都进行计算。

13 24.1-3 m未知时，则某一轮循环没有执行relax操作时终止即可。
24.1-6 修改Bellman-Food算法，先找到负环上的一个节点，再依次找到负环上的其他节点。

14 最后一个顶点没有出度 24.2-4 先进行拓扑排序，然后从右往左依次计算Pu（以u为起点的路径数） Pu=Σ（Pv+1） , v∈Adj(u) Pu=0 ，u的出度为0 最后对所有Pu累加就是路径总数。

15 略 25.2-4 检查Floyd_Warshall( )输出矩阵主对角线上的元素，如果存在负数，则存在权为负的回路。

16 略 h(v)=0, h(u)=0, =w+h(u)-h(v)=w 25.3-5

17 第26章 26.2-1 流：19，容量：31 26.2-2 题目要求写Edmonds-Karp算法的处理过程，注意读清题意 26.2-4 略

18 串匹配附加题 1、 32次 2、 注意二进制串是从后往前记录的，不是正向的！ 3、16次 4、17次