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

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

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

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

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

hanoi算法分析第一種如果只有一個盤子，直接把盤子從a柱子移到c柱子第二種不只一個盤子，設(shè)有n只盤子。1.先把a柱子上的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可以直接出棧；否則出棧后要讓小一級的盤子n-1入棧，然后自己出棧，最后小一級的盤子n-1入棧，hanoi的棧實現(xiàn)

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

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