函數(shù)的遞歸調(diào)用與分治策略-免費(fèi)閱讀
【正文】 return 0。 a[9][7]=8。 a[6][6]=3。 a[3][9]=9。 a[1][9]=7。 //End of Generate next i,j if (i10) { for (l=1。j++) couta[i][j] 。 ( a[pi+l][pj+m]==k ) ) return(0)。 // Now we can check it for (l=0。amp。 (a[i][l]!=0) amp。最后給出填充有部分空缺的九宮格的完整源代碼。l++) backtrack(i,j,l)。這時(shí)需要保證(x,y)以后所填的數(shù)被重新置零，這個(gè)語(yǔ)句的作用即在每個(gè)結(jié)點(diǎn)被殺死時(shí)都將其置零。這種思想可用偽代碼表示如下：procedure backtrack(i,j,k:integer)。 ( a[pi+l][pj+m]==k ) ) return(0)。 // Now we can check it for (l=0。amp。 (a[i][l]!=0) amp。如果可以，返回1，否則返回0。請(qǐng)?jiān)诿總€(gè)空白小格子里面填上1～9的數(shù)字，使每個(gè)數(shù)字在每個(gè)九宮格內(nèi)以及在整個(gè)九宮陣中的每行、每列上均出現(xiàn)一次。R[i].key) i++。 if (st) { temp=R[s] // 用區(qū)間第1個(gè)記錄作為基準(zhǔn) while( i!=j) //從兩端向中間交替掃描，直至i=j。此時(shí)，遞歸調(diào)用函數(shù)，對(duì)第1到第j個(gè)數(shù)和第i到第n個(gè)數(shù)分別再進(jìn)行一趟快速排序。[例5]快速排序問(wèn)題。 if ( (n=MAXN) amp。代碼相當(dāng)簡(jiǎn)單，這都?xì)w功于剛才的推導(dǎo)。于是得到公式：H(n)=∑H(i)*H(ni+1) （i=2,3,…,n1） 公式(1)H(2)=1有了這個(gè)遞歸關(guān)系式，就可以用遞推法或遞歸法解出H(n)。例如，n=5時(shí)H(5)=5。C39。 coutPlease enter the number of Hanoi:。當(dāng)n=1時(shí)，只要將唯一的金片從A移到C即可。 coutendlfibonacci(n)。[例2]Fibonacci數(shù)列（兔子繁殖）問(wèn)題：已知無(wú)窮數(shù)列A，滿足：A(1)=A(2)=1，A(N)=A(N1)+A(N2)（N=3）。}main(){ int n。例如以下程序：include int f(int x){ return(f(x1))。設(shè){U1,U2,U3,…,Un…}是一個(gè)序列，如果從某一項(xiàng)k開(kāi)始，Un和它之前的若干項(xiàng)之間存在一種只與n有關(guān)的關(guān)系，這便稱(chēng)為遞歸關(guān)系。遞歸方法中所使用的“分而治之”的策略也稱(chēng)分治策略。遞歸方法的構(gòu)造構(gòu)造遞歸方法的關(guān)鍵在于建立遞歸關(guān)系。注意到，當(dāng)N=1時(shí)，N!=N*(N1)!（N=1時(shí)，0!=1），這就是一種遞歸關(guān)系。}main(){ coutf(10)。 cinn。從鍵盤(pán)輸入N，輸出A(N)。} [例3]Hanoi塔問(wèn)題。當(dāng)n1時(shí)，只要把較小的(n1)片按移動(dòng)規(guī)則從A移到B，再將剩下的最大的從A移到C（即中間“借助”B把金片從A移到C），再將B上的(n1)個(gè)金片按照規(guī)則從B移到C（中間“借助”A）。 cinn。)。[分析]Catalan數(shù)問(wèn)題有著明顯的遞歸子問(wèn)題特征。[解法2]從V1向除了V2和Vn外的n3個(gè)頂點(diǎn)可作n3條對(duì)角線。如果用前兩種解法中的遞歸關(guān)系，程序會(huì)變得復(fù)雜且容易寫(xiě)錯(cuò)。amp?？焖倥判蚴浅绦蛟O(shè)計(jì)中經(jīng)常涉及的一種排序算法。如果在極端情況下，程序認(rèn)為基準(zhǔn)數(shù)和自身構(gòu)成逆序?qū)?，則將基準(zhǔn)數(shù)與自身交換（這其實(shí)沒(méi)有作用）之后i遞增1，j遞減1（注意斜體字給出的對(duì)逆序?qū)Φ奶幚矸椒ǎ?，同樣?duì)第1到第j個(gè)數(shù)和第i到第n個(gè)數(shù)分別再進(jìn)行一趟快速排序。 { while( jiamp。 if(ij) { R[j]=R[i]。（1）編程將下面圖中的九宮陣補(bǔ)充完整。由于我們是按順序填入數(shù)字的，看起來(lái)一個(gè)數(shù)字后面的數(shù)字并不在判斷能否填的范圍內(nèi)。amp。 (a[l][j]==k) ) return(0)。l=2。 } return(1)。 if check(i,j,k)=true then begin a[i,j]=k。將偽代碼翻譯為C++代碼：backtrack(int i,int j,int k)
物理相關(guān)推薦
鄂ICP備17016276號(hào)-1