每节一经典 用系统的观点观察问题 总体设计，逐步求精 计算机科学学院 王小明 （博士/教授/博士生导师） sss 每节一经典 用系统的观点观察问题 总体设计，逐步求精 计算机科学学院 王小明 （博士/教授/博士生导师） Email: wangxm@snnu.edu.cn 1

第3讲 算法工具与优化技巧 √算法设计7部曲 问题定义—问题分析—数学模型—计算模型-算法设计—算法分析—算法优化 重复操作是复杂算法的重要特征，解决办法有：循环结构，递归结构。 （1）循环结构设计要注重效率（时间、空间） 问题：例如，求1/1!-1/3!+1/5！-1/7!+…+(-1)n+1/(2n-1)! 分析:此问题需要先进行累乘（求阶乘）,再把累乘的结果的符号倒数进行累加. 数学建模：Sn=Sn-1+(-1)n+1/(2n-1)! 计算机建模（计算模型）：S=S+(-1)n+1/(2n-1)!，(这个式子称为循环不变式). 算法设计1: 2重循环实现，效率低。

第3讲 算法工具与优化技巧 注：(1)中问题算法设计 与算法分析： 1)算法正确。因为算法能实现解决问题的目标。 2)算法可终止。当输入确定的n值后，内、外循环的 次数都是有限的，其他语句各执行一次，语句个数也是有限的，所以算法执行有限次后必然终止。 3）算法时间复杂度是O(n2). 缺陷：算法效率低（时间复杂度仍然高O(n2)）。 原因:(1)每一个数的阶乘都需要计算：1*2*3*…*m, (2)每一次循环需要重复计算sign=sign*(-1)， 共n*(n-1)/2次，这是没有必要的。 改进：从数学模型入手 Sn=Sn-1+(-1)n+1An ; An=An-1*1/((2*n-2)*(2*n-1)). 计算模型： S=S+(-1)n+1/A; A=A*(2*i-2)*(2*i-1); 再优化： (-1)n+1用sign=-sign实现。 Main() {int i,n,j,sign=1; float s,t=1; input(n); s=1; for(i=2;i<=n;i=i+1) {t=1; for(j=1;j<=2*i-1;j=j+1) t=t*j; sign=1; for(j=1;j<=i+1;j=j+1) sign=sign*(-1); s=s+sign/t; } print(“sum”,s);

第3讲 算法工具与优化技巧 Main() {int i,n,j,sign=1; 算法分析： float s,t=1; input(n); s=1; sign=1; for(i=2;i<=n;i=i+1) {sign=-sign; A=A*(2*i-2)*(2*i-1) S=S+sign/A } print(“sum”,s); 算法分析： 1)算法正确。因为算法能实现解决问题的目 标。 2)算法可终止。当输入确定的n值后，循环的 次数是有限的，其他语句各执行一次，语 句个数也是有限的，所以算法执行有限次后 必然终止。 3）算法时间复杂度是O(n).

第3讲 算法工具与优化技巧 设计原则：自顶向下，逐步求精 （程序设计课程已讲） （3）特殊问题，具体分析 设计打印下列图形的算法： 1 （2）自顶向下设计（从总体到细节） 设计原则：自顶向下，逐步求精 （程序设计课程已讲） （3）特殊问题，具体分析 设计打印下列图形的算法： 1 5 2 8 6 3 10 9 7 4 （课堂练习）

第3讲 算法工具与优化技巧 （2）递归（recursion）设计要点 什么是递归? 一个函数或过程在其定义或说明中又直接或间接调 用自身的方法 例： 递归函数F可定义如下 Function F(x) Begin If x=1 Return(1) Else y=F(x-1) End

第3讲 算法工具与优化技巧 递归算法设计：把一个复杂的大问题层层转化为一个与原问题相 似的较小问题，再逐步求解小问题，然后回过头 来求得大问题的解。 问题从大到小逐步化小 答案从小到大构造 解决最小问题（简单问题）

第3讲 算法工具与优化技巧 递归算法特点：优点：1）算法简洁（语句（代码）少）。 2）易分析。 缺点：执行效率低（时间多、占用存贮空间多）。 算法设计步骤：1）构造递归关系：逐步使问题变小的规律（数学 公式）； 2）找出递归停止条件：最小问题的解，如1!=1; 3）设计计算模型：根据1）设计计算模型. 例如： 求：1+2+3+…+100 的和。 数学模型是：S= 1+2+3+…+100 计算模型是：S=S+i

第3讲 算法工具与优化技巧 日子不好打法？你想消磨时光？ 请君玩汉诺塔游戏！----- 一个递归问题的实例 也许它会使你成为超人天才！获得重大发现！ A C B

第3讲 算法工具与优化技巧 递归算法设计 例3.1 汉诺塔问题：从一个古老的传说谈起。 C A B 第3讲 算法工具与优化技巧 递归算法设计 例3.1 汉诺塔问题：从一个古老的传说谈起。 古代有一个梵塔，塔内有三个基座A,B,C,最初A上有64个 大小不等的圆盘，大盘在下，小盘在上。有一个老和尚 想把64个盘从A移到B，但每次只能移动一个盘，并且在移动过程 中，3个基座上的盘都保持大盘在下，小盘在上。移动过程中利用 C做辅助。 问题1：需要多长时间？ 问题2：如何设计计算机算法实现上述目标？

第3讲 算法工具与优化技巧 递归算法设计:汉诺塔问题---世界末日问题 很不幸！ 每秒移动一次，无任何多余的移动步骤，完成64个盘子的移动任务需要约5800亿年！ B A C

第3讲 算法工具与优化技巧 例3.2 只有3个盘子的世界末日问题 A C B 1 2 3 最终目标 4

