iiraaa函數(shù)的遞歸調(diào)用與分治策略-在線瀏覽
2024-09-03 11:45本頁面
【正文】 n==1) cout1 t1 t3endl。 coutn t1 t3endl。 }}main(){ int n。 cinn。 hanoi(n,39。,39。,39。)。下面討論著名的Catalan數(shù)問題，人們在對它的研究中充分應(yīng)用了分治策略。[問題描述]一個凸多邊形，通過不相交于n邊形內(nèi)部的對角線，剖分為若干個三角形。H(n)即為Catalan數(shù)。[分析]Catalan數(shù)問題有著明顯的遞歸子問題特征。下面討論三種不同的解法，其中第三種解法沒有使用遞歸，它是由前兩種解法推導(dǎo)而出的。因此，以對角線V1Vi為一個剖分方案的剖分方案數(shù)為H(i)*H(ni+1)。為了讓它同樣符合粗體字給出的公式，規(guī)定H(2)=1。[解法2]從V1向除了V2和Vn外的n3個頂點可作n3條對角線。考慮到同一條對角線在2個頂點被重復(fù)計算了一次，于是對每個由頂點和對角線確定的剖分方案都乘以1/2，故有H(n)=n∑(1/2)H(i)*H(ni+2) （i=3,4,…,n1）把(1/2)提到∑外面，H(n)=n/(2*(n3))∑H(i)*H(ni+2) （i=3,4,…,n1） 公式(2)規(guī)定H(2)=H(3)=1，這是合理的。[解法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)這就不需要再使用遞歸算法了。因此最后給出由公式(3)作為理論依據(jù)范例程序代碼。如果用前兩種解法中的遞歸關(guān)系，程序會變得復(fù)雜且容易寫錯。[代碼]//include define MAXN 100long f(int x){ if (x==3) return(1)。}main(){ int n。 cinn。amp。}本例編程時還有一個細(xì)節(jié)問題需要注意。數(shù)學(xué)上許多有重要意義的計數(shù)問題都可以歸結(jié)為對Catalan數(shù)的研究。下面討論一個遞歸關(guān)系略為復(fù)雜的例子?？焖倥判蚴浅绦蛟O(shè)計中經(jīng)常涉及的一種排序算法。[算法描述]快速排序的一種基本思想是：要將n個數(shù)按由小到大排列，在待排序的n個數(shù)中選取任一個數(shù)（在本例中取第一個），稱為基準(zhǔn)數(shù)，在每一次快速排序過程中設(shè)置兩個指示器i和j，對基準(zhǔn)數(shù)左邊和右邊的數(shù)同時從最左（i）和最右（j）開始進(jìn)行掃描（i逐1遞增，j逐1遞減），直到找到從左邊開始的某個i大于或等于基準(zhǔn)數(shù)，從右邊開始的某個j小于或等于基準(zhǔn)數(shù)。如此反復(fù)，在交換過有限個逆序?qū)?，i和j將越來越靠近，最后“相遇”，即i和j指向同一個數(shù)，暫且稱之為相遇數(shù)（極端情況下，如果一開始就不存在逆序?qū)?，i和j將直接“相遇”）。繼續(xù)掃描，非極端情況下，由于數(shù)列中已經(jīng)沒有逆序?qū)?，i遞增1（如果相遇數(shù)小于基準(zhǔn)數(shù)）或者j遞減1（如果相遇數(shù)大于基準(zhǔn)數(shù)）后即算完成了一趟快速排序，這時第1到第j個數(shù)中的每個都保證小于或等于基準(zhǔn)數(shù)，第i到第n個數(shù)中的每個保證大于或等于基準(zhǔn)數(shù)。如果在極端情況下，程序認(rèn)為基準(zhǔn)數(shù)和自身構(gòu)成逆序?qū)?，則將基準(zhǔn)數(shù)與自身交換（這其實沒有作用）之后i遞增1，j遞減1（注意斜體字給出的對逆序?qū)Φ奶幚矸椒ǎ?，同樣對?到第j個數(shù)和第i到第n個數(shù)分別再進(jìn)行一趟快速排序。由于被排序的數(shù)列將不斷被劃分為兩個至少含一個數(shù)的子列（因為在每趟排序最后進(jìn)行遞歸調(diào)用函數(shù)時ij），最后子列的長度將變?yōu)?。在程序?qū)崿F(xiàn)是，本著“能排則排”的原則，只要第一個數(shù)小于j（或者第i個數(shù)小于最后一個數(shù)），即進(jìn)行遞歸。 RecType temp。 { while( jiamp。R[j].key) j。 i++。amp。 if(ij) { R[j]=R[i]。 } } R[i]=temp。 QuickSort(R,i+1,t)。[問題描述]一個99方陣，由9個“九宮格”組成，每個九宮格又由33共9個小格子組成。（1）編程
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號-1