计算机算法复习重点资料教学文案

1、计算机算法复习重点资料n-bit大数相乘算法归并排序 给定一个数列，将其排序 排序问题的分治法求解 将待排序数列一分为二，每个子数列分别排序 将完成排序的两个子数列合并 考虑合并两个排序的数组 和 ，结果存入 中1. xk1. yl1.zkl“o”表示元素与数列连接 一个mergesort算法执行实例习题 使用分治大数相乘算法，计算两个二进制整数10011011和10111010的乘积。要求画出算法执行的问题分解树。Explore算法 Explore算法 算法执行情况 一个节点上多条边存在时按字母顺序访问下一节点。这个树被称为深度优先搜索树（DFS树） 实线表示图上实际被访问的边，每条实线边代

2、表一个explore调用。实线边被称为树边。 虚线边表示图上没有被访问的边，因为访问这些边不会发现新的节点。虚线边被称为回边。深度优先搜索explore(u)可以访问所有从u出发可达的节点对于没有访问过的节点v，调用explore(v)访问从v出发能够到达的所有节点，直到图G上的所有节点都被访问过 在以上算法中，每个节点有两个关键事件： 算法首次访问到该节点； 算法完成从该节点出发的所有探索，离开该节点 定义数组pre和post分别记录节点的这两个时间 通过在previsit和postvisit，和一个初始化为1的计数变量clock来实现 算法执行实例 算法先后调用explore(A)，exp

3、lore(C)和explore(F)。 算法产生三棵DFS搜索树，称为一个DFS森林 节点上数值分别为该节点pre和post的值有向图上深度优先搜索-边的类型 将DFS算法应用到有向图上，注意在explore中严格按照边的方向访问节点。 DFS在有向图中执行示例 对于有向图DFS产生的搜索树（森林），一些定义： A是树的根节点，是所有节点的祖先 所有节点是A的后裔 F、G和H是E的后裔，E是F、G和H的祖先 A是C和B的父节点、C和B是A的子节点 将有向图G上边集E中的边对应到DFS森林中，有一些定义： DFS森林中的实线被称为树边，在这条边上调用explore 一条从节点到其非子节点的后裔的

4、边被称为前向边 一条从节点到其祖先的边被称为回边 两个非祖先-后裔关系的节点之间的边被称为横跨边习题 在下图中执行深度优先搜索，如果遇到多个节点可供选择的情况，按照节点字母顺序搜索。画出DFS树，给出图上每条边是树边、前向边、回边还是横跨边，并标出每个节点的pre和post值。Dijkstra算法 考虑边有长度的图，其中每条边的长度是正数，我们希望计算图中节点之间的距离。 优先队列支持以下操作： insert：队列中加入一个新元素 decreasekey：将队列中某个元素的键值减少 deletemin：返回队列中具有最小键值的元素，并且将该元素从队列中移除 makequeue：给定一组元素和键

5、值，构造一个优先队列 Dijkstra算法 算法执行实例：从A出发，右边列出所有节点当前的dist值A到各节点的最短路径树Bellman-Ford算法 一个运行实例在每一轮，可以按照边长从小到大调用update，边调用update的顺序不唯一习题 在下图中从节点S出发执行Bellman-Ford算法 (a) 使用表格描述算法执行过程中从S到各节点的当前最短距离 (b) 画出最短路径树最小生成树 Kruskal的算法： 将图G中所有的边按照权重从小到大排序； 树T初始化为空，依次挑选不在T中权重最小的，且在T上不产生环的边加入T 算法执行实例 加入B-C和C-D，但是B-D产生环，略过， ,BC

6、 CD BD CFDF EF AD ABCE AC边的排序： Kruskal算法的实现 使用分离集描述算法的状态。每个分离集包含当前获得连通部件的节点。如上例中A,B,C和D,E 分离集上实现以下操作 makeset(x)：构造一个仅包含x的单集 find(x)：返回当前x所在的集合 union(x,y)：合并包含x和y的集合为一个集合 完整的Kruskal算法描述 分离集数据结构 使用树结构表示一个集合。树可以任意构造。树上每个节点代表一个集合元素，每个节点有一个指针，指向其父节点。根节点的指针指向自己。用根节点代表相应的集合。 树上每个节点保存一个数值rank，表示悬挂于该节点下的子树的高

7、度。B,EH,C,D,F,G,A 实现makeset和find makeset耗时为O(1)，而find耗时正比于树的高度 合并两个集合：将较矮的树的根节点直接连到较高的树的根节点上function find(x)while x(x): x=(x)return x 操作示例，上标代表节点的rank 首先执行makeset构造单集 执行union(A,D)，union(B,E)，union(C,F) 执行union(C,G)，union(E,A)Prim算法 使用优先队列，类似Dijkstra 算法执行实例习题 考虑下图 (a) 它的最小生成树权重（树上边权重的总和）是多少?画出最小生成树。 (

8、b) 在其上运行Kruskal算法，边加入MST的顺序是怎样的？有向无环图dag上最短路径问题 dag中所有节点可以线性排列，这一性质启发我们考虑一种新的算法计算dag中两点间最短路径 例如：考虑下图中从S到D的最短路径 从S到D必须经过B或者C，因此( )min( ) 1,( )3dist Ddist Bdist C 对dag中所有节点，都存在类似的问题分解关系，如果我们按照下图dag节点线性化的顺序计算节点的dist，则在计算每个节点时，所需要的其它节点的距离信息已经是已知的了 算法如下最长递增子序列 给定一个序列的数 定义原序列的子序列为原序列元素的一个子集，且子序列各元素的相对顺序不变

9、 。找出给定序列的最长递增子序列 例如，序列5, 2, 8, 6, 3, 6, 9, 7 的最长递增子序列是2, 3, 6, 912,na aa1212, 1kiiikaaaiiin且 上图的有向边表示元素间的增长关系。如果考虑所有可能添加的有向边，我们得到下图 这是一个dag，其中对任意有向边(i,j)，ij。 令L(j)是终止于元素j的最长递增子序列的长度，则这个子序列必然包含某条指向j的有向边(i,j)，使得L(j)=L(i)+1。得到算法如下最大利润问题 某巧克力工厂生产两种巧克力，普通巧克力和高级巧克力。工厂每生产一盒普通巧克力，利润为￥1，每生产一盒高级巧克力，利润为￥6。每天最多

10、有200盒普通巧克力和300盒高级巧克力的订单，并且工厂每天生产最多400盒巧克力。工厂希望最大化利润，应该怎样安排生产？ 假设工厂每天生产x1盒普通巧克力，x2盒高级巧克力。如何确定它们的取值？ 使用线性规划描述问题如下 目标函数： max x1+6x2 限制条件： x1200 x2300 x1+x2400 x1, x20 假设巧克力工厂开发了一种更高档的巧克力产品，称为礼盒巧克力。每生产一盒礼盒巧克力，实现利润￥13。与上例相同，工厂每天最多生产400盒巧克力，同时，高级巧克力和礼盒巧克力都采用相同的包装材料，不同的是礼盒巧克力消耗3倍于高级巧克力的包装材料。工厂每天有600单位的包装材料。 用x3表示每天生产的礼盒巧克力数量，线性规划问题如下maxx1+6x2+13x3x1200, x2300, x1+x2+x3400 x2+3x3600, x1,x2,x30习题 7.2 某种农产品产于A和B两地，其中A地产量15，B地产量为8。这种产品只在C和D两个城市销售，其中C城