离散数学-递归(精品·公开课件).pptVIP

离散数学 黄晓宇 HuangSir@ 本讲内容 递归算法设计 简单的递归算法复杂度分析 回顾 阶乘 选择排序（P316） 选择排序（二） Procedure election_sort(S,n) // basic if n=1 then return // find max max_index :=1 for i:=2 to n do if Si Smax_index then max_index :=i //move swap(si, Smax_index) call election_sort(S,n-1) end election_sort 时间复杂度分析 bn = n-1+ bn-1 = bn-1 + n-1 = (bn-2 + n-2) + n-1 = (bn-3 + n-3) + n-2 + n-1 = b1 +1+2+3+ . . . +(n-1) = 0+ 1+2+3+ . . . +(n-1) = (n-1)*n/2= ?(n2 ) 递归关系 对序列a1, . . . , an，使用a1，a2… an－1表示an的等式称为递归关系。 显式地给出的a1, a2. . . , 的有限项，称为初始条件。 递归举例（Fibonacci序列）： fn = fn-1 + fn-2 （n ? 3） f1 =1 f2 =2 字符串 Sn不含111的n位二进制字符串的个数，计算Sn 。 字符串（二） Sn不含111的n位二进制字符串，打印出所有Sn。 Hanoi塔 A、B、C三根圆柱，A柱上有n个圆盘，其中小盘在大盘上方，要把A上的所有盘都移到B上，每次只能移一个盘，而且移动过程中三根圆柱上的小盘都必须在大盘上方，最少要移多少步？ Hanoi塔（二） 算法设计（一） 给出m×n走方格问题的所有解。 算法设计（二） P296：为序列a1×a2×a3×…×an添加括号（1）对任意n，编程实现所有编号方法；（2）证明加括号方法数为Cn-1 （n?2） 。 例：当n=3时，有两种加法： （（a1×a2）×a3）、 （a1×（a2×a3 ）） 递归的应用－树型控件 * * 一个递归函数（伪代码）是调用自身的函数。一个递归算法是包含递归函数的算法。 递归算法的基本思想：分而治之。 即将问题分解成与初始问题同类型的子问题来求解，每一个子问题又可以继续分解……依次类推，直到这个过程得到的子问题可以通过一个直接的办法求解。 最后，通过组合子问题的解就可以得到初始问题的解。 int Factorial(int n) { if(n=1) return 1; return n*Factorial(n-1); } Input: s1 , . . ., sn和n Output:以递增顺序排列的s1 , . . ., sn 递归关系? Sort(s,n)＝Sort(s-max{s},n-1)+max{s} b1 =0 1-7 ：0 8 ：n-1 9-11: 0 12: bn-1 bn = n-1+ bn-1 以0开始的： Sn-1 以10开始的： Sn-2 以110开始的： Sn-3 Sn= Sn-1+ Sn-2+ Sn-3 n ?4 PrintS(S,n)? PrintS(S,n-1)+0 PrintS(S,n-2)+01 PrintS(S,n-3)+011 算法实现？参数设计？ A B C 初始状态和移动过程中的要求同上， 如何移？请设计算法。 (n,0,0) (1,0,n-1) (0,n,0) (0,1,n-1) (n-1,0,0) m×n *