首页|嵌入式系统|显示技术|模拟IC/电源|元件与制造|其他IC/制程|消费类电子|无线/通信|汽车电子|工业控制|医疗电子|测试测量
首页 > 分享下载 > 常用文档 > 清华大学电子工程系课件——常用算法设计之二

清华大学电子工程系课件——常用算法设计之二

资料介绍
清华大学电子工程系课件——常用算法设计之二
常用算法设计(2)
孙甲松
清华大学电子工程系
sun@thsp.ee.tsinghua.edu.cn

2007.9.
5. 递归法
内容要点
(a)递归法是描述算法的一种强有力的方法,
其思想是:将N=n时不能得出解的问题,设
法递归(压栈)将其转化为求n-1,n-2,……
的问题,一直持续到N=0或1的初始情况,由
于初始情况的解可以直接给出或方便得到,
因此开始层层退栈,从而得到N=2,
3,……,n时的解,得到最终结果。
(b)用递归法写出的程序简单易读,但往往效
率不高,因为每一次的递归函数调用都要压
栈退栈。同时递归次数也不能无限制,因为
每一次的递归函数调用都要压栈占用内存,
而计算机的内存是有限的。
5. 递归法 (2)
学习难点
递归程序的关键是,对于一个问题,要找出其递归
关系和初始值。方法之一是利用归纳法把一个问题
归纳总结出递归式,加上初始条件,从而编写出递
归函数。
对于单变量的递归问题f(n),步骤是:
(a)当n=1或0时,可以得到f(n)的值;
(b)假设小于等于n-1时,都可以得到f(n) 的值;
( c) 则 对 于 n, 找 出 f(n) 与 f(n-1),f(n-2),……
的关系式:f(n)=F(f(n-1),f(n-2),……);
(d)开始编写递归程序
5. 递归法 (3)
【例 1 】编程求解 Hanoi 塔问题:即有 n 个盘
子在 A 处,盘子从大到小,最上面的盘子
最小,现在要把这 n 个盘子从 A 处搬到 C 处,
可以在 B 处暂存,但任何时候不能出现大
的压在小的上面的情况。
5. 递归……
标签:算法设计清华
清华大学电子工程系课件——常用算法设计之二
本地下载

评论

DY翔宇· 2011-03-18 19:16:50
谢谢啊