棧實(shí)現(xiàn)遞歸 課件

棧實(shí)現(xiàn)遞歸CONTENTS遞歸的涵義漢諾塔問題問題分析

用棧實(shí)現(xiàn)在運(yùn)行的過程中調(diào)用自己。要素1子問題須與原始問題為同樣的事，且更為簡(jiǎn)單要素2不能無限制地調(diào)用本身，須有個(gè)出口，化簡(jiǎn)為非遞歸狀況處理遞歸的涵義遞歸算法一般用于解決三類問題第一類第三類第二類數(shù)據(jù)的定義是按遞歸定義的問題解法按遞歸算法實(shí)現(xiàn)。這類問題雖則本身沒有明顯的遞歸結(jié)構(gòu)，但用遞歸求解比迭代求解更簡(jiǎn)單數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的。由于結(jié)構(gòu)本身固有的遞歸特性，則它們的操作可遞歸地描述。Fibonacci函數(shù)二叉樹、廣義表Hanoi問題遞歸算法的經(jīng)典問題

n!字符串全排列八皇后問題hanoi

問題來源問題是源于印度一個(gè)古老傳說的益智玩具。大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤。問題描述有三根相鄰的柱子，標(biāo)號(hào)為A,B,C，A柱子上從下到上按金字塔狀疊放著n個(gè)不同大小的圓盤，要把所有盤子一個(gè)一個(gè)移動(dòng)到柱子B上，并且每次移動(dòng)同一根柱子上都不能出現(xiàn)大盤子在小盤子上方，請(qǐng)問至少需要多少次移動(dòng)hanoi的輸入柱子名開始端a目的端b借助端c盤子數(shù)nhanoi(intn,chara,charb,charc)hanoi的輸出移動(dòng)過程按照先后移動(dòng)的盤子編號(hào)n從哪根柱子移到哪根柱子移動(dòng)的步數(shù)stepreturnstep;cout<<"disknmovefromxtoy";hanoi的動(dòng)圖實(shí)現(xiàn)

hanoi算法分析第一種如果只有一個(gè)盤子，直接把盤子從a柱子移到c柱子第二種不只一個(gè)盤子，設(shè)有n只盤子。1.先把a(bǔ)柱子上的n-1只盤子柱子移到c柱子,借助b；2.把最大的盤子直接從a柱子移到c柱子；3.把b柱子上的n-1只盤子子移到c柱子,借助a柱。if(n==1){step++;output<<"movenfromatob.";}hanoi(n-1,a,c,b);move(n,a,c);hanoi(n-1,b,c,a)入棧：最大的盤子n先入棧出棧：最小的盤子1可以直接出棧；否則出棧后要讓小一級(jí)的盤子n-1入棧，然后自己出棧，最后小一級(jí)的盤子n-1入棧，hanoi的棧實(shí)現(xiàn)

出棧的條件：設(shè)標(biāo)志位tag==1時(shí)代碼

inthanio(intn){ nodex; SeqStack<int>s; intstep=0; s.Push(n,n,'a','b','c'); while(!s.Empty()){ s.Pop(x); if(x.tag==1) cout<<"第"<<++step<<"步:"<<'\t'<<"將盤子"<<x.n<<"從"<<x.a<<"移到"<<x.c<<endl; else{ s.Push(x.n-1,x.n-1,x.b,x.a,x.c); s.Push(1,x.n,x.a,x.b