函數(shù)的遞歸調(diào)用與分治策略-展示頁
2024-08-19 15:25本頁面
【正文】 //include hanoi(int n,char t1,char t2,char t3){ if (n==1) cout1 t1 t3endl。當(dāng)n1時，只要把較小的(n1)片按移動規(guī)則從A移到B，再將剩下的最大的從A移到C（即中間“借助”B把金片從A移到C），再將B上的(n1)個金片按照規(guī)則從B移到C（中間“借助”A）。[分析]由金片的個數(shù)建立遞歸關(guān)系。移動的規(guī)則如下：這些金片只能在3根針間移動，一次只能一片，且任何時候都不允許將較大的金片壓在較小的上面。在A號針上從下到上套著從大到小的n個圓形金片。} [例3]Hanoi塔問題。 cinn。 else return(fibonacci(x1)+fibonacci(x2))。需要注意的是本例中對于N=3，A(N)的值與A(N1)和A(N2)都有關(guān)。從鍵盤輸入N，輸出A(N)。了解這兩個問題可加深對遞歸方法的理解。經(jīng)典遞歸問題以下討論兩個十分經(jīng)典的遞歸問題。}綜上，得出構(gòu)造一個遞歸方法基本步驟，即描述遞歸關(guān)系、確定遞歸邊界、寫出遞歸函數(shù)并譯為代碼，最后將程序完善。 cinn。 else return(n*f(n1))。}[步驟4]完善程序 主要的遞歸函數(shù)已經(jīng)完成，將程序依題意補充完整即可。[步驟3]寫出遞歸函數(shù)并譯為代碼 將步驟1和步驟2中的遞歸關(guān)系與邊界統(tǒng)一起來用數(shù)學(xué)語言來表示，即 N*(N1)! 當(dāng)N=1時n!= 1 當(dāng)N=0時再將這種關(guān)系翻譯為代碼，即一個函數(shù)：long f(int n){ if (n==0) return(1)。}main(){ coutf(10)。確定遞歸邊界十分重要，如果沒有確定遞歸邊界，將導(dǎo)致程序無限遞歸而引起死循環(huán)。在本例中，遞歸邊界為k=0，即0!=1。[步驟2]確定遞歸邊界 在步驟1的遞歸關(guān)系中，對大于k的Un的求解將最終歸結(jié)為對Uk的求解。注意到，當(dāng)N=1時，N!=N*(N1)!（N=1時，0!=1），這就是一種遞歸關(guān)系。[步驟1]描述遞歸關(guān)系 遞歸關(guān)系是這樣的一種關(guān)系。[分析]N!的計算是一個典型的遞歸問題。下面由一個求n的階乘的程序為例，總結(jié)出構(gòu)造遞歸方法的一般步驟。遞歸方法的構(gòu)造構(gòu)造遞歸方法的關(guān)鍵在于建立遞歸關(guān)系。遞歸方法具有易于描述和理解、證明簡單等優(yōu)點，在動態(tài)規(guī)劃、貪心算法、回溯法等諸多算法中都有著極為廣泛的應(yīng)用，是許多復(fù)雜算法的基礎(chǔ)。函數(shù)的遞歸調(diào)用與分治策略遞歸方法是算法和程序設(shè)計中的一種重要技術(shù)。遞歸方法即通過函數(shù)或過程調(diào)用自身將問題轉(zhuǎn)化為本質(zhì)相同但規(guī)模較小的子問題。遞歸方法中所使用的“分而治之”的策略也稱分治策略。這里的遞歸關(guān)系可以是遞歸描述的，也可以是遞推描述的。[例1]從鍵盤輸入正整數(shù)N（0=N=20），輸出N!。使用遞歸方法來描述程序，十分簡單且易于理解。設(shè){U1,U2,U3,…,Un…}是一個序列，如果從某一項k開始，Un和它之前的若干項之間存在一種只與n有關(guān)的關(guān)系，這便稱為遞歸關(guān)系。對于特定的K!，它只與K與(K1)!有關(guān)。這里的Uk稱為遞歸邊界（或遞歸出口）。對于任意給定的N!，程序?qū)⒆罱K求解到0!。例如以下程序：include int f(int x){ return(f(x1))。}它沒有規(guī)定遞歸邊界，運行時將無限循環(huán)，會導(dǎo)致錯誤。 else return(n*f(n1))。//include long f(int n){ if (n==0) return(1)。}main(){ int n。 coutendlf(n)。以下繼續(xù)引用一些例子來討論遞歸方法的應(yīng)用。它們的算法構(gòu)造同樣遵循剛剛得出的四個步驟。[例2]Fibonacci數(shù)列（兔子繁殖）問題：已知無窮數(shù)列A，滿足：A(1)=A(2)=1，A(N)=A(N1)+A(N2)（N=3）。[分析]遞歸關(guān)系十分明顯，由A(N)的表達式給出。[代碼]//include long fibonacci(int x){ if ( (x==1) || (x==2) ) return(1)。}main(){ int n。 coutendlfibonacci(n)。 [問題描述]在霍比特人的圣廟里，有一塊黃銅板，上面插著3根寶石針（分別為A號，B號和C號）。現(xiàn)要將A針上的金片全部移到C針上，且仍按照原來的順序疊置。從鍵
物理相關(guān)推薦
鄂ICP備17016276號-1