《数据结构课程设计(皇后问题).》由会员分享，可在线阅读，更多相关《数据结构课程设计(皇后问题).（13页珍藏版）》请在金锄头文库上搜索。
1、课 程 设 计 报 告课程名称 数据结构课程设计 课题名称 皇后问题 专 业 信息与计算科学 班 级 信息科学1201 学 号 201210010115 姓 名 宋康 指导教师 刘长松 陈华光 陈多 2014年 6月15日课程设计任务书课程名称 数据结构课程设计 课 题 皇后问题 专业班级 信息科学1201 学生姓名 宋康 学 号 201210010115 指导老师 刘长松 陈华光 陈多 审 批 任务书下达日期： 2014年 6月 16日任务完成日期： 2014年 6月 28日一、设计内容与设计要求1设计内容：1）问题描述在N*N的方格棋盘上，放置n个皇后，要求每个皇后不同行、不同列、不同左右
2、对角线。2）实现提示算法基本思想：从第1行起逐行放置皇后，每放置一个皇后均需要依次对第1.2，n列进行试探，并尽可能取小的列数。若当前试探的列位置是安全的，即不由于回溯求解的规则是“后进先出”，因此要用到栈。2设计要求：l 课程设计报告规范1)需求分析a.程序的功能。b.输入输出的要求。2)概要设计a. 程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。b. 课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。3)详细设计a.采用C语言定义相关的数据类型。b.写出各模块的类C码算法。c.画出各函数的调用关系图、主要函数的流程
3、图。4)调试分析以及设计体会a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。b.程序调试中遇到的问题以及解决问题的方法。c.课程设计过程经验教训、心得体会。5)使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。6)书写格式见附带说明。7)附录a.参考书目b.源程序清单（带注释）l 考核方式指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分： 平时出勤 （占10%） 系统需求分
4、析、功能设计、数据结构设计及程序总体结构合理与否（占10%） 程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%） 设计报告（占30%）、注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。 独立完成情况（占10%）。l 课程验收要求 运行所设计的系统。 回答有关问题。 提交课程设计报告纸质稿。 提交源程序、设计报告文档电子稿。 依内容的创新程度，完善程序情况及对程序讲解情况打分。二、进度安排17周周一下午14：30-18：30信科1101.1102 E51317周周三上午8：00-11：30信科1101.1102 E51317周周五上午8：00-11：30信科110
5、1.1102 E513目录一、 课题叙述6 1.1 课题的来源61.2面对的问题6二、 需求分析62.1功能需求6三、 概要设计6四、 详细设计和实现74.1算法描述及详细流程图74.2算法流程图8五、 运行结果8六、 结果分析99八、 附录（源程序）10一、课题综述1. 1 课题的来源八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的。在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能
6、处于同一列、同一行、或同一条斜线上面，问共有多少种解法。计算机发明后，将8后演变成n后，可以想到n的最小值应为4。1. 2 面对的问题1）解决冲突问题：这个问题包括了行，列，两条对角线；列：规定每一列放一个皇后，不会造成列上的冲突；行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；2）使用数据结构的知识，用回溯法解决问题。二、需求分析2.1功能需求当运行程序时，在屏幕上显示每一种方法n个皇后的相对位置，要用比较直观的界面显示。三、概要设计最容易想到的方法就是有序地从第 1 列的第 1 行开始，尝试放上一个皇后，然后再尝试第 2 列的第几行能够
7、放上一个皇后，如果第 2 列也放置成功，那么就继续放置第 3 列，如果此时第3列没有一行可以放置一个皇后，说明目前为止的尝试是无效的（即不可能得到最终解），那么此时就应该回溯到上一步（即第 2 步），将上一步（第 2 步）所放置的皇后的位置再重新取走放在另一个符合要求的地方如此尝试性地遍历加上回溯，就可以慢慢地逼近最终解了。四、详细设计和实现4.1算法描述及详细流程图1）编写限界函数 bool PLACE(int k,int x)，用以确定在k列上能否放置皇后；2）编写void NQUEENS(int n)函数用以摆放N个皇后；3）编写主函数，控制输入的皇后数目；4）改进和检验程序。4.2算法
8、流程图递归回溯：主函数：五运行结果输入皇后的个数为6，程序输出如下：六.结果分析此程序用回溯算法成功地解决了N皇后问题，以上输入的值为：4，由结果的显示可知，程序切实可行。通过输入其它数值并分析可知：随着皇后数目的增大，排列的个数也越多！七总结通过这次的课程设计，我从中得到了许多经验和软件设计的一些新思路；从这个皇后问题设计以及分析中，本人从中理解到了数据结构对于软件设计的重要性，它的使用，可以改变软件的运行周期，思路从繁化简，并且都能够通过其相关引导，将本身以前编程思想进行扩充，发展.这也是在这次课程设计中我所掌握得到的。 总结一下自己，发现自己虽然在不仅在理论上没有掌握牢固，并且在实践的时
9、候也遇到了问题，所以自己还是远远的不足，不管是在数据结构课程的设计上，还是其他专业课上，在以后的一段学习时间里必须坚持自己思考，自己多动脑，多动手，这样才能脱离理论，让自己的学习更上一层楼。参考文献1. 数据结构教程/李春葆等编著.3版北京：清华大学出版社, 2009.32. 数据结构教程（第三版）上机实验教程/李春葆等编著.北京：清华大学出版社, 2009.3八程序代码#include#includeusing namespace std;int count=0; /皇后摆放的可能性bool PLACE(int k,int x);/限界函数void NQUEENS(int n);/摆放皇后i
10、nt main()int queen;cout请输入皇后的总数，谢谢！:queen;NQUEENS(queen);cout所有可能均摆放完毕,谢谢操作=0&kn) /对所有的行执行以下语句xk=xk+1; /移到下一列while(xk=n&(!PLACE(k,x) /此处能放置一个皇后吗?xk=xk+1; /移到下一列if( xk=n ) /找到一个位置if( k=n-1 ) /是一个完整的解吗cout第+count排法是：endl;for(int i=0;in;i+)/打印皇后的排列for (int j=0;jn;j+)if (xi = j+1)cout*;elsecout. ;coutn;
11、coutn; else k=k+1; xk=0; /移向下一行else k=k-1; /回溯bool PLACE(int k,int x)/* 如果一个皇后能放在第k行和x(k)列，返回ture;否则返回false。x是一个全局变量，进入此过程的时候已经置了k个值。ABS(r)过程返回r的绝对值*/int i=0;while (ik)if( xi=xk|abs(xi-xk)=abs(i-k) )return (false); /在同一列 或者在同一斜角线上 有两个皇后 i=i+1;return (true); 首先找出解空间：给棋盘的行和列都编上1到N的号码，皇后也给编上1到N的号码。由于一个
12、皇后应在不同的行上，为不失一般性，可以假定第i个皇后将放在第i行上的某列。因此N皇后问题的解空间可以用一个N元组（X1，X2，.Xn）来表示，其中Xi是放置皇后i所在的列号。这意味着所有的解都是N元组（1，2，3，.，N）的置换。解空间大小为N！。其次我们看约束条件：因为解空间已经给我们排除了不在同一行（因为每个皇后分别已经对应不同的行号）的约束条件。我们要判断的是不在同一列和不在同一斜线的约束。因为Xi表示皇后所在的列号，所以如果存在X（k）=X（i）那么肯定存在第k个皇后和第i个皇后同列。所以不同列的判段条件是X（k）！=X（i），1ki 。又因为同一斜线的特征是要么行号和列号之和不变（右高左低）要么是行号和列号只差相等（左高右低），所以同斜线的判断条件是 i+X（i）= k+X（k) 或 i-X(i) =k-X(k),两式合并得 |X(i)-
