【正文】 低斜線上的方格，他們的行號與列號之差均相同。對于本題來說，“常用信息”并不是皇后的具體位置，而是“一個皇后是否已經(jīng)在某行和某條斜線合理地安置好了”?！　?}　　 else 擴展當前候選接至下一列；　　 else 改變之，形成下一個候選解；　　 good=檢查當前候選解的合理性；　　 } while (m!=0)。當?shù)趎行配置也找不到一個合理的配置時，就要回溯，去改變前一列的配置。在第1列至第m列為合理配置的基礎上，再配置第m+1列，直至第n列配置也是合理時，就找到了一個解。皇后可以沿著縱橫和兩條斜線4個方向相互捕捉。i++)　　 b=1?！　?ok=check(pos)?！　?do {　　 if (ok)　　 if (pos==8)　　 { write(a)?！　?return pos。(j=selectnum(a[pos]+1))==0)　　 b[a[pos]]=1?！　?return pos。i++)　　 if (!isprime(a[pos]+a[j])　　 return 0?！　　　　　int check(int pos)　　{ int i,j?！　nt selectnum(int start)　　{ int j。)　　 { if (m%i==0) return 0。primes0?！　nt isprime(int m)　　{ int i?！　?printf(“\n”)。i3。如擴展時，先在新位置填入整數(shù)1，調整時，找當前候選解中下一個還未被使用過的整數(shù)?！　?} while (m!=0)?！　?int n=8。amp?！　?do{　　 if (ok) 擴展。如對當前方格試盡所有可能的整數(shù)，都不能滿足要求，就得回退到前一方格，并調整前一方格填入的整數(shù)。當?shù)诰艂€方格也填入合理的整數(shù)后，就找到了一個解，將該解輸出，并調整第九個的填入的整數(shù)，尋找下一個解?！　　　【問題】 填字游戲　　問題描述：在33個方格的方陣中要填入數(shù)字1到N（N≥10）內的某9個數(shù)字，每個方格填一個整數(shù)，似的所有相鄰兩個方格內的兩個整數(shù)之和為質數(shù)?！　?continue?！　?do {　　 if (ai=mr+1　　 { if (i==r1)　　 { for (j=0。按上述思想寫成程序如下：　　【程序】　　 define MAXN 100　　int a[MAXN]。該候選解滿足包括問題規(guī)模在內的全部條件，因而是一個解?！　〔捎没厮莘ㄕ覇栴}的解，將找到的組合以從小到大順序存于a[0]，a[1]，…，a[r1]中，組合的元素滿足以下性質：　　（1） a[i+1]a，后一個數(shù)字比前一個大；　?。?） ai=nr+1。如果元素1進棧，則表示建立并遍歷（1）結點；這時如果元素2進棧，則表示建立并遍歷（1，2）結點；元素3再進棧，則表示建立并遍歷（1，2，3）結點。下面，我們給出回溯法的非遞歸算法的一般流程：　　　　在用回溯法求解問題，也即在遍歷狀態(tài)空間樹的過程中，如果采用非遞歸方法，則我們一般要用到棧的數(shù)據(jù)結構?！　?例如在組合問題中，從T的根出發(fā)深度優(yōu)先遍歷該樹。　　問題的狀態(tài)空間樹T：　　　回溯法的方法　　 對于具有完備約束集D的一般問題P及其相應的狀態(tài)空間樹T，利用T的層次結構和D的完備性，在T中搜索問題P的所有解的回溯法可以形象地描述為：　　 從T的根出發(fā)，按深度優(yōu)先的策略，系統(tǒng)地搜索以其為根的子樹中可能包含著回答結點的所有狀態(tài)結點，而跳過對肯定不含回答結點的所有子樹的搜索，以提高搜索效率。在T中搜索所要求的葉子結點，很自然的一種方式是從根出發(fā)，按深度優(yōu)先的策略逐步深入，即依次搜索滿足約束條件的前綴1元組（x1i）、前綴2元組（x1，x2）、…，前綴I元組（x1，x2，…，xi），…，直到i=n為止。照這種構造方式，E中的一個n元組（x1，x2，…，xn）對應于T中的一個葉子結點，T的根到這個葉子結點的路徑上依次的n條邊的權分別為x1，x2，…，xn，反之亦然?！　』厮莘ㄊ紫葘栴}P的n元組的狀態(tài)空間E表示成一棵高為n的帶權有序樹T，把在E中求問題P的所有解轉化為在T中搜索問題P的所有解。但顯然，其計算量是相當大的?！　』厮莘ǖ囊话忝枋觥　】捎没厮莘ㄇ蠼獾膯栴}P，通常要能表達為：對于已知的由n元組（x1，x2，…，xn）組成的一個狀態(tài)空間E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，給定關于n元組中的一個分量的一個約束集D，要求E中滿足D的全部約束條件的所有n元組。當發(fā)現(xiàn)當前候選解不可能是解時，就選擇下一個候選解；倘若當前候選解除了還不滿足問題規(guī)模要求外，滿足所有其他要求時，繼續(xù)擴大當前候選解的規(guī)模，并繼續(xù)試探?！　or (k=0。a[k].weight,amp。limitW)?！　?scanf((“%d”,amp?！　?}　　 break?！　?i++?！　?case 0: i。　　 }　　 else　　 { maxv=tv?！　?tv=?！　?next(0,totv)?！　?double maxv,tw,tv,totv?！　oid next(int i,double tw,double tv)　　{ twv.=1。　　struct { int ?！　truct ele { double weight。同樣地，僅當物品不被包括在候選解中，還是有可能找到比目前臨時最佳解更好的候選解時，才去考慮該物品不被包括在候選解中；反之，該物品不包括在當前候選解中的方案也不應繼續(xù)考慮?！　?printf(“\n總價值為%.2f\n”,maxv)。　　 for (k=0。　　 }　　 printf(“輸入限制重量\n”)。v)?！　?printf(“輸入各物品的重量和價值\n”)?！　?double w,v?！　　　 /*考慮物品i不包含在當前方案中的可能性*/　　 if (maxV)　　 if (i　　 else　　 { for (k=0?！　?if (i　　 else　　 { for (k=0?！　?}a[N]?！　　　“瓷鲜鏊惴ň帉懞瘮?shù)和程序如下：　　【程序】　　 include 　　 define N 100　　double limitW,totV,maxV。設有4件物品，它們的重量和價值見表：　　物品 0 1 2 3　　重量 5 3 2 1　　價值 4 4 3 1　　　　并設限制重量為7。　　按以上思想寫出遞歸算法如下：　　try(物品i，當前選擇已達到的重量和，本方案可能達到的總價值tv)　　{ /*考慮物品i包含在當前方案中的可能性*/　　 if(包含物品i是可以接受的)　　 { 將物品i包含在當前方案中；　　 if (i　　 try(i+1,tw+物品i的重量,tv)。因為當方案的總價值不比maxv大時，該方案不會被再考察，這同時保證函數(shù)后找到的方案一定會比前面的方案更好。設前面已有了多種選擇的方案，并保留了其中總價值最大的方案于數(shù)組option[ ]，該方案的總價值存于變量maxv?！　?b(5,3)。j0。i=k。細節(jié)見以下程序中的函數(shù)b。當組合的第一個數(shù)字選定時，其后的數(shù)字是從余下的m1個數(shù)中取k1數(shù)的組合。例如上例計算斐波那契數(shù)列的第n項的函數(shù)fib(n)應采用遞推算法，即從斐波那契數(shù)列的前兩項出發(fā)，逐次由前兩項計算出下一項，直至計算出要求的第n項?！　?在編寫遞歸函數(shù)時要注意，函數(shù)中的局部變量和參數(shù)知識局限于當前調用層，當遞推進入“簡單問題”層時，原來層次上的參數(shù)和局部變量便被隱蔽起來。依次類推，直至計算fib(1)和fib(0)，分別能立即得到結果1和0?！　　　 遞歸算法的執(zhí)行過程分遞推和回歸兩個階段。　　 fib(n)=fib(n1)+fib(n2) （當n1時）。特別地，當規(guī)模N=1時，能直接得解?！　?write(a,k)?！　?write(a,1)?！　?scanf(“%d”,amp。i)　　 printf(“%d”,a)?！　　　　　void write(int *a,int k)　　{ int i?！　?carry=r/10。j=k。　　 for ( i=1。例如，已知4！=24，計算5！，可對原來的24累加4次24后得到120。如有m位成整數(shù)N用數(shù)組a[ ]存儲：　　 N=a[m]10m1+a[m1]10m2+ … +a[2]101+a[1]100　　并用a[0]存儲長整數(shù)N的位數(shù)m，即a[0]=m。能采用遞推法構造算法的問題有重要的遞推性質，即當?shù)玫絾栴}規(guī)模為i1的解后，由問題的遞推性質，能從已求得的規(guī)模為1，2，…，i1的一系列解，構造出問題規(guī)模為I的解。amp?！　?for (j=0。i++)　　{ B[0..n1]=0。因此，如果把0～2n1分別轉化為相應的二進制數(shù)，則可以得到我們所需要的2n個n元組。顯然這個n元組等價于一個選擇方案。下面再用一個示例來加以說明。i,j++)　　 { t=*pt[j]。* pt[j1] =* pt?！　?for (i=VARIABLES1?！　?}　　 for (j=VARIABLES1?！　?if (equal)　　 { for (i=1。　　 }　　 for (equal=1,i=0?！　?while(1)　　 { for (i=0?！　nt side_total[SIDE_N]。E,amp。B,amp。E,amp。A,amp。在前面數(shù)字1，2，5固定的情況下，還應選擇對應最小整數(shù)的那個排列，為此還需將后面那部分數(shù)字的排列順序顛倒，如將數(shù)字6，4，3的排列順序顛倒，得到排列1，2，5，3，4，6，這才是排列1，2，4，6，5，3的下一個排列。但為了順序從小到大列舉出所有的排列，不能立即調整得太大，如本例中將數(shù)字6與數(shù)字4交換得到的排列126453就不是排列124653的下一個排列。按數(shù)列的遞增順序逐一列舉每個排列對應的每個整數(shù)，這能更有效地完成排列的窮舉。如問題改成有9個變量排成三角形，每條邊有4個變量的情況，程序的循環(huán)重數(shù)就要相應改變?！　?printf(“%4d%4d”,b,f)。　　f=21(a+b+c+d+e)。d++) {　　 if (d==a)||(d==b)||(d==c) continue。c=6。a++) 　　 for (b=1。細節(jié)見下面的程序。求使三角形三條邊上的變量之和相等的全部解。 } while (deltaEpsilon)； delta=fabs(yx)； if (fabs(yx)delta) x=gi(X)。 y=x。 一、迭代法 常用算法設計方法(C)要使計算機能完成人們預定的工作，首先必須為如何完成預定的工作設計一個算法，然后再根據(jù)算法編寫程序。 計算機按算法指令所描述的順序執(zhí)行算法的指令能在有限的步驟內終止，或終止于給出問題的解，或終止于指出問題對此輸入數(shù)據(jù)無解。其次是算法所需要的存儲空間少和執(zhí)行更快等。另外，為了更簡潔的形式設計和藐視算法，在算法設計時又常常采用遞歸技術，用遞歸描述算法。設方程為f(x)=0，用某種數(shù)學方法導出等價的形式x=g(x)，然后按以下步驟執(zhí)行： （1）將x0的值保存于變量x1，然后計算g(x1)，并將結果存于變量x0； （3）上述算法用C程序的形式表示為： 【算法】迭代法求方程的根 {do { x0=g(x1)； } while ( fabs(x0x1)Epsilon)； X=（x0，x1，…，xn1） 設方程組為： { iprintf(“變量x[%d]的近似根是 %f”，I，x)； } 如果方程無解，算法求出的近似根序列就不會收斂，迭代過程會變成死循環(huán)，因此在使用迭代算法前應先考察方程是否有解，并在程序中對迭代的次數(shù)給予限制； （2）　　【問題】 將A、B、C、D、E、F這六個變量排成如圖所示的三角形，這六個變量分別取[1，6]上的整數(shù)，且均不相同。當這些變量取盡所有的組合后，程序就可得到全部可能的解。a=6?！　?for (c=1。d=6。e++) {　　 if (e==a)||(e==b)||(e==c)||(e==d) continue。(a+b+c==e+f+a)) {　　printf(“%6d,a)?！　　　 }　　 }　　 }　　 }　　 }　　按窮舉法編寫的程序通常不能適應變化的情況。將這組整數(shù)按從小到大的順序排列排成一個整數(shù)，從對應最小的整數(shù)開始。要尋找比長整數(shù)124653更大的排列，可從該排列的最后一個數(shù)字順序向前逐位考察，當發(fā)現(xiàn)排列中的某個數(shù)字比它前一個數(shù)字大時，如本例中的6比它的前一位數(shù)字4大，這說明還有對應更大整數(shù)的排列。5與4交換后，得到排列125643?！　nt *pt[]={amp。D,amp。A,amp。D,amp。A}。j　　 *pt[j]=j+1?！　?side_total=t。i　　 if (side_total!=side_total[i+1] equal=0?！　?scanf(“%*c”)?！　?if (j==0) break。　　 t=*pt[j1]。ij。 }　　 }　　}　　從上述問題解決的方法中，最重要的因素就是確定某種方法來確定所有的候選解?？紤]一個n元組（x0，x1，…，xn1），其中xi=0 表示第i個物品沒有選取，而xi=1則表示第i個物品被選取。而每個n元組其實對應了一個長度為n的二進制數(shù)，且這些二進制數(shù)的取值范圍為0～2n1。i2n?！　?temp_v=