函數(shù)的遞歸調(diào)用與分治策略-全文預(yù)覽
【正文】 } return(1)。amp。l=2。 if (j=3) pj=1。 (a[l][j]==k) ) return(0)。l++) if ( (l!=i) amp。amp。l=9。由于我們是按順序填入數(shù)字的，看起來一個數(shù)字后面的數(shù)字并不在判斷能否填的范圍內(nèi)。首先考慮如何得出全部解的情況。（1）編程將下面圖中的九宮陣補充完整。 QuickSort(R,i+1,t)。 if(ij) { R[j]=R[i]。 i++。 { while( jiamp。在程序?qū)崿F(xiàn)是，本著“能排則排”的原則，只要第一個數(shù)小于j（或者第i個數(shù)小于最后一個數(shù)），即進行遞歸。如果在極端情況下，程序認為基準數(shù)和自身構(gòu)成逆序?qū)Γ瑒t將基準數(shù)與自身交換（這其實沒有作用）之后i遞增1，j遞減1（注意斜體字給出的對逆序?qū)Φ奶幚矸椒ǎ?，同樣對?到第j個數(shù)和第i到第n個數(shù)分別再進行一趟快速排序。如此反復(fù)，在交換過有限個逆序?qū)螅琲和j將越來越靠近，最后“相遇”，即i和j指向同一個數(shù)，暫且稱之為相遇數(shù)（極端情況下，如果一開始就不存在逆序?qū)Γ琲和j將直接“相遇”）。快速排序是程序設(shè)計中經(jīng)常涉及的一種排序算法。數(shù)學(xué)上許多有重要意義的計數(shù)問題都可以歸結(jié)為對Catalan數(shù)的研究。amp。}main(){ int n。如果用前兩種解法中的遞歸關(guān)系，程序會變得復(fù)雜且容易寫錯。[解法3] 把公式(1)中的自變量改為n+1，再將剛剛得出的公式(2)代入公式(1)，得到H(n+1)=∑H(i)*H(ni+2) （i=2,3,…,n） 由公式(1)H(n+1)=2*H(n)+∑H(i)*H(ni+2) （i=3,4,…,n1） 由H(2)=1H(n+1)=(4n6)/n*H(n) 由公式(2)H(n)=(4n10)/(n1)*H(n1) 公式(3)這是一個較之前兩種解法更為簡單的遞歸公式，還可以繼續(xù)簡化為H(n)=1/(n1)*C(n2,2n4) 公式(4)這就不需要再使用遞歸算法了。[解法2]從V1向除了V2和Vn外的n3個頂點可作n3條對角線。因此，以對角線V1Vi為一個剖分方案的剖分方案數(shù)為H(i)*H(ni+1)。[分析]Catalan數(shù)問題有著明顯的遞歸子問題特征。[問題描述]一個凸多邊形，通過不相交于n邊形內(nèi)部的對角線，剖分為若干個三角形。)。,39。 cinn。 coutn t1 t3endl。當(dāng)n1時，只要把較小的(n1)片按移動規(guī)則從A移到B，再將剩下的最大的從A移到C（即中間“借助”B把金片從A移到C），再將B上的(n1)個金片按照規(guī)則從B移到C（中間“借助”A）。移動的規(guī)則如下：這些金片只能在3根針間移動，一次只能一片，且任何時候都不允許將較大的金片壓在較小的上面。} [例3]Hanoi塔問題。 else return(fibonacci(x1)+fibonacci(x2))。從鍵盤輸入N，輸出A(N)。經(jīng)典遞歸問題以下討論兩個十分經(jīng)典的遞歸問題。 cinn。}[步驟4]完善程序 主要的遞歸函數(shù)已經(jīng)完成，將程序依題意補充完整即可。}main(){ coutf(10)。在本例中，遞歸邊界為k=0，即0!=1。注意到，當(dāng)N=1時，N!=N*(N1)!（N=1時，0!=1），這就是一種遞歸關(guān)系。[分析]N!的計算是一個典型的遞歸問題。遞歸方法的構(gòu)造構(gòu)造遞歸方法的關(guān)鍵在于建立遞歸關(guān)系。函數(shù)的遞歸調(diào)用與分治策略遞歸方法是算法和程序設(shè)計中的一種重要技術(shù)。遞歸方法中所使用的“分而治之”的策略也稱分治策略。[例1]從鍵盤輸入正整數(shù)N（0=N=20），輸出N!。設(shè){U1,U2,U3,…,Un…}是一個序列，如果從某一項k開始，Un和它之前的若干項之間存在一種只與n有關(guān)的關(guān)系，這便稱為遞歸關(guān)系。這里的Uk稱為遞歸邊界（或遞歸出口）。例如以下程序：include int f(int x){ return(f(x1))。 else return(n*f(n1))。}main(){ int n。以下繼續(xù)引用一些例子來討論遞歸方法的應(yīng)用。[例2]Fibonacci數(shù)列（兔子繁殖）問題：已知無窮數(shù)列A，滿足：A(1)=A(2)=1，A(N)=A(N1)+A(N2)（N=3）。[代碼]//i
物理相關(guān)推薦
鄂ICP備17016276號-1