第11讲 函数与过程二.ppt

函数与过程（二） 1、函数与过程的关系 和区别 2、递归算法 一.函数与过程的关系和区别 函数的定义格式 形式参数表 形式参数表 二.子程序之间的调用关系 三、递归 采用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决。 例：计算n! 用递归公式如下: ????????????? 1? 当 n=0 时?? n*fac(n-1) 当n0时 执行流程 fac(3) fac(2) fac(1) fac(0) 3*fac(2) 2*fac(1) 1*fac(0) fac(0)=1 如何设计递归算法 1.确定递归公式 2.确定边界(终了)条件 汉诺塔问题 有n个半径各不相同的圆盘，按半径从大到小，自下而上依次套在A柱上，另外还有B、C两根空柱。要求将A柱上的n个圆盘全部搬到C柱上去，每次只能搬动一个盘子，且必须始终保持每根柱子上是小盘在上，大盘在下。 var a,b,c,number:integer; procedure move(n: integer;a,b,c:char); begin ???? if n=1 then writeln(a,-,c) ???? else ???????? begin ????????????? move(n-1,a,c,b); ????????????? writeln(a,-,c); ????????????? move(n-1,b,a,c) ???????? end; end; begin ???? write(the number of dish:); ???? readln(number); ???? move(number,’A’,’B’,’C’); end. 要求找出具有下列性质的数的个数(包含输入的自然数n)： 先输入一个自然数n(n=500),然后对此自然数按照如下方法进行处理: ①. 不作任何处理; ②. 在它的左边加上一个自然数,但该自然数不能超过原数的一半; ③. 加上数后,继续按此规则进行处理,直到不能再加自然数为止. 样例:? 输入:? 6 满足条件的数为? ?6 ??????????????? 16 ??????????????? 26 ?????????????? 126 ?????????????? ? 36 ?????????????? 136 输出:? 6 var n,i:integer; ??? s:real; procedure qiu(x:integer); var k:integer; begin ???? if x0 then ??? ? begin ??????? ?? s:=s+1; ????? ???? for k:=1 to x div 2 do qiu(k) ???? end end; begin ???? readln(n);???? s:=0; ??? qiu(n); ??? writeln(s:2:0) end. 求m与n的最大公约数 分析：从数学上可以知道求m与n的最大公约数等价于求n与(m mod n)的最大公约数。这时可以把n当作新的m, (m mod n)当作新的n，这样问题又变成了求新的m与n的最大公约数……这种方法我们称为辗转相除法。 设两个整数分别为m和n，将m整除n得到一个余数r，若r=0，则除数n就是最大公约数，否则，将除数作为被除数，余数作为除数继续相除，直到余数=0为止。 Var  m,n:integer;function gys(a,b:integer):integer;var r:integer;begin r:=a mod b; if r=0 then gys:b else gys:=gys(b,r);end;begin readln(m,n); writeln(‘gys is:’,gys(m,n));end. 有一个人爬楼梯，他上梯子的方法可以一步走1级，也可以一步走2级。现在楼梯有n级，问有多少种爬楼梯的方法？ Var s,n:integer;function f(n:integer):intege