第3讲 算法工具与优化技巧 例3.2 只有3个盘子的世界末日问题（续） A C B 5 6 7 共7步

第3讲 算法工具与优化技巧 演示： A C B

第3讲 算法工具与优化技巧 初始状态：A(1,2) Step 1: A( ,2) B( ) C(1) 从简单问题入手：2个盘子的世界末日 问题解决思路。 初始状态：A(1,2) Step 1: A( ,2) B( ) C(1) Step 2: A( , ) B(2) C(1) Step 3: A( , ) B(1,2) C( ) 猜想1：步数=22-1=3 ? 猜想2：步数=2n-1 ? ? 目标 A C B 1 2 A B C 1 2 A C B 2 1 A B 1 C 2

第3讲 算法工具与优化技巧 从简单问题扩展：n个盘子的世界末日问题解决思路。 基本思想： 2）再把编号（n-1）的盘子与编号为n的盘子一起看作2 个盘子，进行移动。

第3讲 算法工具与优化技巧 n个盘子的世界末日问题解决过程。 移动过程： 1）把上层编号为（n-1）盘子看成 一个整体，从A借助B移到C 2 A n-1 n C B 第3讲 算法工具与优化技巧 n个盘子的世界末日问题解决过程。 移动过程： 1）把上层编号为（n-1）盘子看成 一个整体，从A借助B移到C 2）然后把编号为n的盘子从A移到B 3) 再把C上的编号为（n-1）的 盘子借助A移到B.

1 2 A n-1 n C B

第3讲 算法工具与优化技巧 n个盘子的世界末日问题解决算法： 1）设计一个名为hanoi(n,a,b,c)的算法，其中n是圆盘层数， a,b,c是基座的功能标记,注意：a,b,c并不总是代表A,B,C. a:每次移动的起始基座; b:每次移动的目标基座；c:辅助基座 Step1：hanoi(n-1,a,c,b) Step2: 把最下面一个大盘从A移到B Step3: hanoi(n-1,c,b,a) 注意：hanoi(n-1,*,*,*)位置变量. a n-1 c a 第n个 b c n-1 b

第3讲 算法工具与优化技巧 Public static void hanoi(int n,int a,int b,int c) { if (n>0) hanoi(n-1,a,c,b) move(a,b) hanoi(n-1,c,b,a); ｝

第3讲 算法工具与优化技巧 定理 3.1 对n阶汉诺塔问题，共需2n-1次移动操作. 证明：用数学归纳法。 2*(21-1)+1=2*2-2+1=22-1=3，此时结论成立。 3）假设n=k时，结论成立（k>1），即k阶汉诺塔问题，共需2k-1次移动操作. 4) 当n=k+1时，把k个盘子看成一个整体（看成一个盘子），再把第k+1个盘子和 k个盘子构成的那个整体盘子一起看作2个盘子进行移动。由2)知，共需要移 动次数：2*(2k-1)+1= 2k+1-1. 综合1）、2）、3）、4），定理得证。 因此，上述算法的时间复杂度是：O(2n), 即指数复杂度的，也就是说它是NP问 题。

第3讲 算法工具与优化技巧 小结： 循环算法效率问题：尽可能降低循环嵌套，提高时间效率。 递归算法设计要点,步骤。 作业：1)试用手工操作，画出4或5阶汉诺塔求解过程。 2）设计汉诺塔求解算法，如有兴趣可在机器上运行 ，看看当n增大时，算法所用时间长短变化情况。 3）预习：P61-68,递归与循环比较

That’s all for today See you next time Good bye!

第3讲 算法工具与优化技巧 √递归与循环比较 递归是实现“重复操作”的一种机制，通过把大问题化小，小问题化到能解问 题为止，再由小到大把问题的解“累积”起来，从而得到最大问题（原问题） 的解，需要用到数据结构中的栈（stack）来暂时存贮中间结果。 重要结论： 定理3.2 每个迭代算法原则上总可以转换成与其功能等价的递归算法；反之不然，即并 不是每个递归算法都可以转换成与其功能等价的迭代算法。 证明：提示：后一部分结论证明只需举例汉诺塔问题作为反例即可证明。前半部分结论 需要程序变换知识，比较难（省略，有兴趣的同学可以试一试）。 注意： 有些递归程序转化为非递归程序需要栈(stack)辅助，有些则不需要栈(stack)辅助。

第3讲 算法工具与优化技巧 √递归与循环比较 递归算法优缺点： 优点： 1）更接近自然语言理解 2）算法简洁，设计难度小 3）正确性容易证明 4）复杂性容易分析 缺点： 1）时间效率低（执行速度慢：保存中间结果现场、返回时回收资源 需要时间） 2）空间效率低（用stack保存中间结果现场）

第3讲 算法工具与优化技巧 √递归与循环比较 迭代算法优缺点： 缺点： 1）不接近自然语言，难理解 2）有些算法较长 3）有些算法正确性不容易证明 4）有些算法复杂性不容易分析 5）适用范围小，设计难度大 优点： 1）时间效率高（一般不需要保存中间结果现） 2）空间效率高（一般不用stack保存中间结果现场）

第3讲 算法工具与优化技巧 √算法与数据结构（自己复习、看书总结） 算法+数据=程序 数据=数据元素+存贮结构 所以存贮结构影响算法，算法影响存贮结构。 作业：p75, 例15；p77,例17

第3讲 算法工具与优化技巧 √算法优化技巧（自己复习、看书总结） 作业：p114, 例40；p115,例41

第3讲 算法工具与优化技巧 √习题 作业：p118,（9,10,12,15,20,27）

That’s all for today See you next time Good bye!