iiraaa函數(shù)的遞歸調(diào)用與分治策略(編輯修改稿)
2025-08-20 11:45 本頁面
【文章內(nèi)容簡介】 的斜體部分，按照公式(4)計算時一定要先進行乘法再進行除法運算，因為(4*x10)并不總能整除(x1)，如果先進行除法則除出的小數(shù)部分將自動被舍去，從而導(dǎo)致得到不正確的解。數(shù)學(xué)上許多有重要意義的計數(shù)問題都可以歸結(jié)為對Catalan數(shù)的研究。可以看到，本例中的遞歸關(guān)系經(jīng)簡化還是相當簡單的。下面討論一個遞歸關(guān)系略為復(fù)雜的例子。[例5]快速排序問題。快速排序是程序設(shè)計中經(jīng)常涉及的一種排序算法。它的最好時間復(fù)雜度為O(nlog2n)，最差為O(n2)，是一種不穩(wěn)定的排序方法（大小相同的數(shù)在排序后可能交換位置）。[算法描述]快速排序的一種基本思想是：要將n個數(shù)按由小到大排列，在待排序的n個數(shù)中選取任一個數(shù)（在本例中取第一個），稱為基準數(shù)，在每一次快速排序過程中設(shè)置兩個指示器i和j，對基準數(shù)左邊和右邊的數(shù)同時從最左（i）和最右（j）開始進行掃描（i逐1遞增，j逐1遞減），直到找到從左邊開始的某個i大于或等于基準數(shù)，從右邊開始的某個j小于或等于基準數(shù)。一旦發(fā)現(xiàn)這樣的i和j（暫且稱之為一個“逆序?qū)Α保?，則把第i個數(shù)和第j個數(shù)交換位置，這樣它們就不再是逆序?qū)α?，緊接著再將i遞增1，j遞減1。如此反復(fù)，在交換過有限個逆序?qū)螅琲和j將越來越靠近，最后“相遇”，即i和j指向同一個數(shù)，暫且稱之為相遇數(shù)（極端情況下，如果一開始就不存在逆序?qū)?，i和j將直接“相遇”）。相遇后就保證數(shù)列中沒有逆序?qū)α耍ǔ嗽谏鲜龅臉O端情況下基準數(shù)和自身也算構(gòu)成一個逆序?qū)Γ⒁獯煮w字給出的逆序?qū)Φ亩x）。繼續(xù)掃描，非極端情況下，由于數(shù)列中已經(jīng)沒有逆序?qū)?，i遞增1（如果相遇數(shù)小于基準數(shù)）或者j遞減1（如果相遇數(shù)大于基準數(shù)）后即算完成了一趟快速排序，這時第1到第j個數(shù)中的每個都保證小于或等于基準數(shù)，第i到第n個數(shù)中的每個保證大于或等于基準數(shù)。此時，遞歸調(diào)用函數(shù)，對第1到第j個數(shù)和第i到第n個數(shù)分別再進行一趟快速排序。如果在極端情況下，程序認為基準數(shù)和自身構(gòu)成逆序?qū)?，則將基準數(shù)與自身交換（這其實沒有作用）之后i遞增1，j遞減1（注意斜體字給出的對逆序?qū)Φ奶幚矸椒ǎ?，同樣對?到第j個數(shù)和第i到第n個數(shù)分別再進行一趟快速排序。最后的問題就是確定遞歸邊界。由于被排序的數(shù)列將不斷被劃分為兩個至少含一個數(shù)的子列（因為在每趟排序最后進行遞歸調(diào)用函數(shù)時ij），最后子列的長度將變?yōu)?。這就是遞歸的邊界。在程序?qū)崿F(xiàn)是，本著“能排則排”的原則，只要第一個數(shù)小于j（或者第i個數(shù)小于最后一個數(shù)），即進行遞歸。[主程序（遞歸函數(shù)體）]void QuickSort(RecType R[ ],int s,int t){ int i=s,j=t,k。 RecType temp。 if (st) { temp=R[s] // 用區(qū)間第1個記錄作為基準 while( i!=j) //從兩端向中間交替掃描，直至i=j。 { while( jiamp。amp。R[j].key) j。 if(ij) { R[i]=R[j]。 i++。 } while( ijamp。amp。R[i].key) i++。 if(ij) { R[j]=R[i]。 j。 } } R[i]=temp。 QuickSort(R,s,i1)。 QuickSort(R,i+1,t)。}} [例6]“九宮陣”智力游戲。[問題描述]一個99方陣，由9個“九宮格”組成，每個九宮格又由33共9個小格子組成。請在每個空白小格子里面填上1～9的數(shù)字，使每個數(shù)字在每個九宮格內(nèi)以及在整個九宮陣中的每行、每列上均出現(xiàn)一次。（1）編程將下面圖中的九宮陣補充完整。（2）討論是否可能給出“九宮陣”的全部解？[分析]本題可利用回溯法解決，其基本思想為深度優(yōu)先搜索（DFS），這也是一種以分治策略為基礎(chǔ)的算法?；厮莘ㄅc純粹的DFS不同的是，它在搜索過程中不斷殺死不合題意的結(jié)點。這一點保證了解法的效率。首先考慮如何得出全部解的情況。解空間樹容易構(gòu)造，只需按順序（從第一行第一個數(shù)字開始到第一行最后一個，然后第二行……，一直到最后一行最后一個數(shù)字）“嘗試”填入數(shù)字即可。為了解決這個問題，我們需要先編寫一個函數(shù)check，其原型為int
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號-1