函數(shù)的遞歸調(diào)用與分治策略-在線瀏覽
2024-09-14 15:25本頁面
【正文】 盤輸入n，要求給出移動的次數(shù)和方案。當(dāng)n=1時，只要將唯一的金片從A移到C即可。本題的特點在于不容易用數(shù)學(xué)語言寫出具體的遞歸函數(shù)，但遞歸關(guān)系明顯，仍可用遞歸方法求解。 else { hanoi(n1,t1,t3,t2)。 hanoi(n1,t2,t1,t3)。 coutPlease enter the number of Hanoi:。 coutAnswer:endl。A39。B39。C39。}函數(shù)遞歸調(diào)用的應(yīng)用與分治策略許多算法都采用了分治策略求解，而可以說分治與遞歸是一對孿生兄弟，它們經(jīng)常同時被應(yīng)用于算法的設(shè)計中。[例4]Catalan數(shù)問題。求不同的剖分方案總數(shù)H(n)。例如，n=5時H(5)=5。在計算Catalan數(shù)時雖然可以推導(dǎo)出只關(guān)于n的一般公式，但在推導(dǎo)過程中卻要用到遞歸公式。[解法1]對于多邊形V1V2…Vn，對角線V1Vi（i=3,4,…,n1）將其分為兩部分，一部分是i邊形，另一部分是ni+1邊形。還有一種的特殊情形，是對角線V2Vn將其分為一個三角形V1V2Vn和一個n2+1邊形。于是得到公式：H(n)=∑H(i)*H(ni+1) （i=2,3,…,n1） 公式(1)H(2)=1有了這個遞歸關(guān)系式，就可以用遞推法或遞歸法解出H(n)。每一條對角線V1Vi把多邊形剖分成兩部分，剖分方案數(shù)為H(i)*H(ni+2)，由于Vi可以是V3V4…Vn1中的任一點，且V1可換成V2，V3，…，Vn中任一點也有同樣的結(jié)果。由公式(2)和H(2)=1，同樣可以用遞推法或遞歸法解出H(n)。然而在程序設(shè)計上，公式(4)反而顯得更加復(fù)雜，因為要計算階乘。代碼相當(dāng)簡單，這都?xì)w功于剛才的推導(dǎo)。因此，有時對具體問題將遞歸關(guān)系公式進行必要的化簡也是至關(guān)重要的。 else return((4*x10)*f(x1)/(x1))。 cout\nPlease input N for a Catalan number:。 if ( (n=MAXN) amp。 (n=3) ) coutThe answer is:f(n)。注意函數(shù)f中的斜體部分，按照公式(4)計算時一定要先進行乘法再進行除法運算，因為(4*x10)并不總能整除(x1)，如果先進行除法則除出的小數(shù)部分將自動被舍去，從而導(dǎo)致得到不正確的解?？梢钥吹?，本例中的遞歸關(guān)系經(jīng)簡化還是相當(dāng)簡單的。[例5]快速排序問題。它的最好時間復(fù)雜度為O(nlog2n)，最差為O(n2)，是一種不穩(wěn)定的排序方法（大小相同的數(shù)在排序后可能交換位置）。一旦發(fā)現(xiàn)這樣的i和j（暫且稱之為一個“逆序?qū)Α保瑒t把第i個數(shù)和第j個數(shù)交換位置，這樣它們就不再是逆序?qū)α?，緊接著再將i遞增1，j遞減1。相遇后就保證數(shù)列中沒有逆序?qū)α耍ǔ嗽谏鲜龅臉O端情況下基準(zhǔn)數(shù)和自身也算構(gòu)成一個逆序?qū)?，注意粗體字給出的逆序?qū)Φ亩x）。此時，遞歸調(diào)用函數(shù)，對第1到第j個數(shù)和第i到第n個數(shù)分別再進行一趟快速排序。最后的問題就是確定遞歸邊界。這就是遞歸的邊界。[主程序（遞歸函數(shù)體）]void QuickSort(RecType R[ ],int s,int t){ int i=s,j=t,k。 if (st) { temp=R[s] // 用區(qū)間第1個記錄作為基準(zhǔn) while( i!=j) //從兩端向中間交替掃描，直至i=j。amp。 if(ij) { R[i]=R[j]。 } while( ijamp。R[i].key) i++。 j。 QuickSort(R,s,i1)。}} [例6]“九宮陣”智力游戲。請在每個空白小格子里面填上1～9的數(shù)字，使每個數(shù)字在每個九宮格內(nèi)以及在整個九宮陣中的每行、每列上均出現(xiàn)一次。（2）討論是否可能給出“九宮陣”的全部解？[分析]本題可利用回溯法解決，其基本思想為深度優(yōu)先搜索（DFS），這也是一種以分治策略為基礎(chǔ)的算法。這一點保證了解法的效率。解空間樹容易構(gòu)造，只需按順序（從第一行第一個數(shù)字開始到第一行最后一個，然后第二行……，一直到最后一行最后一個數(shù)字）“嘗試”填入數(shù)字即可。如果可以，返回1，否則返回0。但為了解決題中某個特解問題的方便，還是引入較為嚴(yán)謹(jǐn)?shù)呐袛喾椒ā? //1. Check the line for (l=1。l++) if ( (l!=
物理相關(guān)推薦
鄂ICP備17016276號-1