【练习2】因数分解
题目描述 各位在小学时都学过因数分解，都了解怎么样用纸笔计算 出结果，现在由你来教电脑做因数分解。因数分解就是把 一个数，切分为若干个质数的乘积，如 12=2^2 * 3 ,其中, 次方的符号以 ^ 来表示. 输入 一个整数n, 大于1 且 小于等于 1000000 输出 一个字串为整数n的因数分解答案，格式如样例。 样例输入 20 样例输出 2^2*5
2.
斐波那契(Fibonacci)数列用递归过程描述为： Funtion fb(n:integer):integer; Begin if n<3 then fb:=1 else fb:=fb(n-1)+fb(n-2); End; 上面的递归过程，调用一次产生二个新的调用，递归次数呈指数增长，时 间复杂度为O（2n）,把它改为非递归： x:=1;y:=1; for i:=3 to n do begin z:=y;y:=x+y;x:=z; end; 修改后的程序，它的时间复杂度为O（n）。 我们在编写程序时是否使用递归算法，关键是看问题是否适合用递归算法 来求解。由于递归算法编写的程序逻辑性强，结构清晰，正确性易于证明， 程序调试也十分方便，在NOIP中，数据的规模一般也不大，只要问题适合 用递归算法求解，我们还是可以大胆地使用递归算法。
在调用过程或函数之前，系统需完成三件事： ⑴为被调用过程的局部变量分配存储区； ⑵将所有的实在参数、返回地址等信息传递给被调用过程保存； ⑶将控制转移到被调过程的入口。 从被调用过程返回调用过程之前，系统也应完成三件工作： ⑴保存被调过程的计算结果； ⑵释放被调过程的数据区； ⑶依照被调过程保存的返回地址将控制转移到调用过程。
递归的概念
• 直接或间接地调用自身的算法称为递归算法。 用函数自身给出定义的函数称为递归函数。
从前有座山，山上有座庙，庙里有一个 老和尚在给小和尚讲故事，老和尚说： 从前有座山，山上有座庙，庙里有一个 老和尚在给小和尚讲故事，老和尚说： 从前有座山……
递归的概念
例1 阶乘函数 阶乘函数可递归地定义为：
汉诺塔问题
• 只有一个盘子的移动：AC • 两个盘子的移动：AB，AC，BC • n个盘子的移动(n>2)： o 将上面的n－1个盘子看成一个整体，则此问题被转换 为两个盘子的移动 o 而n－1个盘子的移动规则与此相同
汉诺塔游戏演示
汉诺塔问题的递归描述
• 当只移动一个盘子的时候，直接从起始柱移动到目标柱， 否则，执行如下操作： 1. 将前n-1盘子以相同的方法从起始柱移动到临时柱； 2. 将第n个盘子直接移动到目标柱；
递归



