【正文】 　 }　　 if (carry) a[++m]=carry。j++)　　 { for ( carry=0,i=1。i=m。細節(jié)見以下程序。按上述約定，數(shù)組的每個元素存儲k的階乘k！的一位數(shù)字，并從低位到高位依次存于數(shù)組的第二個元素、第三個元素……。這樣，程序可從i=0或i=1出發(fā)，重復地，由已知至i1規(guī)模的解，通過遞推，獲得規(guī)模為i的解，直至得到規(guī)模為N的解。(temp_vmaxv))　　 { maxv=temp_v。j　　 { if (B[j]==1)　　 { temp_w=temp_w+w[j]?！　?把i轉(zhuǎn)化為二進制數(shù)，存儲于數(shù)組B中?！　　舅惴ā俊　axv=0。用枚舉法解決背包問題，需要枚舉所有的選取方案，而根據(jù)上述方法，我們只要枚舉所有的n元組，就可以得到問題的解。　　【問題】 背包問題　　問題描述：有不同價值、不同重量的物品n件，求從這n件物品中選取一部分物品的選擇方案，使選中物品的總重量不超過指定的限制重量，但選中物品的價值之和最大。 *pt[j] =* pt。 *pt=t。i=j。j0。i　　 printf(“%4d”,*pt)。equalamp。i　　 { for (t=j=0?！　ain{}　　{ int i,j,t,equal。E,amp。C,amp。F}。B,amp。按以上想法編寫的程序如下。為了得到排列124653的下一個排列，應從已經(jīng)考察過的那部分數(shù)字中選出比數(shù)字大，但又是它們中最小的那一個數(shù)字，比如數(shù)字5，與數(shù)字4交換。從一個排列找出對應數(shù)列的下一個排列可在當前排列的基礎上作部分調(diào)整來實現(xiàn)?！　?對一組數(shù)窮盡所有排列，還有更直接的方法?！　?printf(“%2d%4d%4d”,c,d,e)?！　f ((a+b+c==c+d+e))amp。　　for (e=1。c++) {　　 if (c==a)||(c==b) continue。b=6?！　　境绦?】　　 include 　　void main()　　{ int a,b,c,d,e,f。如圖就是一個解。方程雖然有解，但迭代公式選擇不當，或迭代的初始近似根選擇不合理，也會導致迭代失敗。具體使用迭代法求根時應注意以下兩種可能發(fā)生的情況： （1） printf(“\n”)； for (delta=,i=0。 for (i=0。 for (i=0。 do { for (i=0。(I=0，1，…，n1) 則求方程組根的迭代算法可描述如下： 【算法】迭代法求方程組的根 xi=gi(X)printf(“方程的近似根是%f\n”，x0)； } 迭代算法也常用于求方程組的根，令 /*按特定的方程計算新的近似根*/ x1=x0； x0=初始近似根； 當x0與x1的差的絕對值還小于指定的精度要求時，重復步驟（2）的計算。選一個方程的近似根，賦給變量x0； （2） 算法是問題求解過程的精確描述，一個算法由有限條可完全機械地執(zhí)行的、有確定結果的指令組成。計算機程序要對問題的每個對象和處理規(guī)則給出正確詳盡的描述，其中程序的數(shù)據(jù)結構和變量用來描述問題的對象，程序結構、函數(shù)和語句用來描述問題的算法。算法數(shù)據(jù)結構是程序的兩個重要方面。指令正確地描述了要完成的任務和它們被執(zhí)行的順序。 通常求解一個問題可能會有多種算法可供選擇，選擇的主要標準是算法的正確性和可靠性，簡單性和易理解性。 算法設計是一件非常困難的工作，經(jīng)常采用的算法設計技術主要有迭代法、窮舉搜索法、遞推法、貪婪法、回溯法、分治法、動態(tài)規(guī)劃法等等。迭代法是用于求方程或方程組近似根的一種常用的算法設計方法。 若方程有根，并且用上述方法計算出來的近似根序列收斂，則按上述方法求得的x0就認為是方程的根。 ix=初始近似根。 i i i for (i=0。 二、窮舉搜索法　　 窮舉搜索法是對可能是解的眾多候選解按某種順序進行逐一枚舉和檢驗，并從眾找出那些符合要求的候選解作為問題的解?！　〕绦蛞胱兞縜、b、c、d、e、f，并讓它們分別順序取1至6的證書，在它們互不相同的條件下，測試由它們排成的如圖所示的三角形三條邊上的變量之和是否相等，如相等即為一種滿足要求的排列，把它們輸出。　　 for (a=1。b++) {　　 if (b==a) continue?！　?for (d=1。e=6。amp。　　 scanf(“%*c”)。將一個排列看作一個長整數(shù)，則所有排列對應著一組整數(shù)。倘若當前排列為1，2，4，6，5，3，并令其對應的長整數(shù)為124653。該數(shù)字也是從后向前考察過程中第一個比4大的數(shù)字?！　　境绦?】　　 include 　　 define SIDE_N 3　　 define LENGTH 3　　 define VARIABLES 6　　int A,B,C,D,E,F。C,amp?！　nt *side[SIDE_N][LENGTH]={amp。C,amp。F,amp。　　 for (j=0。j　　 t+=*side[j]。amp?！　?printf(“\n”)。j)　　 if (*pt[j]*pt[j1]) break。i)　　 if (*pt*pt[i1]) break。　　 for (i=VARIABLES1。 *pt=t?！　≡On個物品的重量和價值分別存儲于數(shù)組w[ ]和v[ ]中，限制重量為tw?！　★@然，每個分量取值為0或1的n元組的個數(shù)共為2n個?！　or (i=0。　　 temp_w=0?！　?temp_v=temp_v+v[j]?！　?保存該B數(shù)組；　　 }　　 }　　}　　　　三、遞推法　　 遞推法是利用問題本身所具有的一種遞推關系求問題解的一種方法?！　　締栴}】 階乘計算　　問題描述：編寫程序，對給定的n（n≦100），計算并輸出k的階乘k?。╧=1，2，…，n）的全部有效數(shù)字。例如，5！=120，在數(shù)組中的存儲形式為：　　3 0 2 1 ……　　首元素3表示長整數(shù)是一個3位數(shù)，接著是低位到高位依次是0、1，表示成整數(shù)120?！　?include 　　 include 　　 define MAXN 1000　　void pnext(int a[ ],int k)　　{ int *b,m=a[0],i,j,r,carry。i++) b=a。i=m?！　?}　　 free(b)。　　 for (i=a[0]?！　　　　　void main()　　{ int a[MAXN],n,k?！　?a[0]=1。k=n?！　?}　　}　　四、遞歸　　 遞歸是設計和描述算法的一種有力的工具，由于它在復雜算法的描述中被經(jīng)常采用，為此在進一步介紹其他算法設計方法之前先討論它?！　?斐波那契數(shù)列為：0、……，即：　　 fib(0)=0?！　?if (n==1) return 1。例如上例中，求解fib(n)，把它推到求解fib(n1)和fib(n2)。例如在函數(shù)fib中，當n為1和0的情況?！　?由于遞歸引起一系列的函數(shù)調(diào)用，并且可能會有一系列的重復計算，遞歸算法的執(zhí)行效率相對較低。例如n=5，r=3的所有組合為： （1）3 （2）2 （3）1　　 （4）2 （5）1 （6）1　　 （7）2 （8）1 （9）1　　 （10）1　　 分析所列的10個組合，可以采用這樣的遞歸思想來考慮求組合函數(shù)的算法。設函數(shù)引入工作數(shù)組a[ ]存放求出的組合的數(shù)字，約定函數(shù)將確定的k個數(shù)字組合的第一個數(shù)字放在a[k]中，當一個組合求出后，才將a[ ]中的一個組合輸出?！　oid b(int m,int k)　　{ int i,j?！　?if (k1)　　 b(i1,k1)。　　 printf(“\n”)?！　≡On件物品的重量分別為w0、w…、wn1，物品的價值分別為v0、v…、vn1。假定當前方案已考慮了前i1件物品，現(xiàn)在要考慮第i件物品；當前方案已包含的物品的重量之和為tw；至此，若其余物品都選擇是可能的話，本方案能達到的總價值的期望值為tv。選中后，繼續(xù)遞歸去考慮其余物品的選擇。　　 恢復物品i不包含狀態(tài)；　　 }　　 /*考慮物品i不包含在當前方案中的可能性*/　　 if (不包含物品i僅是可男考慮的)　　 if (i　　 try(i+1,tw,tv物品i的價值)；　　 else　　 /*又一個完整方案，因它比前面的方案好，以它作為最佳方案*/　　以當前方案作為臨時最佳方案保存。由圖知，一旦找到一個解，算法就進一步找更好的佳?！　truct { double weight?！　oid find(int i,double tw,double tv)　　{ int k?！　?maxv=tv?！　?maxv=?！　?scanf((“%d”,amp。k　　 { scanf(“%1f%1f”,amp?！　?a[k].value=v。limitV)?！　?for (k=0。為了提高找解速度，程序不是簡單地逐一生成所有候選解，而是從每個物品對候選解的影響來形成值得進一步考慮的候選解，一個候選解是通過依次考察每個物品形成的。　　【程序】　　 include 　　 define N 100　　double limitW?！　?} a[N]?！　?double tv?！　?=tv?！　?for (totv=,k=0。　　 While (i=0)　　 { f=twv.。　　 if (tw+=limitW)　　 if (i　　 { next(i+1,tw+,tv)。k　　 cop[k]=twv[k].!=0?！　?default: twv.=0。　　 for (k=0。　　}　　　　void main()　　{ double maxv?！　?printf(“輸入限制重量\n”)。　　 for (k=0。　　 maxv=find(a,n)?！　?printf(“\n總價值為%.2f\n”,maxv)。在回溯法中，放棄當前候選解，尋找下一個候選解的過程稱為回溯。我們稱E中滿足D的全部約束條件的任一n元組為問題P的一個解。因此，對于約束集D具有完備性的問題P，一旦檢測斷定某個j元組（x1，x2，…，xj）違反D中僅涉及x1，x2，…，xj的一個約束，就可以肯定，以（x1，x2，…，xj）為前綴的任何n元組（x1，x2，…，xj，xj+1，…，xn）都不會是問題P的解，因而就不必去搜索它們、檢測它們。從根開始，讓T的第I層的每一個結點都有mi個。特別，E中的任意一個n元組的空前綴（），對應于T的根?！　　締栴}】 組合問題　　問題描述：找出從自然數(shù)……、n中任取r個數(shù)的所有組合。　　在搜索過程中，只要所激活的狀態(tài)結點又滿足終結條件，那么它就是回答結點，應該把它輸出或保存?！　』厮莘ǖ囊话懔鞒毯图夹g　　 在用回溯法求解有關問題的過程中，一般是一邊建樹，一邊遍歷該樹?！　±缭诮M合問題中，我們用一個一維數(shù)組Stack[ ]表示棧。這時只要棧頂元素（3）出棧，即表示從結點（1，2，3）回溯到結點（1，2）。因該候選解滿足除問題規(guī)模之外的全部條件，擴大其規(guī)模，并使其滿足上述條件（1），候選組合改為1，2。由于對5不能再作調(diào)整，就要從a[2]回溯到a[1]，這時，a[1]=2，可以調(diào)整為3，并向前試探，得到解1，3，4。　　 i=0?！　?printf(“\n”)?！　?a[i]++?！　】捎迷囂桨l(fā)找到問題的解，即從第一個方格開始，為當前方格尋找一個合理的整數(shù)填入，并在當前位置正確填入后，為下一方格尋找可填入的合理整數(shù)。在滿足要求的情況下，繼續(xù)用同樣的方法為下一方格填入整數(shù)?！　』厮莘ㄕ乙粋€解的算法：　　{ int m=0,ok=1?！　?ok=檢查前m個整數(shù)填放的合理性。　　 else 輸出無解報告；　　}　　如果程序要找全部解，則在將找到的解輸出后，應繼續(xù)調(diào)整最后位置上填放的整數(shù)，試圖去找下一個解?！　?}　　 else 調(diào)整。給解的候選者設定一個被檢驗的順序，按這個順序逐一形成候選者并檢驗?！　　境绦颉俊　?include 　　 define N 12　　void write(int a[ ])　　{ int i,j。j3?！　　　　　int b[N+1]?！　?if (m==1||m%2=0) return 0?！　?for (i=3。　　 }　　 return 1。j=N。　　 for (i=0?！　?　　　　int extend(int pos)　　{ a[++pos]=selectnum(1)?！　?while (pos=0amp?！　?a[pos]=j?！　?a[pos]=1?！　?}　　 else pos=extend(pos)?！　?for (i=1?！　【問題】 n皇后問題　　問題描述：求出在一個nn的棋盤上，放置n個不能互相捕捉的國際象棋“皇后”的所有布局。　　 　　1 2 3 4 5 6 7 8　　 　　 　　 　　 Q 　　 　　 　　 　　 　　從圖中可以得到以下啟示：一個合適的解應是在每列、每行上只有一個皇后，且一條斜線上也只有一個皇后。另外，在任一列上，可能有n種配置。　　 good=1。比較直觀的方法是采用一個二維數(shù)組，但仔細觀察就會發(fā)現(xiàn)，這種表示方法給調(diào)整候選解及檢查其合理性帶來困難。例如：col[3]=4，就表示在棋盤的第3列、第4行上有一個皇后。一個皇后在m列，col[m]行方格內(nèi)配置是合理的，