1、棧與遞歸遞歸與回溯廣義表課件棧與遞歸遞歸與回溯廣義表課件一、棧和遞歸遞歸定義遞歸函數(shù)一、棧和遞歸遞歸定義遞歸定義先定義最基本的概念 再用已定義的概念定義新的概念例 命題演算公式的定義 （1） 單個命題變元符號是命題 （2） 如果A,B是命題，則 (A), (AB), (AB), (AB), （AB) 都是公式遞歸定義先定義最基本的概念例 命題演算公式的定義遞歸定義先定義最基本的概念 再用已定義的概念定義新的概念例 標識符的定義 （1）單個英文字母是標識符 （2）標識符后綴一個數(shù)字 或一個英文字母是標識符遞歸定義先定義最基本的概念例 標識符的定義遞歸函數(shù)的定義一個算法可以分解成 若干相同的小算法

2、 分解到某簡單的子算法時終止 有一個或幾個終止條件 遞歸：由其前面的值求當前值 遞歸必須導(dǎo)致終止條件 遞歸函數(shù)的定義一個算法可以分解成遞歸函數(shù)的例例 函數(shù) xn x0=1 xn=x*xn-1 n0 xn=xn-1/x n0遞歸函數(shù)的例例 函數(shù) xn遞歸函數(shù)的例函數(shù) C(n, m) C(0, m)=1, C(m, m)=1. C(n, m)=C(n-1,m-1)+C(n, m-1)遞歸函數(shù)的例函數(shù) C(n, m)#include / compute n! = n*(n-1)*(n-2).(2)(1), 0!=1 recursivelylong Factorial(long n) / if n =

3、 0, then 0! = 1; otherwise, n! = n*(n-1)! if (n = 0) return 1; else return n * Factorial(n - 1);#include / computvoid main (void) int i, n; / enter 4 positive integers and compute n! for each cout Enter 4 positive integers: ; for (i = 0; i n; cout n ! = Factorial(n) endl; void main (void)/*Enter 4 p

