八皇后问题的C课程设计

课 程 设 计 报 告学院、系：专业名称：课程设计科目VC+程序课程设计学生姓名：指导教师：完成时间：八皇后问题一、设计任务与目标 1. 用c+语言平台将一个的棋盘上放上个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现。2. 通过这次课程设计,提高自己的编程能力,熟悉c+的编程坏境,为以后的程序开发打基础。 二、方案设计与论证在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面。我的主要思路以及思想如下：1. 解决冲突问题： 这个问题包括了行，列，两条对角线； 列：规定每一列放一个皇后，不会造成列上的冲突； 行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态； 对角线：对角线有两个方向。在这我把这两条对角线称为：主对角线和从对角线。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。 2.数据结构的实现 ：数组aI：a I表示第I个皇后放置的列；I的范围：1.8; 对角线数组：bj(主对角线),cj（从对角线），根据程序的运行，去决定主从对角线是否放入皇后；算法描述A、 数据初始化。B、 从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置（n，m）是否等于0（未被占领）。如果是，摆放第n个皇后，并宣布占领（记得要横列竖列斜列一起设置），接着进行递归；如果不是，测试下一个位置（n，m+1），但是如果当n8时，便打印出结果。E、输出函数我使用printf输出，运行形式为：第m种方法为：* * * * * * * * 三、程序框图或流程图，程序清单与调用关系4、 全部源程序清单#include #include #include #include #include #define QUEENS 8int iCount = 0; /!记录解的序号的全局变量。int SiteQUEENS; /!记录皇后在各行上的放置位置的全局数组。void Queen(int n); /!递归求解的函数。void Output();/!输出一个解。int IsValid(int n); /!判断第n个皇后放上去之后，是否有冲突。void main() /*-Main：主函数。-*/ system(title 递归算法八皇后问题 );cout 八皇后的解法：endl;cout -endl; Queen(0); /!从第0行开始递归试探。 getch();/!按任意键返回。 void Queen(int n) /*-Queen：递归放置第n个皇后，程序的核心!-*/ int i; if(n = QUEENS) /!参数n从0开始，等于8时便试出了一个解，将它输出并回溯。 Output(); return; for(i = 1 ; i = QUEENS ; i+) /!n还没到8，在第n行的各个行上依次试探。 Siten = i; /!在该行的第i行上放置皇后。 if(IsValid(n) /!如果放置没有冲突，就开始下一行的试探。 Queen(n + 1); int IsValid(int n) /*-IsValid：判断第n个皇后放上去之后，是否合法，即是否无冲突。-*/ int i; for(i = 0 ; i n ; i+) /!将第n个皇后的位置依次于前面n1个皇后的位置比较。 if(Sitei = Siten) /!两个皇后在同一列上，返回0。 return 0; if(abs(Sitei - Siten) = (n - i) /!两个皇后在同一对角线上，返回0。 return 0; return 1; /!没有冲突，返回1。 void Output()/*-Output：输出一个解，即一种没有冲突的放置方案。-*/ int i; printf(No.%-5d , +iCount); /!输出序号。 for(i = 0 ; i QUEENS ; i+)/!依次输出各个行上的皇后的位置，即所在的列数。 printf(%d , Sitei); printf(n); 五、程序运行的测试与分析 六、结论与心得 通过这次的程序设计，我从中得到了许多的经验以及软件设计的一些新的思路；从这个八皇后问题设计以及分析中，本人从中理解到了数据结构对于计算机软件设计的重要性，它的使用，可以改变一个软件的运行周期，也可以将软件的思路从繁化简，并且都能够通过数据结构的相关引导，将本身以前编程思想进行扩充，发展；这也是在这次课程设计中我所掌握得到的。 但由于我的基本知识还不是那么扎实，也缺乏对软件设计的经验，在这过程中也出现了一些问题，如，八皇后在变成初期由于没真正体会到数据结构中“树”在里面的运用，将程序往大一时c语言的方向发展，不自觉的采用了非递归的算法，结果大大增加了程序的复杂程度。并且也让整个程序的时间复杂度变得更大；在后来学生对数据结构的第六章进行了比较深入的研读，才发现了数据结构树的实际运用的空间是相当的大，并且，通过了重温树的回溯，以及二叉树的遍历，最终将程序进行了一次较大的改造。并且通过思考，再将以前的数组知识加以运用才最终解决了这个问题，整个程序的算法的可看性也有了相当的改进。 课程设计随着时间的推移，也即将结束了，但这上学期数据结构的学习还是具有相当大的意义，它从一个程度上改变了我们的编程思想，如何将一个程序快速而又准备的进行编写，进行编译，都成为了我们思考的重点，也通过这一个学期的学习，我们将数据结构的思想带入到了我们以后的编程学习中去。在这个阶段，我也明白了，好的思想，不能提留于字面上的认知，还需要的是平时多练多写一些相关的程序，并且通过修改，加入新的算法去尝试改变自己的一些编程思想。保持更新算法的速度，这才是关键。 课程设计已经接近尾声了，但它给我的不只是程序设计上的满足，更重要的是对自己编程思想的一次更新，以及对算法的一个全新的认识！ 我觉得还可以考虑开发N皇后问题,在主界面中添加一个 int型的变量,程序一开始要求输入一个数(确定是几皇后问题),输入后按下 enter 后,输出各种解.主程序与八皇后的求解大体相同. 七、参考资料 参考文献1 陈守孔，孟佳娜，算法与数据结构c语言版. 机械工业出版社2 严蔚敏，吴伟民，数据结构清华大学出版社3 刘斌，王忠，面向对象程序设计Visual C+ . 清华大学出版社课程设计成绩评定表对课程设计工作过程的简短介绍和自我评价 学生签名：2010年 月 日（以下由评定小组教师填写）质量评价指标（在相应栏目打）评 价 项 目评 价 质 量优秀良好一般及格不及格工作量和态度实验、计算可靠性文字和图表质量总体评价评定成绩（百分制）评定小组成员签名2010年 月 日制定人： 审定人：10 / 11文档可自由编辑打印