第三章 递归详解.ppt

举例说明： F(a,b) {a=a+b; } Main() { a=2; b=3; f(a,b); A? } * 棋子移动问题 移动规则 每次必须同时移动相邻两个棋子 颜色不限，移动方向不限 每次移动必须跳过若干棋子 不能调换这两个棋子的位置 * n=4 _ step1 000_ _11101 (4,5)?(9,10) step2 0001011_ _1 (8,9)?(4,5) step3 0_ _1011001 (2,3)?(8,9) step4 010101_ _01 (7,8)?(2,3) step5 _ (1,2)?(7,8) 寻找递归出口 * n?5 0000011111_ _ step1 0000_ _111101 (5,6)?(11,12) step2 _01 (9,10)?(5,6) n?6 000000111111_ _ step1 00000_ _1111101 (6,7)?(13,14) step2 0000011111_ _01 (11,12)?(6,7) chess(n) 递归出口：n?4; 递归过程：n?4时； move (n,n?1)?(2n?1,2n?2)； move (2n?1,2n)?(n,n?1); call chess(n?1); * 棋子的移动问题 Procedure Chess(n) if n=4 then move (4,5) ?(9,10) move (8,9) ?(4,5) move (2,3) ?(8,9) move (7,8) ?(2,3) move (1,2) ?(7,8) else move (n, n+1) ?(2n+1, 2n+2) move (2n?1, 2n) ?(n, n+1) call Chess(n-1) endif End Chess 递归出口 递归调用 A(9)←A(4) A(10)←A(5) * 例3.6 求n个元素的全排列 设A={a1,a2,…,an}是要进行排列的n个元素的集合， n?1 输出a1 n?2 输出a1a2 a2a1 n?3 输出a3a1a2 a3a2a1 a1a2a3 a1a3a2 a2a1a3 a2a3a1 分析n=3，排列按如下步骤进行： a3之后跟a1,a2的所有全排列； 在上述全排列里，a3和a1位置互换； 在上述全排列里，a3和a2位置互换。 * 求n个元素的全排列 range(A) = a1range(A1), a2range(A2),…, anrange(An) 集合A用数组实现 range(A,1,n)： 递归出口：range(A, n, n) 递归调用：使得集合所有元素都可以作为前缀出现 A-a1 A-a2 A-an * 求n个元素的全排列 procedure range(A, k, n) if k?n then print(A) else for i ?k to n do A(k) ? A(i) call range(A,k?1,n) A(k) ? A(i) repeat endif end range 递归出口，打印整个数组A。 A(i)与A(k)值互换 缺省时，认为形参是in型，其值变化时不回传。 call range(A,1,n) * range(A,1,3) If 1=3 then print(A) els