【正文】 從解遞歸方程的套用公式法，我們看到問題出在合并步驟耗時太多。然而，這樣做效率太低，需要O(n2)的計算時間。例如，在空中交通控制問題中，若將飛機作為空間中移動的一個點來看待，則具有最大碰撞危險的2架飛機，就是這個空間中最接近的一對點?！　3=MULT(B,D,n/2)。 {S為X和Y的符號乘積}　　X=ABS(X)。所有這些加法和移位共用O（n）步運算。　　請設(shè)計一個有效的算法，可以進(jìn)行兩個n位大整數(shù)的乘法運算。分治法的合并步驟是算法的關(guān)鍵所在。ADHOC（P）是該分治法中的基本子算法，用于直接解小規(guī)模的問題P。而當(dāng)n較大時，問題就不那么容易處理了。i++)　　 { for (j=0。step++)　　 { if ((no=next(i,j,start))==1) break。i++)　　 for (j=0?！　　　　　void main()　　{ int sx,sy,i,j,step,no,start?！　　　　　int next(int i,int j,int s)　　{ int m,k,mm,min,a[8],b[8],temp。i18amp。　　int board[8][8]。但是，對于某些開始位置，實際上有解，而該算法不能找到解?！　?}　　}　　【問題】 馬的遍歷　　問題描述：在88方格的棋盤上，從任意指定的方格出發(fā)，為馬尋找一條走遍棋盤每一格并且只經(jīng)過一次的一條路徑。　　 printf(“各箱子裝物品情況如下：”)。amp?！　?jhead=NULL。　　 For (i=0?！　?Printf(“輸入物品種數(shù)\n”)。　　 Struct hnode *next。　　 若每只箱子所裝物品用鏈表來表示，鏈表首結(jié)點指針存于一個結(jié)構(gòu)中，結(jié)構(gòu)記錄尚剩余的空間量和該箱子所裝物品鏈表的首指針。該算法依次將物品放到它第一個能放進(jìn)去的箱子中，該算法雖不能保證找到最優(yōu)解，但還是能找到非常好的解。將這n種物品裝到容量都為V的若干箱子里。貪婪法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。c[n+ki])　　 { col[k]=i?！　?i=found=0?！　?a=b[k+i]=c[n+ki]?！　?for (j=1。i=n。j++) a[j]=1?！　　境绦颉俊　?include 　　 include 　　 define MAXN 20　　int n。　　 }　　 col[m]++。　　 if (awn==’Q’||awn==’q’) exit(0)。 col[0]=0。j=n。細(xì)節(jié)見以下程序：　　【程序】　　 include 　　 include 　　 define MAXN 20　　int n,m,good。更好的方法乃是盡可能直接表示那些常用的信息。開始時配置在第1行，以后改變時，順次選擇第2行、第3行、…、直到第n行?！　?這是來源于國際象棋的一個問題?！　?else pos=change(pos)?！　?b[j]=0?！　?b[a][pos]}=0。j++)　　 if (b[j]) return j　　 return 0。i*i=m?！　nt a[10]?！　?for (i=0。　　 ok=檢查前m個整數(shù)填放的合理性。　　 } while ((!ok||m!=n)amp。如果最近填入的整數(shù)不能滿足要求，就改變填入的整數(shù)?！　?}　　 } while (1)　　}　　　　main()　　{ b(5,3)?！　?a=1。繼續(xù)這一過程，得到候選組合1，2，3。開始棧空，則表示了樹的根結(jié)點。由于在回溯法求解問題時，一般要求出問題的所有解，因此在得到回答結(jié)點后，同時也要進(jìn)行回溯，以便得到問題的其他解，直至回溯到T的根且根的所有結(jié)點均已被搜索過為止?！　?因而，在E中尋找問題P的一個解等價于在T中搜索一個葉子結(jié)點，要求從T的根到該葉子結(jié)點的路徑上依次的n條邊相應(yīng)帶的n個權(quán)x1，x2，…，xn滿足約束集D的全部約束?；厮莘ㄕ轻槍@類問題，利用這類問題的上述性質(zhì)而提出來的比枚舉法效率更高的算法。擴大當(dāng)前候選解的規(guī)模，以繼續(xù)試探的過程稱為向前試探?！　?printf(“\n選中的物品為\n”)?！　?scanf(“%1f”,amp。k　　 cop[k]=twv[k].!=0?！　?}　　 break?！　?tw=?！　　　double find(struct ele *a,int n)　　{ int i,k,f?！　nt k,n。對物品i的考察有這樣幾種情況：當(dāng)該物品被包含在候選解中依舊滿足解的總重量的限制，該物品被包含在候選解中是應(yīng)該繼續(xù)考慮的；反之，該物品不應(yīng)該包括在當(dāng)前正在形成的候選解中。　　 maxv=。w,amp?！　?}　　}　　　　void main()　　{ int k?！　?/*考慮物品i包含在當(dāng)前方案中的可能性*/　　 if (tw+=limitW)　　 { cop=1。如能判定某個查找分支不會找到更好的解，算法不會在該分支繼續(xù)查找，而是立即終止該分支，并去考察下一個分支。　?。?） 考慮物品i不被選擇，這種可能性僅當(dāng)不包含物品i也有可能會找到價值更大的方案的情況。采用遞歸尋找物品的選擇方案?！　?else　　 { for (j=a[0]。第一個數(shù)可以是m、m……、k，函數(shù)將確定組合的第一個數(shù)字放入數(shù)組后，有兩種可能的選擇，因還未去頂組合的其余元素，繼續(xù)遞歸去確定；或因已確定了組合的全部元素，輸出這個組合。當(dāng)某個遞歸算法能較方便地轉(zhuǎn)換成遞推算法時，通常按遞推算法編寫程序。也就是說，為計算fib(n)，必須先計算fib(n1)和fib(n2)，而計算fib(n1)和fib(n2)，又必須先計算fib(n3)和fib(n4)?！　?fib(1)=1。k++)　　 { pnext(a,k)。　　 printf(“Enter the number n: “)?！　?a[0]=m?！　?for ( j=1?！　?計算階乘k！可采用對已求得的階乘(k1)！連續(xù)累加k1次后求得。設(shè)要求問題規(guī)模為N的解，當(dāng)N=1時，解或為已知，或能非常方便地得到解?！　?temp_v=0。而每個n元組其實對應(yīng)了一個長度為n的二進(jìn)制數(shù)，且這些二進(jìn)制數(shù)的取值范圍為0～2n1。 }　　 }　　}　　從上述問題解決的方法中，最重要的因素就是確定某種方法來確定所有的候選解?！　?t=*pt[j1]?！　?scanf(“%*c”)?！　?side_total=t。A}。A,amp?！　nt *pt[]={amp。要尋找比長整數(shù)124653更大的排列，可從該排列的最后一個數(shù)字順序向前逐位考察，當(dāng)發(fā)現(xiàn)排列中的某個數(shù)字比它前一個數(shù)字大時，如本例中的6比它的前一位數(shù)字4大，這說明還有對應(yīng)更大整數(shù)的排列?！　　　 }　　 }　　 }　　 }　　 }　　按窮舉法編寫的程序通常不能適應(yīng)變化的情況。e++) {　　 if (e==a)||(e==b)||(e==c)||(e==d) continue?！　?for (c=1。當(dāng)這些變量取盡所有的組合后，程序就可得到全部可能的解。如果方程無解，算法求出的近似根序列就不會收斂，迭代過程會變成死循環(huán)，因此在使用迭代算法前應(yīng)先考察方程是否有解，并在程序中對迭代的次數(shù)給予限制； （2）printf(“變量x[%d]的近似根是 %f”，I，x)； } while ( fabs(x0x1)Epsilon)； do { 將x0的值保存于變量x1，然后計算g(x1)，并將結(jié)果存于變量x0； （3）另外，為了更簡潔的形式設(shè)計和藐視算法，在算法設(shè)計時又常常采用遞歸技術(shù)，用遞歸描述算法。計算機按算法指令所描述的順序執(zhí)行算法的指令能在有限的步驟內(nèi)終止，或終止于給出問題的解，或終止于指出問題對此輸入數(shù)據(jù)無解。常用算法設(shè)計方法(C)要使計算機能完成人們預(yù)定的工作，首先必須為如何完成預(yù)定的工作設(shè)計一個算法，然后再根據(jù)算法編寫程序。 一、迭代法 y=x。 if (fabs(yx)delta)} while (deltaEpsilon)； 細(xì)節(jié)見下面的程序。c=6?！　=21(a+b+c+d+e)。如問題改成有9個變量排成三角形，每條邊有4個變量的情況，程序的循環(huán)重數(shù)就要相應(yīng)改變。但為了順序從小到大列舉出所有的排列，不能立即調(diào)整得太大，如本例中將數(shù)字6與數(shù)字4交換得到的排列126453就不是排列124653的下一個排列。A,amp。B,amp。　　int side_total[SIDE_N]。　　 }　　 for (equal=1,i=0?！　?}　　 for (j=VARIABLES1。* pt[j1] =* pt。下面再用一個示例來加以說明。因此，如果把0～2n1分別轉(zhuǎn)化為相應(yīng)的二進(jìn)制數(shù)，則可以得到我們所需要的2n個n元組。　　 for (j=0。能采用遞推法構(gòu)造算法的問題有重要的遞推性質(zhì)，即當(dāng)?shù)玫絾栴}規(guī)模為i1的解后，由問題的遞推性質(zhì)，能從已求得的規(guī)模為1，2，…，i1的一系列解，構(gòu)造出問題規(guī)模為I的解。例如，已知4！=24，計算5！，可對原來的24累加4次24后得到120。j=k?！　　　　　void write(int *a,int k)　　{ int i?！　?scanf(“%d”,amp?！　?write(a,k)?！　?fib(n)=fib(n1)+fib(n2) （當(dāng)n1時）。依次類推，直至計算fib(1)和fib(0)，分別能立即得到結(jié)果1和0。例如上例計算斐波那契數(shù)列的第n項的函數(shù)fib(n)應(yīng)采用遞推算法，即從斐波那契數(shù)列的前兩項出發(fā)，逐次由前兩項計算出下一項，直至計算出要求的第n項。細(xì)節(jié)見以下程序中的函數(shù)b。j0。設(shè)前面已有了多種選擇的方案，并保留了其中總價值最大的方案于數(shù)組option[ ]，該方案的總價值存于變量maxv。　　按以上思想寫出遞歸算法如下：　　try(物品i，當(dāng)前選擇已達(dá)到的重量和，本方案可能達(dá)到的總價值tv)　　{ /*考慮物品i包含在當(dāng)前方案中的可能性*/　　 if(包含物品i是可以接受的)　　 { 將物品i包含在當(dāng)前方案中；　　 if (i　　 try(i+1,tw+物品i的重量,tv)?！　　　“瓷鲜鏊惴ň帉懞瘮?shù)和程序如下：　　【程序】　　 include 　　 define N 100　　double limitW,totV,maxV?！　?if (i　　 else　　 { for (k=0?！　?double w,v。v)?！　?for (k=0。同樣地，僅當(dāng)物品不被包括在候選解中，還是有可能找到比目前臨時最佳解更好的候選解時，才去考慮該物品不被包括在候選解中；反之，該物品不包括在當(dāng)前候選解中的方案也不應(yīng)繼續(xù)考慮。　　struct { int ?！　?double maxv,tw,tv,totv?！　?tv=?！　?case 0: i?！　?}　　 break。limitW)?！　or (k=0?！　』厮莘ǖ囊话忝枋觥　】捎没厮莘ㄇ蠼獾膯栴}P，通常要能表達(dá)為：對于已知的由n元組（x1，x2，…，xn）組成的一個狀態(tài)空間E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，給定關(guān)于n元組中的一個分量的一個約束集D，要求E中滿足D的全部約束條件的所有n元組?！　』厮莘ㄊ紫葘栴}P的n元組的狀態(tài)空間E表示成一棵高為n的帶權(quán)有序樹T，把在E中求問題P的所有解轉(zhuǎn)化為在T中搜索問題P的所有解。在T中搜索所要求的葉子結(jié)點，很自然的一種方式是從根出發(fā)，按深度優(yōu)先的策略逐步深入，即依次搜索滿足約束條件的前綴1元組（x1i）、前綴2元組（x1，x2）、…，前綴I元組（x1，x2，…，xi），…，直到i=n為止?！　?例如在組合問題中，從T的根出發(fā)深度優(yōu)先遍歷該樹。如果元素1進(jìn)棧，則表示建立并遍歷（1）結(jié)點；這時如果元素2進(jìn)棧，則表示建立并遍歷（1，2）結(jié)點；元素3再進(jìn)棧，則表示建立并遍歷（1，2，3）結(jié)點。該候選解滿足包括問題規(guī)模在內(nèi)的全部條件，因而是一個解?！　?do {　　 if (ai=mr+1　　 { if (i==r1)　　 { for (j=0?！　　　【問題】 填字游戲　　問題描述：在33個方格的方陣中要填入數(shù)字1到N（N≥10）內(nèi)的某9個數(shù)字，每個方格填一個整數(shù)，似的所有相鄰兩個方格內(nèi)的兩個整數(shù)之和為質(zhì)數(shù)。如對當(dāng)前方格試盡所有可能的整數(shù)，都不能滿足要求，就得回退到前一方格，并調(diào)整前一方格填入的整數(shù)。amp?！　?} while (m!=0)。i3?！　nt isprime(int m)　　{ int i。)　　 { if (m%i==0) return 0?！　　　　　int check(int pos)　　{ int i,j?！　?return pos?！　?return pos?！　?ok=check(pos)?；屎罂梢匝刂v橫和兩條斜線4個方向相互捕捉。當(dāng)?shù)趎行配置也找不到一個合理的配置時，就要回溯，去改變前一列的配置。對于本題來說，“常用信息”并不是皇后的具體位置，而是“一個皇后是否已經(jīng)在某行和某條斜線合理地安置好了”?！　nt col[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1]。j++) a[j]=1?！　?do {　　 if (good)　　 if (m==n)　　 { printf(“列\(zhòng)t行”)?！　?while (col[m]==n)　　 {