【正文】 由數(shù)組a[ ]、b[ ]和c[ ]對(duì)應(yīng)位置的值都為1來確定?！　?char awn。　　 for (j=0。j=2*n。 good=1。j=n。awn)?！　?}　　 col[m]++?！　?a[col[m]]=b[m+col[m]]=c[n+mcol[m]]=1。b[m+col[m]]amp?！　　　 試探法找解算法也常常被編寫成遞歸函數(shù)，下面兩程序中的函數(shù)queen_all()和函數(shù)queen_one()能分別用來解皇后問題的全部解和一個(gè)解。　　 printf(“Enter n: “)。j=n。j++) cb[j]=c[j]=1?！　?for (i=1。b[k+i]amp?！　?if (k==n)　　 { printf(“列\(zhòng)t行”)?！　?printf(“Enter a character (Q/q for exit)!\n”)?！　?}　　 queen_all(k+1,n)。設(shè)函數(shù)queen_one()返回1表示找到解，返回0表示當(dāng)前候選解不能成為解?！　?int queen_one(int k,int n)　　 { int i,found。i　　 { i++。amp。　　 else　　 found=queen_one(k+1,n)。貪婪法一般可以快速得到滿意的解，因?yàn)樗∪チ藶檎易顑?yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間。這種方法在這里總是最優(yōu)，是因?yàn)殂y行對(duì)其發(fā)行的硬幣種類和硬幣面值的巧妙安排?！　　締栴}】 裝箱問題　　問題描述：裝箱問題可簡述如下：設(shè)有編號(hào)為0、…、n1的n種物品，體積分別為v0、v…、vn1。裝箱問題要求使裝盡這n種物品的箱子數(shù)要少。為此，對(duì)裝箱問題采用非常簡單的近似算法，即貪婪法。裝箱算法簡單描述如下：　　{ 輸入箱子的容積；　　 輸入物品種數(shù)n；　　 按體積從大到小順序，輸入各物品的體積；　　 預(yù)置已用箱子鏈為空；　　 預(yù)置已用箱子計(jì)數(shù)器box_count為0；　　 for (i=0。而最優(yōu)解為兩只箱子，分別裝物品5和6?！　　境绦颉俊　?include 　　 include 　　typedef struct ele　　{ int vno?！　?ELE *head?！　?HNODE *box_h, *box_t, *j。box_volume)?！　?A=(int *)malloc(sizeof(int)*n)?！　?Box_count=0?！　?for (j=box_h?！　?jremainder=box_volumea?！　?jnext=NULL。q!=NULLamp?！　?if (q==NULL)　　 { plink=jhead?！　?}　　 }　　 printf(“共使用了%d只箱子”，box_count)。j=jnext,i++)　　 { printf(“第%2d只箱子，還剩余容積%4d，所裝物品有；\n”,I,jremainder)?！　?printf(“\n”)。另對(duì)馬的8種可能走法（稱為著法）設(shè)定一個(gè)順序，如當(dāng)前位置在棋盤的（i，j）方格，下一個(gè)可能的位置依次為（i+2，j+1）、（i+1，j+2）、（i1，j+2）、（i2，j+1）、（i2，j1）、（i1，j2）、（i+1，j2）、（i+2，j1），實(shí)際可以走的位置盡限于還未走過的和不越出邊界的那些位置。　　 由于程序采用的是一種貪婪法，整個(gè)找解過程是一直向前，沒有回溯，所以能非常快地找到解。以下程序考慮到這種情況，引入變量start，用于控制8種可能著法的選擇順序?！　nt delta_j[ ]={1,2,2,1,1,2,2,1}。k8。amp。amp?！　?}　　 return count?！　?for (min=9,k=0。　　 }　　 }　　 return kk。sx++)　　 for (sy=0。i8?！　?board[sx][sy]=1。step64。　　 board[j]=step。i8?！　?printf(“\n\n”)。例如，對(duì)于n個(gè)元素的排序問題，當(dāng)n=1時(shí)，不需任何計(jì)算；n=2時(shí)，只要作一次比較即可排好序；n=3時(shí)只要作3次比較即可，…?！　∪绻瓎栴}可分割成k個(gè)子問題　　分治法的適用條件　　分治法所能解決的問題一般具有以下幾個(gè)特征：　?。?）該問題的規(guī)模縮小到一定的程度就可以容易地解決；　　（2）該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；　?。?）利用該問題分解出的子問題的解可以合并為該問題的解；　?。?）該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子子問題?！　∷囊话愕乃惴ㄔO(shè)計(jì)模式如下：　　Divide_and_Conquer（P）　　if |P|≤n0 　　then return（ADHOC（P））　　將P分解為較小的子問題PP…、Pk　　for i←1 to k 　　do 　　yi ← DivideandConquer（Pi） △ 遞歸解決Pi　　T ← MERGE（y1，y2，…，yk） △ 合并子問題　　Return（T）　　其中 |P| 表示問題P的規(guī)模；n0為一閾值，表示當(dāng)問題P的規(guī)模不超過n0時(shí)，問題已容易直接解出，不必再繼續(xù)分解?！　「鶕?jù)分治法的分割原則，原問題應(yīng)該分為多少個(gè)子問題才較適宜？各個(gè)子問題的規(guī)模應(yīng)該怎樣才為適當(dāng)？這些問題很難予以肯定的回答。這種使子問題規(guī)模大致相等的做法是出自一種平衡子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好?！　　締栴}】 大整數(shù)乘法　　問題描述：　　通常，在分析一個(gè)算法的計(jì)算復(fù)雜性時(shí)，都將加法和乘法運(yùn)算當(dāng)作是基本運(yùn)算來處理，即將執(zhí)行一次加法或乘法運(yùn)算所需的計(jì)算時(shí)間當(dāng)作一個(gè)僅取決于計(jì)算機(jī)硬件處理速度的常數(shù)。若要精確地表示大整數(shù)并在計(jì)算結(jié)果中要求精確地得到所有位數(shù)上的數(shù)字，就必須用軟件的方法來實(shí)現(xiàn)大整數(shù)的算術(shù)運(yùn)算。如果將每2個(gè)1位數(shù)的乘法或加法看作一步運(yùn)算，那么這種方法要作O(n2)步運(yùn)算才能求出乘積XY。這樣，X和Y的乘積為：　　XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD （1）　　如果按式（1）計(jì)算XY，則我們必須進(jìn)行4次n/2位整數(shù)的乘法(AC，AD，BC和BD)，以及3次不超過n位的整數(shù)加法（分別對(duì)應(yīng)于式（1）中的加號(hào)），此外還要做2次移位（分別對(duì)應(yīng)于式（1）中乘2n和乘2n/2）。要想改進(jìn)算法的計(jì)算復(fù)雜性，必須減少乘法次數(shù)。 {X和Y為2個(gè)小于2n的整數(shù)，返回結(jié)果為X和Y的乘積XY}　　begin　　S=SIGN(X)*SIGN(Y)?！　=X的右邊n/2位?！　2=MULT(AB,DC,n/2)。 　　end。在涉及這些幾何對(duì)象的問題中，常需要了解其鄰域中其他幾何對(duì)象的信息?！　∽罱咏c(diǎn)對(duì)問題的提法是：給定平面上n個(gè)點(diǎn)，找其中的一對(duì)點(diǎn)，使得在n個(gè)點(diǎn)的所有點(diǎn)對(duì)中，該點(diǎn)對(duì)的距離最小。我們只要將每一點(diǎn)與其他n1個(gè)點(diǎn)的距離算出，找出達(dá)到最小距離的兩個(gè)點(diǎn)即可。在這里，一個(gè)關(guān)鍵的問題是如何實(shí)現(xiàn)分治法中的合并步驟，即由S1和S2的最接近點(diǎn)對(duì)，如何求得原集合S中的最接近點(diǎn)對(duì)，因?yàn)镾1和S2的最接近點(diǎn)對(duì)未必就是S的最接近點(diǎn)對(duì)。整個(gè)算法所需計(jì)算時(shí)間T(n)應(yīng)滿足：　　T(n)=2T(n/2)+O(n2)　　它的解為T(n)=O(n2)，即與合并步驟的耗時(shí)同階，顯示不出比用窮舉的方法好。此時(shí)S中的n個(gè)點(diǎn)退化為x軸上的n個(gè)實(shí)數(shù)xx…、xn。這啟發(fā)我們把注意力放在合并步驟上。但是，如果這2個(gè)點(diǎn)分別在S1和S2中，則對(duì)于S1中任一點(diǎn)p，S2中最多只有n/2個(gè)點(diǎn)與它構(gòu)成最接近點(diǎn)對(duì)的候選者，仍需做n2/4次計(jì)算和比較才能確定S的最接近點(diǎn)對(duì)。我們能否找到問題的一個(gè)O (nlogn)算法。為了簡單起見，這里只限于找其中的一對(duì)。這類問題是計(jì)算幾何學(xué)中研究的基本問題之一?！　∩鲜龆M(jìn)制大整數(shù)乘法同樣可應(yīng)用于十進(jìn)制大整數(shù)的乘法以提高乘法的效率減少乘法次數(shù)。 　　S=S*(m1*2n+(m1+m2+m3)*2n/2+m3)?！　=Y的右邊n/2位?！　=ABS(Y)。由此可得：　　 （4）　　用解遞歸方程的套用公式法馬上可得其解為T(n)=O(nlog3)=O()。設(shè)T（n）是2個(gè)n位整數(shù)相乘所需的運(yùn)算總數(shù)，則由式（1），我們有：　　 （2）由此可得T（n）=O（n2）?！　?　　圖63 大整數(shù)X和Y的分段　　我們將n位的二進(jìn)制整數(shù)X和Y各分為2段，每段的長為n/2位（為簡單起見，假設(shè)n是2的冪），如圖63所示?！　≡O(shè)X和Y都是n位的二進(jìn)制整數(shù)，現(xiàn)在要計(jì)算它們的乘積XY。然而，在某些情況下，我們要處理很大的整數(shù)，它無法在計(jì)算機(jī)硬件能直接表示的范圍內(nèi)進(jìn)行處理。有些問題的合并方法比較明顯，有些問題合并方法比較復(fù)雜，或者是有多種合并方案；或者是合并方案不明顯。換句話說，將一個(gè)問題分成大小相等的k個(gè)子問題的處理方法是行之有效的。因此，當(dāng)P的規(guī)模不超過n0時(shí)，直接用算法ADHOC（P）求解。第四條特征涉及到分治法的效率，如果各子問題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時(shí)雖然可用分治法，但一般用動(dòng)態(tài)規(guī)劃法較好。要想直接解決一個(gè)規(guī)模較大的問題，有時(shí)是相當(dāng)困難的?！　?}　　}　　七、分治法　　分治法的基本思想　　任何一個(gè)可以用計(jì)算機(jī)求解的問題所需的計(jì)算時(shí)間都與其規(guī)模N有關(guān)。j8?！　?start++?！　?I+=delta_i[no]。 j=sy。j8。sy++)　　 { start=0?！　?for (sx=0。　　 if (temp　　 { min=temp。　　 m=exitn(i,j,s,a)。amp。amp?！　?j1=i+delta_j[(s+k)%8]?！　nt exitn(int i,int j,int s,int a[ ])　　{ int i1,j1,k,count。細(xì)節(jié)以下程序。對(duì)于找不到解的情況，程序只要改變8種可能出口的選擇順序，就能找到解。　　 4 3 　　5 2　　 馬 　　6 1　　 7 0 　　　　 對(duì)于本題，一般可以采用回溯法，這里采用Warnsdoff策略求解，這也是一種貪婪法，其選擇下一出口的貪婪標(biāo)準(zhǔn)是在那些允許走的位置中，選擇出口最少的那個(gè)位置。　　 馬在某個(gè)方格，可以在一步內(nèi)到達(dá)的不同位置最多有8個(gè)，如圖所示。p!=NULL。　　 for (j=box_h,i=1?！　?}　　 else　　 { plink=NULL。qlink!=NULL?！　?}　　 else jremainder=a。　　 if (box_h==NULL) box_h=box_t=j。j=jnext)　　 if (jremainder=a) break。i　　 { p=(ELE *)malloc(sizeof(ELE))?！　?For (i=0?！　?Scanf(“%d”,amp。　　 Printf(“輸入箱子容積\n”)?！　 HNODE?！　 ELE。另將全部箱子的信息也構(gòu)成鏈表。下面的例子說明該算法不一定能找到最優(yōu)解，設(shè)有6種物品，它們的體積分別為：60、4320和20單位體積，箱子的容積為100個(gè)單位體積。不失一般性，設(shè)n件物品的體積是按從大到小排好序的，即有v0≥v1≥…≥vn1。但所有可能劃分的總數(shù)太大。約定這n種物品的體積均不超過V，即對(duì)于0≤i＜n，有0＜vi≤V。按貪婪算法，應(yīng)找1個(gè)11單位面值的硬幣和4個(gè)1單位面值的硬幣，共找回5個(gè)硬幣?！　?例如平時(shí)購物找錢時(shí)，為使找回的零錢的硬幣數(shù)最少，不考慮找零錢的所有各種發(fā)表方案，而是從最大面值的幣種開始，按遞減的順序考慮各幣種，先盡量用大面值的幣種，當(dāng)不足大面值幣種的金額時(shí)才去考慮下一種較小面值的幣種。　　 }　　 }　　 return found。　　 a=b[k+i]=c[n+ki]=0。amp?！　?While (!foundamp。　　【程序】　　 define MAXN 20　　 int n?！　?}　　}　　 采用遞歸方法找一個(gè)解與找全部解稍有不同，在找一個(gè)解的算法中，遞歸算法要對(duì)當(dāng)前候選解最終是否能成為解要有回答。awn)。j=n。c[n+ki])　　 { col[k]=i。i++)　　 if (aamp?！　　　　　void queen_all(int k,int n)　　{ int i,j。　　 for (j=0。n)。　　int col[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1]。c[n+mcol[m]]?！　?}　　 good=a[col[m]]amp?！　?col[++m]=1?！　?while (col[m]==n)　　 { m?！　?printf(“Enter a character (Q/q for exit)!\n”)?！　?do {　　 if (good)　　 if (m==n)　　 { printf(“列\(zhòng)t行”)?！　?m=1。j++) a[j]=1。 scanf(“%d”,amp?！　nt col[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1]。為使程序在檢查皇后配置的合理性方面簡易方便，引入以下三個(gè)工作數(shù)組：　?。?） 數(shù)組a[ ]，a[k]表示第k行上還沒有皇后；　?。?） 數(shù)組b[ ]，b[k]表示第k列右高左低斜線上沒有皇后；　?。?） 數(shù)組 c[ ]，c[k]表示第k列左高右低斜線上沒有皇后；　　棋盤中同一右高左低斜線上的方格，他們的行號(hào)與列號(hào)之和相同；同一左高右