Presentation is loading. Please wait.

Presentation is loading. Please wait.

每节一经典 用系统的观点观察问题 总体设计,逐步求精 计算机科学学院 王小明 (博士/教授/博士生导师)

Similar presentations


Presentation on theme: "每节一经典 用系统的观点观察问题 总体设计,逐步求精 计算机科学学院 王小明 (博士/教授/博士生导师)"— Presentation transcript:

1 每节一经典 用系统的观点观察问题 总体设计,逐步求精 计算机科学学院 王小明 (博士/教授/博士生导师)
sss 每节一经典 用系统的观点观察问题 总体设计,逐步求精 计算机科学学院 王小明 (博士/教授/博士生导师) 1

2 第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 第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);

4 第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).

5 第3讲 算法工具与优化技巧 设计原则:自顶向下,逐步求精 (程序设计课程已讲) (3)特殊问题,具体分析 设计打印下列图形的算法: 1
(2)自顶向下设计(从总体到细节) 设计原则:自顶向下,逐步求精 (程序设计课程已讲) (3)特殊问题,具体分析 设计打印下列图形的算法: 1 5 2 (课堂练习)

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

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

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

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

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

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

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

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

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

15 第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

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

17 第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.

18 1 2 A n-1 n C B

19 第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

20 第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);

21 第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问 题。

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

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

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

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

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

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

28 第3讲 算法工具与优化技巧 √算法优化技巧(自己复习、看书总结) 作业:p114, 例40;p115,例41

29 第3讲 算法工具与优化技巧 √习题 作业:p118,(9,10,12,15,20,27)

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


Download ppt "每节一经典 用系统的观点观察问题 总体设计,逐步求精 计算机科学学院 王小明 (博士/教授/博士生导师)"

Similar presentations


Ads by Google