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