递归迷宫等.pptVIP

* * * 递归 1.递归的概念 1)定义是递归的 2)数据结构是递归的 3)问题的解法是递归的 2.迷宫问题 3. 递归过程的实现 4. 利用栈实现的迷宫问题的非递归解法 * * 递归 1.递归的概念 n!= 1 n=0 n*(n-1)! n0 若一个对象部分地包含它自己或用它自己给自己定义，则称这个对象是递归的。 若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。 *测试终结递归的条件 递归出口 *n问题化为n-1问题（或着大问题化为小问题） * * 三种常用到递归的方法 定义是递归的。 数据结构是递归的。 问题的解法是递归的。 1)定义是递归的 例1：如上面求n！的定义就是递归的。 long factorial(long n) { if(n==0)return 1;//递归终结条件 else return n*factorial(n-1);//n问题化为n-1问题 } * * 下面看一下求factorial（3） f(3) f(2) f(1) f(0) n=3 n=2 n=1 n=0 6 n*f(2) n*f(1) n*f(0) 3*2 2*1 1*1 long factorial(long n) { if(n==0)return 1;//递归终结条件 else return n*factorial(n-1);//n问题化为n-1问题 } * * 例2 斐波那契数列（Fibonacci) 0，1，1，2，3，5，8，…… 以fn表示数列中第n个数，fn的递归定义： n 当n=0，1时 Fib(n)= Fib(n-1)+Fib(n-2) 当n1时 long Fib(long n) { if(n=1)return n; else return Fib(n-1)+Fib(n-2); } * * 2）数据结构是递归的 链表就是一种递归数据结构。 data link first 是一个单链表 first …… 是一个单链表 指向的也是一个单链表 ^ ^ * * 数据结构是递归的，则写算法采用递归方法是最方便的。 例1.查找非空单链表的最后一个结点并打印其数据域。 templateclass typevoid find(listnodetype*f) { if(f link==null) coutf dataendL; else find(f link); } 例2.查找非空单链表中值为x的结点，并输出之。 templateclass typevoid print(listnodetype*f) { if(f!=null) if(f data==x)coutf dataendL; else print(f link); } * * 3）问题的解法是递归的 （Hanoi塔） A B C 从A柱移到C柱：每次移一片盘，而且不允许大盘在小盘上。 分析：1.先将n-1个盘由A B(递归） 2.将一个盘由A C 3.将n-1个盘由B C(递归） n * * #include iostream.h #include “strclass.h” //字符串类的原型文件 Void Hanoi (int n,string A,string B,string C) {