Algorithms Chapter 5 减治法.pptVIP

* * * * * * * * * * * * * * * * * * * * /deensley/mathdl/Joseph.html /examples/josephusproblem/ /deensley/DiscreteMath/flash/ch1/sec1_1/josephus.html * * * * * * * Nim Games：/ActivityDetail.aspx?ID=140 Nim：/Nim.html Nim Game：/robban/nim1.htm * * Deng Xin The Design and Analysis of Computer Algorithms 第五章 减治法Decrease and Conquer * 教学内容 减治法的一般方法及变种 插入排序 深度优先查找和广度优先查找 生成组合对象的算法 减常因子算法 减可变规模算法 * 减治法 减治技术利用了一种关系：一个问题给定实例的解和同样的问题较小实例的解之间的关系。 一旦建立了这种关系，就可以从顶至下（递归），也可以从底至上（非递归）的来运用。 减治法有三种变种： 1)减去一个常量 2)减去一个常数因子 3)减去的规模是可变的 * 减（一）治技术 规模为n 的问题 规模为n-1 的子问题 子问题的解 原始问题的解 f(n)=an f(n)=f(n-1)*a n1 f(n)=a n=1 * 减（半）治技术 规模为n 的问题 规模为n/2 的子问题 子问题的解 原始问题的解 an=(an/2)2 n是偶数 an=(a(n-1)/2)2 *a n是奇数 an =a n=1 * 插入排序 For j?2 to n do 将A(j)放到已分类集合A(0..j-1)的正确位置上 Repeat 算法 InsertionSort(A[0..n-1]) //用插入排序对给定数组排序 //输入：一个可排序数组 //输出：非降序列数组A for i?1 to n-1 do{ v?A[i]; j?i-1; while (j≥0 and A[j]v){ A[j+1]?A[j]; j?j-1; } A[j+1]?v; } 89 | 45 68 90 29 34 17 45 89 | 68 90 29 34 17 45 68 89 | 90 29 34 17 45 68 89 90 | 29 34 17 29 45 68 89 90 | 34 17 29 34 45 68 89 90 | 17 17 29 34 45 68 89 90 * 深度优先查找 邻接矩阵表示，该遍历算法的时间效率属于Θ(|V|2) 邻接链表表示，该遍历算法的时间效率属于Θ(|V|+|E|) * * 广度优先查找 邻接矩阵表示，该遍历算法的时间效率属于Θ(|V|2) 邻接链表表示，该遍历算法的时间效率属于Θ(|V|+|E|) * * 广度优先查找 * DFS与BFS的主要性质 * 拓扑排序(Topological sorting) 有向图 * 拓扑排序(Topological sorting) 用深度优先算法解决！ * 拓扑排序(Topological sorting) * 生成排列(Permutations) 生成由n个元素 {a1,a2,...,an}的排列 算法 JohnsonTrotter(n) //生成n个数的排列 //输入：一个正整数n //输出：{1,...,n}的所有的排列数 将第一个排列初始化为12...n while 存在一个移动整数k do 求最大的移动整数k 把k和它箭头指向的相邻整数互换 调转所有大于k的整数的方向 213 3和4可移动（看书上定义） * 生成子集（Subset） 背包问题中如何穷举出给定物品集合的所有子集？ A={a1,a2,...,an}={a1,a2,...,an-1} ∪{an} * 假币问题(Fake-Coin) 当n1时，W(n)=W([n/2])+1 , W(1)=0 * 俄式乘法(Multiplication á la russe) 两个大整数m和n乘法 n * m= n — 2 * 2 * m n为偶数 n * m= n -1