《(陈慧南-第3版)算法设计与分析——第8章课后习题答案》由会员分享，可在线阅读，更多相关《(陈慧南-第3版)算法设计与分析——第8章课后习题答案（6页珍藏版）》请在金锄头文库上搜索。
1、第八章课后习题 姓名：赵文浩 学号：16111204082 班级：2016 级计算机科学与技术 8-3 重新定义函数 Place()， 使得它或者返回下一个合法的列号或返回-1 表示没有不冲突的列号，并按这种做法改写程序 8-4 的 Place 和 NQeens 函数。 解析： 8-4 图 8-4 所示的两个可行解是对称的。观察表明，n-皇后问题的解的确存在这种对偶性。修改算法 NQueens，令01,2,2xn，使得只求其中不对称的那些解。 解析： 为了解决对称性的冲突，只需在第一层时，遍历一半的列号即可。 改写后的程序如下： #include #include using namespac
2、e std; bool Place(int k,int i,int *x); void NQueens(int k,int n,int *x); int main() int n; cinn; int *x=new intn; NQueens(0,n,x); return 0; bool Place(int k,int i,int *x) int j; for(j=0;jk;j+) if(xj=i)|(abs(xj-i)=abs(j-k) return false; return true; void NQueens(int k,int n,int *x) int i,j; if(k=0) f
3、or(i=0;in/2;i+) if(Place(k,i,x) xk=i; if(k=n-1) for(j=0;jn;j+) coutxj ; coutendl; else NQueens(k+1,n,x); else for(i=0;in;i+) if(Place(k,i,x) xk=i; if(k=n-1) for(j=0;jn;j+) coutxj ; coutendl; else NQueens(k+1,n,x); 8-6 设 有 子 集 和 数 问 题 的 实 例( 0, 1, 6)(5,7,10,12,15,18,20)Wwww和35M 。 求W中元素之和等于M的所有子集。 画出对
4、于这一实例由SumOfSub算法实际生成的那部分状态空间树。 解析： 构造的状态空间树如图所示： 从图中可以看出，满足和为 M 的子集共有 4 个，分别是： (1,0,1,0,0,0,1)(1,0,0,1,0,1,0)(0,1,1,0,0,1,0)(0,0,0,0,1,0,1)ABCD 8-9 （更改）设计程序，该程序的功能是给定一个待着色的图，在指定提供颜色种类个数的情况下，返回能否给该图成功着色，并给出相应输出提示（相邻区域颜色不同） 。 解析： 本程序只需基于课本 P171-P172 m-着色算法，对程序进行修改，满足题目要求即可，更改主要体现在着色方案的计数上。 更改后的程序如下： /
5、m-着色问题 #include using namespace std; void CreateGraph(); void PrintGraph(); void NextValue(int k,int m,int *x); void mColoring(int k,int m,int *x); int *a;/邻接矩阵 int V;/顶点数（带着色区域个数） int E;/边数 int flag=0;/标志是否有可行的着色方案 int main() int i; int m;/颜色种类 int *x;/着色方案 CreateGraph(); PrintGraph(); x=new intV;
6、for(i=0;iV;i+) x0=0;/着色方案初始化 cout请输入给定的颜色种类m; if(flag=1) cout可行的着色方案如下：endl; mColoring(0,m,x); else cout无可行的着色方案endl; return 0; void CreateGraph() int i,j; int m1,m2; cout请输入顶点个数 VV; cout请输入边数 EE; a=new int*V; for(i=0;iV;i+) ai=new intV; /- for(i=0;iV;i+) for(j=0;jV;j+) aij=0;/邻接矩阵初始化 /- cout请依次输入E条
7、边，用边相邻的两个顶点编号表示endl; for(i=0;im1m2; am1m2=1; am2m1=1; void PrintGraph() int i,j; cout创建的邻接矩阵为：endl; for(i=0;iV;i+) for(j=0;jV;j+) coutaij ; coutendl; void NextValue(int k,int m,int *x) int j; do xk=(xk+1)%(m+1); if(!xk) return; for(j=0;jk;j+) if(akj&xk=xj) break; if(j=k) return; while(1); void mColoring(int k,int m,int *x) int i; do NextValue(k,m,x); if(!xk) break; if(k=V-1) flag=1; for(i=0;iV;i+) coutxi ; coutendl; else mColoring(k+1,m,x); while(1);
