第六章 算法设计技术

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