栈与递归递归与回溯广义表ppt课件

1、一、栈和递归递归定义递归函数递归定义先定义最根本的概念 再用已定义的概念定义新的概念例 命题演算公式的定义 1 单个命题变元符号是命题 2 假设A,B是命题，那么 (A), (AB), (AB), (AB), AB) 都是公式递归定义先定义最根本的概念 再用已定义的概念定义新的概念例 标识符的定义 1单个英文字母是标识符 2标识符后缀一个数字 或一个英文字母是标识符递归函数的定义一个算法可以分解成 假设干一样的小算法 分解到某简单的子算法时终止 有一个或几个终止条件 递归：由其前面的值求当前值 递归必需导致终止条件 递归函数的例例 函数 xn x0=1 xn=x*xn-1 n0 xn=xn-1

2、/x n0递归函数的例函数 C(n, m) C(0, m)=1, C(m, m)=1. C(n, m)=C(n-1,m-1)+C(n, m-1)#include / compute n! = n*(n-1)*(n-2).(2)(1), 0!=1 recursivelylong Factorial(long n) / if n = 0, then 0! = 1; otherwise, n! = n*(n-1)! if (n = 0) return 1; else return n * Factorial(n - 1);void main (void) int i, n; / enter 4 po

3、sitive integers and compute n! for each cout Enter 4 positive integers: ; for (i = 0; i n; cout n ! = Factorial(n) endl; /*Enter 4 positive integers: 0 7 1 4 0! = 1 7! = 5040 1! = 1 4! = 24*/阶乘堆栈阶乘堆栈 主程序参数4 4*Factorial(3)参数3 3*Factorial(2)参数2 2*Factorial(1)参数1 1*Factorial(0)参数0 Factorial(0) 1 1 2 6

4、24递归函数递归函数 先操作先操作 后遍历后遍历 例 void Fucnc(char ch) if(ch=z) coutch; Func(ch+1); 调用 Func(a);输出 abcdefghijklmnopqrstuvwxyz递归函数递归函数 先遍历先遍历 后操作后操作例 void Fucnc(char ch) if(ch=z) Func(ch+1); coutch; 调用 Func(a);输出 zyxwvutsrqponmlkjihgfedcba递归函数递归函数 操作操作 遍历遍历 操作操作例 void Fucnc(char ch) if(ch=z) coutch; Func(ch+1

5、); coutch; 调用 Func(a);输出 abcdefghijklmnopqrstuvwxyz zyxwvutsrqponmlkjihgfedcba递归函数递归函数 遍历遍历 操作操作 遍历遍历例 void Fucnc(char ch) if(ch=d) Func(ch+1); coutch; Func(ch+1); 调用 Func(a);输出 dcdbdcdadcdbdcd河内塔问题A BC河内塔问题河内塔问题 将将A塔上的金盘移到塔上的金盘移到B塔上塔上 ！要求 一次只能挪动一个盘 大盘不能压小盘A BCA河内塔问题 第一次A BC河内塔问题 第二次A BC河内塔问题 第三次A B

6、C河内塔问题 第四次A BC 河内塔问题 第五次A BC河内塔问题 第六次A BC河内塔问题 第七次A BC河内塔问题河内塔问题设n个金盘挪动 F(n)次F(1)=1F(n)=F(n-1)+1+F(n-1)=2*F(n-1)+1 F(n)+1=2*(F(n-1)+1) =22*(F(n-2)+1) = =2n-1*(F(1)+1)=2n F(n)=2n-1 河内塔问题程序河内塔问题程序#include #pragma hdrstop#include strclass.h/ move n disks from startpeg to endpeg,/ using middlepeg as the

7、 intermediate pegvoid hanoi(int n, char A, char B, char C) if (n = 1) cout “move A B endl; else hanoi(n-1,A, C, B); cout “move A B endl; hanoi(n-1, C, B, A); void main( ) int n; / number of disks and the peg names cout n; cout The solution for n = n endl; hanoi(n, A, B, C);/* Enter the number of dis

8、ks: 3The solution for n = 3move A Bmove A Cmove B Cmove A Bmove C Amove C Bmove B C*/ 迷宫mazestruct Intersectionint left; int forword; int right; 4 3 5 2 1 7 660 2 03 5 60 0 40 0 00 0 07 0 07回溯 此路不通，前往回溯 此路不通，前往回溯 此路不通，前往回溯 此路不通，前往二、递归和回溯迷宫算法八皇后问题/ record that specifies the intersection you/ arrive a

9、t when departing left, forward or right/ from the current intersectionstruct Intersection int left; int forward; int right;#include #include #include class Maze int mazesize; int EXIT; Intersection *intsec; public: Maze(char *filename); int TraverseMaze(int intsecvalue);Maze:Maze(char *filename) ifs

10、tream fin; int i; fin.open(filename, ios:in | ios:nocreate); if (!fin) cerr The maze data file filename cannot be opened! mazesize; intsec = new Intersectionmazesize+1; for (i = 1; i intseci.left intseci.forward intseci.right; fin EXIT; fin.close( );回溯法回溯法一个变量控制递归用另一个变量来控制回溯出现特定情况时该变量取值0 回溯1。全局变量2。变

11、量参数 援用变量，指针变量3。函数前往值 int Maze:TraverseMaze(int intsecvalue) if (intsecvalue 0) if (intsecvalue = = EXIT) cout intsecvalue ; return 1; else if (TraverseMaze(intsecintsecvalue.left) cout intsecvalue ; return 1; else if (TraverseMaze(intsecintsecvalue.forward) cout intsecvalue ; return 1; else if (Trav

12、erseMaze(intsecintsecvalue.right) cout intsecvalue ; return 1; return 0;#include #pragma hdrstop#include maze.h / include the maze classvoid main (void) char filename32; cout filename; Maze M(filename); if (M.TraverseMaze(1) cout nYou are free! endl; else cout No path out of the maze endl;/maze1.dat

13、60 2 03 5 60 0 4 0 0 00 0 07 0 07 4 3 5 7 2 6 1/maze2.dat11 0 2 03 0 50 0 40 0 06 7 00 0 08 0 09 0 00 11 100 0 00 0 0121011 9 8 7 4 6 3 2 5 1/bigmaze.dat180 2 0 3 8 0 7 4 0 0 6 5 0 0 00 0 0 0 0 0 9 0 0 0 0 10 14 0 1112 13 0 0 0 0 0 0 0 0 15 16 0 0 017 0 0 0 18 19 0 0 019/* Enter the data file name:

14、maze1.dat7 6 2 1You are free!Enter the data file name: maze2.datNo path out of the mazeEnter the data file name: bigmaze.dat19 17 16 14 10 9 8 2 1You are free.*/ 4 3 5 7 2 6 1 0 0 0 0 0 0 0 0 0 0 0 0 0迷宫的另一种模型迷宫的另一种模型迷宫的另一种模型迷宫的另一种模型1011 9 8 74 6 3 2 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0八皇后问

15、题八皇后问题WWW两皇后在同一行或同一列或同一对角线上相互杀死要求：一个棋盘上摆八个皇后，恣意两个都不相互杀死皇后的表示皇后的表示用二维数组表示8*8棋盘 皇后用棋盘上的格点表示用坐标表示皇后的位置 (a, 4) (1, 4)用一维数组表示皇后的位置 int q9; q1=4; 表示第一行第四列有一个皇后 q4=2; 表示第四行第二列有一个皇后两个皇后冲突的特征两个皇后冲突的特征 (a1, b1)与 (a2, b2)冲突 当且仅当 a1= b1或 a2= b2 或 | a1- b1|=| a2- b2| qi与qj冲突 当且仅当 i= j 或 qi=qj 或 | i - j |=| qi -

16、qj | 三、广义表三、广义表LS=(a1, a2,an)长度 n每个 ai 1in 或是一个元素原子，或是一个子广义表。a1是表头head, a2,an 是表尾。用小写字母表示原子，大写字母表示广义表。广义表的例广义表的例A=( ) 长度为0的空表。B=(e) 只需一个元素的表，长为1。C=(a,(b,c,d) 长度为2的广义表，第二个 元素是长度为3的子表。D=(A,B,C) 长度为3的广义表，三个 元素都是长度为3的子表。 D=( ),(e),(a,(b,c,d)E=(a,E) 递归定义的表。 E=(a,(a,(a,).广义表的存储广义表的存储广义表的结点标志域标志域 表头指针表头指针

17、表尾指针表尾指针 tag=1 hp tp 表结点1标志域标志域 原子域原子域 表尾指针表尾指针 tag=0 atom tp 表结点2广义表结点类定义广义表结点类定义enum ElemTagATOM, LIST;templatestruct GLNode ElemTag tag; union T atom; GLNode *hp; GLNode *tp; tag=1 hp tp 表结点1tag=0 atom tp 表结点2广义表的链表表示广义表的链表表示1 A1B0 e C1 0 e10 a0 b0 c D11 11E10 a1广义表结点类的补充定义广义表结点类的补充定义enum ElemTag

18、ATOM, LIST;templateclass GLNode ElemTag tag; union T atom; GLNode *hp; GLNode *tp; public: GLNode(const T& item, GLNode *t=NULL); GLNode(GLNode *h,GLNode *t); ElemTag GetType( )return tag; T& GetValue( ); GLNode* Next( ); Void SetValue(GLNode & x); ; 广义表结点类的实现广义表结点类的实现template GLNode: GL

19、Node(const T& item, GLNode*t=NULL) tag=ATOM; atom=item; temp.tp=t; template GLNode:GLNode(GLNode *h,GLNode *t) tag=LIST; hp=h; tp=t;template T& GLNode:GetValue( )if (tag=ATOM) return atom; else cout“no value; return 0;template GLNode* GLNode: Next( ) return tp;template Void GLNode: SetValue(

20、GLNode & x) tag=x.tag; tp=x.tp; if(tag=ATOM) atom=x.atom; else hp=x.hp; 广义表类定义广义表类定义template class GList GLNode *first; GLNode *GetNode(const T&item, Node *t=NULL); GLNode *GetNode(Node *h=NULL, Node *t=NULL); void FreeGLNode(GLNode *p); void CopyList(const GList& list); void ClearGList(

21、 ); public: GList(void); Glist(GLNode*p); Glist(GLNode&x,Glist&list); Glist(GList&head,Glist&tail); GList(const GList& list); GList(void); GLNode *First( ); GLNode& Head( ); GLNode *Tail( ); void Push(GLNode&x);/add node x as head void SetHead(GLNode&x);/replace x to

22、head void SetTail(Glist&L);templateGlist:GList(const GList& list) CopyList(list):template GLNode * Glist: GetNode(const T& item, Node *t=NULL) GLNode *p=new GLNode; p-tag=ATOM; p-atom=item; p-tp=t; return p; template GLNode * Glist:GetNode( Node *h=NULL, Node *t=NULL) GLNode*p=new GLNode

23、; p-tag=LIST; p-hp=h; p-tp=t; return p;template void Glist:FreeGLNode(GLNode *p) free p;template GLNode* GList:CopyList( const GList& list)GLNode*p,*q; q=this; if(list.first!=NULL) p=new GLNode; p-tag=list.first-tag; if(p.-tag=ATOM) p-atom=list.first-atom; elae p-hp=CopyList(list.first-hp); p-tp=CopyList(list.first-tp); this=p; q.ClearList( ); return p;templatevoid Glist: ClearGList( ) if(first-tag=LIST) ClearGList(first-hp); ClearList(fir