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