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