函數(shù)的遞歸調(diào)用與分治策略(完整版)
【正文】 n==0) return(1)。}綜上，得出構(gòu)造一個遞歸方法基本步驟，即描述遞歸關(guān)系、確定遞歸邊界、寫出遞歸函數(shù)并譯為代碼，最后將程序完善。需要注意的是本例中對于N=3，A(N)的值與A(N1)和A(N2)都有關(guān)。在A號針上從下到上套著從大到小的n個圓形金片。[代碼]//include hanoi(int n,char t1,char t2,char t3){ if (n==1) cout1 t1 t3endl。 hanoi(n,39。下面討論著名的Catalan數(shù)問題，人們在對它的研究中充分應(yīng)用了分治策略。下面討論三種不同的解法，其中第三種解法沒有使用遞歸，它是由前兩種解法推導(dǎo)而出的。考慮到同一條對角線在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，這是合理的。[代碼]//include define MAXN 100long f(int x){ if (x==3) return(1)。}本例編程時還有一個細(xì)節(jié)問題需要注意。[算法描述]快速排序的一種基本思想是：要將n個數(shù)按由小到大排列，在待排序的n個數(shù)中選取任一個數(shù)（在本例中取第一個），稱為基準(zhǔn)數(shù)，在每一次快速排序過程中設(shè)置兩個指示器i和j，對基準(zhǔn)數(shù)左邊和右邊的數(shù)同時從最左（i）和最右（j）開始進行掃描（i逐1遞增，j逐1遞減），直到找到從左邊開始的某個i大于或等于基準(zhǔn)數(shù)，從右邊開始的某個j小于或等于基準(zhǔn)數(shù)。由于被排序的數(shù)列將不斷被劃分為兩個至少含一個數(shù)的子列（因為在每趟排序最后進行遞歸調(diào)用函數(shù)時ij），最后子列的長度將變?yōu)?。R[j].key) j。 } } R[i]=temp?；厮莘ㄅc純粹的DFS不同的是，它在搜索過程中不斷殺死不合題意的結(jié)點。函數(shù)check代碼如下：int check(int i,int j,int k){ int l,m,pi,pj。 //2. Check the column for (l=1。 else if (i=6) pi=4。m=2。下面考慮程序最重要的部分，即遞歸函數(shù)。 if i10 then begin for l:=1 to 9 do backtrack(i,j,l)。 //Fill in the okay solution //Generate next i,j if (j9) j++。 /*When fails and goes upperwards, the value must be cleared*/ }}函數(shù)output()用雙重循環(huán)完成輸出。int check(int i,int j,int k){ int l,m,pi,pj。 //2. Check the column for (l=1。 else if (i=6) pi=4。m=2。 coutOne solution is:endl。 if (check(i,j,k)==1) { a[i][j]=k。 } else output()。 a[2][6]=9。 a[5][3]=4。 a[8][2]=6。 for (i=1。i++){ init()。 a[8][5]=9。 a[5][9]=3。 a[3][4]=3。 /*When fails and goes upperwards, the value must be cleared*/ }}void init(){ a[1][2]=9。 else { i++。i=9。amp。 if (j=3) pj=1。l++) if ( (l!=i) amp。l=9。運行時發(fā)現(xiàn)九宮格的解相當(dāng)多，即使保存到文件中也不現(xiàn)實。 j=1。a[i,j]:=0。對下一格，同樣這樣考慮。amp。 if (j=3) pj=1。l++) if ( (l!=i) amp。l=9。首先考慮如何得出全部解的情況。 QuickSort(R,i+1,t)。
物理相關(guān)推薦
鄂ICP備17016276號-1