4、ositive integers: 0 7 1 4 0! = 1 7! = 5040 1! = 1 4! = 24*/*階乘堆棧 主程序參數(shù)44*Factorial(3)參數(shù)33*Factorial(2)參數(shù)22*Factorial(1)參數(shù)11*Factorial(0)參數(shù)0 Factorial(0) 1 1 2 6 24階乘堆棧 主程序參數(shù)44*Factorial(遞歸函數(shù) 先操作 后遍歷 例 void Fucnc(char ch) if(ch=z) coutch; Func(ch+1); 調(diào)用 Func(a);輸出 abcdefghijklmnopqrstuvwxyz遞歸函數(shù) 先操作 后

5、遍歷 例 void Fucnc(ch遞歸函數(shù) 先遍歷 后操作例 void Fucnc(char ch) if(ch=z) Func(ch+1); coutch; 調(diào)用 Func(a);輸出 zyxwvutsrqponmlkjihgfedcba遞歸函數(shù) 先遍歷 后操作例 void Fucnc(char遞歸函數(shù) 操作 遍歷 操作例 void Fucnc(char ch) if(ch=z) coutch; Func(ch+1); coutch; 調(diào)用 Func(a);輸出 abcdefghijklmnopqrstuvwxyz zyxwvutsrqponmlkjihgfedcba遞歸函數(shù) 操作 遍歷

6、操作例 void Fucn遞歸函數(shù) 遍歷 操作 遍歷例 void Fucnc(char ch) if(ch=d) Func(ch+1); coutch; Func(ch+1); 調(diào)用 Func(a);輸出 dcdbdcdadcdbdcd遞歸函數(shù) 遍歷 操作 遍歷例 void Fucnc河內(nèi)塔問題A BC河內(nèi)塔問題A BC河內(nèi)塔問題 將A塔上的金盤移到B塔上 ！要求 一次只能移動一個盤 大盤不能壓小盤A BCA河內(nèi)塔問題 將A塔上的金盤移到B塔上 ！要求 一次河內(nèi)塔問題 第一次A BC河內(nèi)塔問題 第一次A BC河內(nèi)塔問題 第二次A BC河內(nèi)塔問題 第二次A BC河內(nèi)塔問題 第三次A BC河內(nèi)塔問

7、題 第三次A BC河內(nèi)塔問題 第四次A BC河內(nèi)塔問題 第四次A BC 河內(nèi)塔問題 第五次A BC 河內(nèi)塔問題 第五次A BC河內(nèi)塔問題 第六次A BC河內(nèi)塔問題 第六次A BC河內(nèi)塔問題 第七次A BC河內(nèi)塔問題 第七次A BC河內(nèi)塔問題設(shè)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 河內(nèi)塔問題設(shè)n個金盤移動 F(n)次河內(nèi)塔問題程序#include #pragma hdrstop#include strcla

8、ss.h/ move n disks from startpeg to endpeg,/ using middlepeg as the intermediate peg河內(nèi)塔問題程序#include void 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 hanoi(int n, char A, charvoid main( ) int n; / numbe

9、r of disks and the peg names cout n; cout The solution for n = n endl; hanoi(n, A, B, C);void main( ) int n; / numb/* Enter the number of disks: 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 6

10、60 2 03 5 60 0 40 0 00 0 07 0 07回溯 此路不通，返回回溯 此路不通，返回回溯 此路不通，返回回溯 此路不通，返回 迷宮mazestruct Intersection 4 二、遞歸和回溯迷宮算法八皇后問題二、遞歸和回溯迷宮算法/ record that specifies the intersection you/ arrive at when departing left, forward or right/ from the current intersectionstruct Intersection int left; int forward; int r

11、ight;/ record that specifies the i#include #include #include class Maze int mazesize; int EXIT; Intersection *intsec; public: Maze(char *filename); int TraverseMaze(int intsecvalue);#include #include Maze:Maze(char *filename) ifstream fin; int i; fin.open(filename, ios:in | ios:nocreate); if (!fin)

12、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( );Maze:Maze(char *filename)回溯法一個變量控制遞歸用另一個變量來控制回溯出現(xiàn)特定情況時該變量取值0 回溯1。全局變量2。變量參數(shù) 引用變量，指針變量3。函數(shù)返回值 回溯法一個變量控制遞歸int Maze:Traverse

13、Maze(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 (TraverseMaze(intsecintsecvalue.right) cout

14、 intsecvalue ; return 1; return 0;int Maze:TraverseMaze(int int#include #pragma hdrstop#include maze.h / include the maze class#include #pragma hvoid 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;v

15、oid main (void) char filena/maze1.dat60 2 03 5 60 0 4 0 0 00 0 07 0 07 4 3 5 7 2 6 1/maze1.dat6 4 5 7 /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/maze2.dat11 1011 9 /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

16、 0 0 0 0 0 0 15 16 0 0 017 0 0 0 18 19 0 0 019/bigmaze.dat18/* Enter the data file name: 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迷宮的另一種模型

17、4 5 7 2 迷宮的另一種模型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迷宮的另一種模型1011 9 八皇后問題WWW兩皇后在同一行或同一列或同一對角線上互相殺死要求：一個棋盤上擺八個皇后，任意兩個都不互相殺死八皇后問題WWW兩皇后在同一行或同一列要求：一個棋盤上擺八個皇后的表示用二維數(shù)組表示8*8棋盤 皇后用棋盤上的格點表示用坐標表示皇后的位置 (a, 4) (1, 4)用一維數(shù)組表示皇后的位置 int q9; q1=4; 表示第一行第四列有一個皇后 q4=2; 表示第四行第二列有一個皇后皇后的表示用二維數(shù)

18、組表示8*8棋盤兩個皇后沖突的特征 (a1, b1)與 (a2, b2)沖突 當且僅當 a1= b1或 a2= b2 或 | a1- b1|=| a2- b2| qi與qj沖突 當且僅當 i= j 或 qi=qj 或 | i - j |=| qi - qj | 兩個皇后沖突的特征 (a1, b1)與 (a2, b2)三、廣義表LS=(a1, a2,an)長度 n每個 ai 1in 或是一個元素（原子），或是一個子廣義表。a1是表頭head, a2,an 是表尾。用小寫字母表示原子，大寫字母表示廣義表。三、廣義表LS=(a1, a2,an)廣義表的例A=( ) 長度為0的空表。B=(e) 只有一

19、個元素的表，長為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,).廣義表的例A=( ) 長度為0的空表。廣義表的存儲廣義表的結(jié)點標志域 表頭指針 表尾指針 tag=1 hp tp 表結(jié)點1標志域 原子域 表尾指針 tag=0 atom tp 表結(jié)點2廣義表的存儲廣義表的結(jié)點標志域 表頭指針 表尾指針 廣義表結(jié)點類定義enum ElemTagATOM, LIST;templatestruct GLNod

20、e ElemTag tag; union T atom; GLNode *hp; GLNode *tp; tag=1 hp tp 表結(jié)點1tag=0 atom tp 表結(jié)點2廣義表結(jié)點類定義enum ElemTagATOM, LI廣義表的鏈表表示1A1B0eC1 0e10a0b0cD1111E10a1廣義表的鏈表表示1A1B0eC1 0e10a0b廣義表結(jié)點類的補充定義enum ElemTagATOM, LIST;templateclass GLNode ElemTag tag; union T atom; GLNode *hp; GLNode *tp; public: GLNode(cons

21、t T& item, GLNode *t=NULL); GLNode(GLNode *h,GLNode *t); ElemTag GetType( )return tag; T& GetValue( ); GLNode* Next( ); Void SetValue(GLNode & x); ; 廣義表結(jié)點類的補充定義enum ElemTagATOM,廣義表結(jié)點類的實現(xiàn)template GLNode: GLNode(const T& item, GLNode*t=NULL) tag=ATOM; atom=item; temp.tp=t; 廣義表結(jié)點類的實現(xiàn)template template G

22、LNode:GLNode(GLNode *h,GLNode *t) tag=LIST; hp=h; tp=t;template template T& GLNode:GetValue( )if (tag=ATOM) return atom; else cout“no value”; return 0;template template GLNode* GLNode: Next( ) return tp;template template Void GLNode: SetValue(GLNode & x) tag=x.tag; tp=x.tp; if(tag=ATOM) atom=x.atom;

23、 else hp=x.hp; template Void GLNo廣義表類定義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( ); 廣義表類定義template public: GList(void); Glist(GLNode*p);

24、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 head void SetTail(Glist&L);public:templateGlist:GList(const GList& list) C

25、opyList(list):templatetemplate 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 template GLNode * Glist:GetNode( Node *h=NULL, Node *t=NULL) GLNode*p=new GLNode; p-tag=LIST; p-hp=h; p-tp=t; return p;template template void

26、Glist:FreeGLNode(GLNode *p) free p;template 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;template templatevoid Glist: ClearGList( ) if(first-tag=LIST) ClearGList(first-hp); ClearList(first-