1、 3021 圖圖6.233方格的編號和一個解的實例方格的編號和一個解的實例#include #include #define MAXN 8int colMAXN+1,aMAXN+1, b2*MAXN+1,c2*MAXN+1;char chess2*MAXN+1 4*MAXN+3 = , , , , , , , , ,;void putOut(int *r, int n) int j , k, p; char ans; printf( 列t行n); for(j = 1; j = n; j+) printf(%3dt%dn, j, colj); for(k = 0; k n; k+) for(p

2、= 0; p n; p+) chess2*k+14*p+2 =chess2*k+14*p+3 = ; for(j = 1; j = n; j+) chess2*colj-14*j-2= Q; for(k = 0; k 17; k+) printf(%sn, chessk); printf(繼續找下一個解嗎？(y/q:quit)n); scanf( %c,&ans); if(ans =Q | ans =q)exit(1);int check(int m, int n) / 檢查m列配置的合理性 return acolm & bm+colm & cn+m-colm; int change(int

3、m, int n) while (colm = n) / 回溯調整，形成下一個候選解 / 回退一列，并清除關于第 m-1 列, colm-1 行有皇后標志 m-; acolm = bm+colm = cn+m-colm= 1; colm+; / 調整第 m 列的皇后配置 return m;int n, m, good;void main() int j; n = 8; for(j = 0; j = n; j+) aj = 1; for(j = 0; j = 2*n; j+) bj = cj = 1;/棋盤空，所有位置，斜線都無皇后 m = 1; col1 = 1; good = 1; col0

4、 = 0; do if (good) acolm = bm+colm = cn+m-colm = 0; if (m = n) /找到了一個解 putOut(col, n); acolm = bm+colm = cn+m-colm = 1; change(m, n); else / m != n,擴展，進入下一列，并置第一行上 col+m = 1; /進入第 m+1 列, 從第 1 行開始配置 */ else m = change(m, n); good = check(m, n); while (m != 0); 工作工作運行時間運行時間J115J28J33J410 表表6.1 工作和運行時間

5、表工作和運行時間表方案，由于方案，由于J1J1在第在第1515單位時間結束，單位時間結束，J2J2在第在第2323單位時間結束，單位時間結束，J3J3在在第第2626單位時間結束，單位時間結束，J4J4在第在第3636單位時間結束，所以平均完成時間為單位時間結束，所以平均完成時間為2525單位時間。單位時間。方案方案2 2，不難計算，該方案的平均完成時間是，不難計算，該方案的平均完成時間是17.7517.75單位時間。方案單位時間。方案的特點是工作時間短的優先。可以證明，方案的策略總能得到最優的特點是工作時間短的優先。可以證明，方案的策略總能得到最優解。解。設某個調度方案為設某個調度方案為J

6、Ji1i1、J Ji2i2、J JiNiN，則，則J Ji1i1在在t ti1i1完成，完成，J Ji2i2在在t ti1i1+t+ti2i2完成，完成，全部工作的完成時間和是：，全部工作的完成時間和是：公式的第一項與調度方案無關，只有第二項影響總的完成時間公式的第一項與調度方案無關，只有第二項影響總的完成時間，欲得到最小的，應讓第二項取最大值，就應該讓工作時間，欲得到最小的，應讓第二項取最大值，就應該讓工作時間長的按排在靠后做，所以方案的策略是最優策略。長的按排在靠后做，所以方案的策略是最優策略。NkkNC1ikt ) 1(NkikNkiktkNCt11*) 1(分治法的分（分治法的分（Di

7、videDivide）是指：劃分一個大問題為若干個較小）是指：劃分一個大問題為若干個較小的子問題。治（的子問題。治（ConquerConquer）就是：從子問題的解決構建原）就是：從子問題的解決構建原問題的解。問題的解。1、選擇問題、選擇問題2、找最短距離點對、找最短距離點對 4 4、排序問題、排序問題排序的目標是給定一系列對象（如整數），將這些對象按從排序的目標是給定一系列對象（如整數），將這些對象按從小到大（或從大到小）的順序排好小到大（或從大到小）的順序排好( (一一) ) 歸并排序法歸并排序法(merge sorting)(merge sorting)。把待排序的整數直接等分為前半段和

8、后半組用分治法繼續排把待排序的整數直接等分為前半段和后半組用分治法繼續排序獲得每組從小到大的排序結果，然后將這兩組結果合并形序獲得每組從小到大的排序結果，然后將這兩組結果合并形成一個從小到大的序列。這就是歸并排序法的主要思想。這成一個從小到大的序列。這就是歸并排序法的主要思想。這種思路主要的工作量是在合并結果上。一個具體的種思路主要的工作量是在合并結果上。一個具體的1010個數的個數的排序問題為例，說明歸并排序法的主要過程。排序問題為例，說明歸并排序法的主要過程。 ( (二二) ) 快速排序快速排序把待排序的整數分為比基準元素小的一組和比基準把待排序的整數分為比基準元素小的一組和比基準元素大的

9、一組；然后，對每組繼續用元素大的一組；然后，對每組繼續用 排序法排序法(quick sorting)(quick sorting)。取一個基準整數，將所有整數。取一個基準整數，將所有整數與這個基準整數進行比較，與這個基準整數進行比較， 1 花瓶花瓶j(1jv)j(1jv)中若被放入一束鮮花，則鮮花編號的中若被放入一束鮮花，則鮮花編號的可能范圍為可能范圍為(1.j)(1.j)。設。設pijpij為鮮花為鮮花i i放入花瓶放入花瓶j j的好的好看程度，按問題的說明，這由輸入給定。看程度，按問題的說明，這由輸入給定。另設另設qijqij為鮮花為鮮花1.i1.i放入花瓶放入花瓶1.j1.j所能得到的最

10、大所能得到的最大好看程度。首先有：好看程度。首先有：q00 = 0, q0j = q00 = 0, q0j = 0(1jv)0(1jv)。而。而qfvqfv正是問題的解答。正是問題的解答。特別地，特別地，j j束鮮花插到前面束鮮花插到前面j j只花瓶中，即每束鮮花插只花瓶中，即每束鮮花插在相同編號的花瓶中，如此插花方案的好看程度為在相同編號的花瓶中，如此插花方案的好看程度為qjj = p11 + p22+pjjqjj = p11 + p22+pjj。將求解過程按花瓶排列順序劃分，鮮花以編號從小到將求解過程按花瓶排列順序劃分，鮮花以編號從小到大的順序插到花瓶中，現考慮編號為大的順序插到花瓶中，現考慮編號為i i的一束鮮花的插的一束鮮花的插入。第入。第i i束鮮花若插在花瓶束鮮花若插在花瓶j j，最大好看程度為，最大好看程度為qi-qi-1j-1+pij1j-1+pij；若第；若第i i束鮮花插入前束鮮花插入前j-1j-1個花瓶中的個花瓶中的某一個，所得好看程度應為某一個，所得好看程度應為qij-1qij-1。這樣，在階段。這樣，在階段j