信息学奥赛解题三步曲： 1.看 （分析问题） 看清楚已知什么，求什么，也就是输入什么，输出什么； 准确区分问题的主要条件和次要条件； 把握数据规模，迅速提炼问题模型和原型； 2.想 （算法设计） 要先考虑人脑怎么做，再考虑如何编程让电脑去做； 要从时间复杂性和空间复杂性两方面对算法进行评价，尽量优化； 3.动手（代码编写） 选择一种语言，编写程序并调试运行； 样例数据、边界数据和极限数据都要调试； 经典算法的核心思想基本上是不会变化的，但是竞赛时候解决具体问题 的方法却千变万化。要想利用“不变”的算法，解决“万变”的问题， 不仅需要深刻理解经典算法的精髓思想、还要有丰富的解题经验、和一 定的分析问题，构建模型能力。 任何时候都是根据问题选择算法，不应该用算法来选择问题，本末不能 倒置。
• 因此，我们可以得到递归公式： F(n)=F(n-1)+F(n-2) • 而递归的终止条件则是： n=1或n=2时，F(n)=1
function F(k: integer): longint; begin if (k = 1) or (k = 2) then F := 1 else F := F(k - 1) + F(k - 2) end; begin read(n); writeln(F(n)); end.
n=3，f(3)=3*f(2)
思考：输入一串以‘!’结束的字符，按逆序输出。
program ex2； procedure rever； var c:char； begin read(c)； if c<>’!’ then rever; write(c)； end； begin {主程序} rever； end．
应用举例—Hanoi塔问题
例 Hanoi塔问题 设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这 些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号 为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍 按同样顺序叠置。在移动圆盘时应遵守以下移动规则： 规则1：每次只能移动1个圆盘； 规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上； 规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中 任一塔座上。
兔子出生演示
1 1
1月
2月
2
2 3
1
1
3月 4月
5
2
3
4
1
5月
• 从上面的分析可以看到，第n个月后兔子的数目有 两部分构成：1、上月的所有兔子；2、上月的所 有老兔子所生的小兔子。 • 因此，若我们记第n个月的兔子总数为F(n)、老兔 子数为G(n)的话，那么F(n)=F(n-1)+G(n-1)。 • 那么G(n)怎么得到呢？通过分析上图，我们可以 发现，第n个月的老兔子数等于第n-1个月的兔子 总数，因此上式中的G(n-1)=F(n-2)。
输入 hey! 输出 !yeh。
c=‘!’
procedure rever； var c：char； begin read(c)； if c<>'!' then rever; write(c)； end；
hey!
c=‘y’
c=‘e’ c=‘h’
procedure rever； var c:char； begin read(c)； if c<>'!' then rever; write(c)； end； procedure rever； var c：char； begin read(c)； if c<>'!' then rever; write(c)； end；
小结与思考
递归算法简单直观，是整个计算机算法和程序设计领 域一个非常重要的方面，必须熟练掌握和应用它。递 归算法在计算机中的执行过程比较复杂，需要用系统 栈进行频繁的进出栈操作和转移操作。递归转化为非 递归后，可以解决一些空间上不够的问题，但程序太 复杂。所以，并不是一切递归问题都要设计成非递归 算法。实际上，很多稍微复杂一点的问题（如汉诺塔 问题、二叉树的遍历、图的遍历、快速排序等），不 仅很难写出它们的非递归过程，而且即使写出来也非 常累赘和难懂。在这种情况下，编写出递归算法是最 佳选择。
第n个Fibonacci数可递归地计算如下： Function fib(n:integer):integer; Begin If n=0 then fib:=0 Else if n=1 then fib:=1 else fib:=fib(n-1)+fib(n-2) End;
应用举例
• 有一种兔子，出生后一个月就可以长大，然后再过一个月 一对长大的兔子就可以生育一对小兔子且以后每个月都能 生育一对。 现在，我们有一对刚出生的这种兔子，那么，n个月过后， 我们会有多少对兔子呢？假设所有的兔子都不会死亡。 • 输入：5 • 输出：5
递归算法的优缺点
优点：结构清晰，可读性强，而且容易用 数学归纳法来证明算法的正确性，因此它 为设计算法、调试程序带来很大方便。
缺点：递归算法的运行效率较低，无论是 耗费的计算时间还是占用的存储空间都比 非递归算法要多，递归的深度受到系统栈 空间的限制
递归算法转非递归算法
1. 递归转化为递推：当递归算法所涉及的数据定义形式是 递归的情况下，通常可以将递归算法转化为递推算法， 用递归的边界条件做为递推的边界条件。比如求阶乘、 斐波那契数列等。求阶乘的递推算法如下： s := 1; for i := 1 to n do s := s * i; writeln(s); 递归转化为回溯：对于可以用回溯算法解决的问题，也 可以用非递归的回溯来实现。如n皇后问题。
【练Байду номын сангаас1】阅读程序：
const num = 5; var n: integer; function r(n : integer) : integer; var i : integer; begin if n <= num then begin r := n; exit; end; for i :=1 to num do if r(n-i) < 0 then begin r:=i; exit; end; r:=-1; end; begin readln(n); writeln(r(n)); end. 输入 16 输出：__________
边界条件
n0 1 n! n(n 1)! n 0
递归方程 边界条件与递归方程是递归函数的二个要素，递归函 数只有具备了这两个要素，才能在有限次计算后得出 结果。
如何设计递归算法
1.确定递归公式 2.确定边界(终了)条件
Function f (n :integer) : longint; Begin if n = 0 then f:=1 else f:=n*f(n-1) End;
procedure rever； var c：char； begin read(c)； if c<>'!' then rever; write(c)； end；
程序中，c 是过程rever的局部变量。 每一次递归调用，都要为局部变量重 新分配单元，因此各层的变量c实际上 是不同的变量，它们分别用于保存执 行本层调用时的输入值。