[工学]《算法设计与分析》第02讲.ppt

第2讲 递归技术 2.1 递归技术概述 递归的基本思想 人们在解决一些复杂问题时，为了降低问题的复杂程度（如问题的规模等），一般总是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是在解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。 递归算法示例 2.1 Hanoi塔问题 2.3 递归方程的建立与求解 数学基础知识 定义：设x是任意的实数，则 ?x? 为大于或等于x的最小整数，?x? 为小于或等于x的最大整数。 很明显，对任给的实数x，有△x1和△x2，使得x = ?x? + △x1和x = ?x? - △x2，0≤△x1，△x2 1。 下面给出整数函数的一些性质： （1）?x? = ?x?，当且仅当x是整数； （2）?x? = ?x? +1，当且仅当x不是整数； （3）?- x? = - ?x?； （4）x – 1 ?x? ≤ x ≤ ?x? x + 1； （5）若n，x分别是整数和实数，实数x可以表示成2k+ △x或2k+1+△x，则有 ① ?x? n, 当且仅当xn; ② n≤ ?x? ，当且仅当n≤ x ； ③ ?x?≤ n ，当且仅当 x ≤ n ； ④ n ?x? ，当且仅当n x ； ⑤ ?x?=n，当且仅当x-1 n ≤ x, 或n ≤ x n +1; ⑥ ?x? =n，当且仅当x ≤ n x+1, 或n -1 x ≤ n ; ⑦ ?x± n ?= ?x? ± n ， ?x ± n ? = ?x? ± n; ⑧ ?x/2?= ? ?x?/2 ? 定义：设n是正整数，若n是2的幂，则存在正整数k，使得n = 2k，而k=log n ; 若n不是2的幂，则有正整数k，使得2k n 2k+1，而k= ?log n?。 此外，log n还有如下性质： （1）?log n? log n – 1; （2）?log n ? log n + 1; （3）n≤2 ?log n? ≤2n ; （4）n/2 2 ?log n? ≤n; （5）?log (n + 1) ? = ?log n? +1； （6）若n为大于1的奇数，则 ?log n ?= ?log（n-1）?； （7） = n ?log n? - 2 ?log n ? + 1 + 2。 2.3.1 递推方程 递归方程的求解---递推法(迭代法) 2.4 递归消除 阶乘函数 递归算法 fibonacci数列的递归算法 long fab(int n)????{????????if ( n == 1 || n == 2 )????????????return 1;????????else????????????return fab(n-1) + fab(n-2);????}???? fibonacci数列的非递归算法 long fabx(int n)????{????????if ( n == 1 || n == 2 )????????????return 1;????????????????long xx = 1;????????long yy = 1;????????long res = 0;??????? 先序遍历递归算法 /*先序遍历二叉树，递归算法*/Status PreOrderTraverse(BiTree T,Status(*PrintElement)(TElemType e)){ if(T){ if(PrintElement(T-data)) if(PreOrderTraverse(T-lchild,PrintElement)) if(PreOrderTraverse(T-rchild,PrintElement)) return OK; return ERROR;} 先序遍历非递归算法 void PreOrderUnrec(Bitree *t){??? Stack s;? ? StackInit(s);? ? Bitree *p=t;? ? ? ? while (p!=NULL || !StackEmpty(s))? ? {? ?? ???while (p!=NULL)? //遍历左子树? ?? ???{? ?? ?? ?? ?visite(p-data);? ?? ?? ?? ?push(s,p);? ?? ?? ?? ?p=p-lchild;??????????}????????????? 小结 本章从整数函数和对数函数的定义及其性质等预备知识开始，以Hanoi塔问题为实例逐步进行讲解递归技