八皇后问题的解决完整文档 .docx

《八皇后问题的解决完整文档 .docx》由会员分享，可在线阅读，更多相关《八皇后问题的解决完整文档 .docx（18页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精品名师归纳总结淮阴工学 院数据结构课程设计报告设计题目 ：八皇后 系（院） :计 算 机 工 程系专业：信 息 安 全班级：信 息 1 0 6同学姓名 :叶 青学 号: 1061303127指导老师 :张亚红 寇海洲 胡荣林 夏森学年学期 : 2007 2021 学年第 2 学期2021年6月 25日可编辑资料 - - - 欢迎下载精品名师归纳总结设计任务书课题八皇后名称1. 用 c+语言平台将一个的棋盘上放上个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92 种结构予以实设计现目的2. 通过这次课程设计 ,提高自己的编程才能 ,熟识 c+的编程坏境 ,为以后的程序

2、开发打下基础 .1） 系统要求： win98 以上操作系统。试验2）语言平台： tc+或 vc+6.0。环境3 ） 执行文件：八皇后 .exe试编写程序实现将八个皇后放置在国际象棋棋盘的无冲突的位置上的算法， 并给出全部的解。任务要求序号起止日期工作进度方案工 作 内 容12021.6.232021.6.24查阅相关内容22021.6.242021.6.25编写代码及实习报告32021.6.252021.6.26完善课程设计报告42021.6.262021.6.27答辩指导老师（签章）：2021年 6 月 30 日可编辑资料 - - - 欢迎下载精品名师归纳总结摘要：八皇后问题要求在一个 的棋

3、盘上放上 个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击依据国际象棋的规章，一个皇后可以攻 击与之处在同一行或同一列或同一斜线上的其他任何棋子因此，八皇后问题等于要 求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。而本课程设计本人的目的也是通过用 c+ 语言平台将一个 的棋盘上放上 个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的 92 种结构予以实现 使用递归方法最终将其问题变得一目了然，更加易懂。关键词： 八皇后 。 c+。 递归法可编辑资料 - - - 欢迎下载精品名师归纳总结目 录1. 课题综述 .1.1. 1 课题的来源及意

4、义11. 2 面对的问题12. 需求分析 .1.2. 1 涉及到的学问12. 2 软硬件的需求12. 3 功能需求23. 概要设计 .2.4. 具体设计和实现 .2.4. 1 算法描述及具体流程图24.1.1 算法描述34.1.2 算法流程图35. 代码编写及具体注释 .4.6. 程序调试 .7.6. 1 调试过程、步骤及遇到的问题77. 运行与测试 .7.7.1 运行演示7总结.9.致谢 1.0.参考文献11.可编辑资料 - - - 欢迎下载精品名师归纳总结1. 课题综述1. 1 课题的来源及意义八皇后问题是一个古老而闻名的问题，该问题是十九世纪闻名的数学家高斯1850 年提出的。在国际象棋

5、中，皇后是最有权益的一个棋子。只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8 的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。到了现代，随着运算机技术的飞速进展，这一古老而好玩的数学嬉戏问题也自然而然的被搬到了运算机上。运用所学运算机学问来试着解决这个问题是个锤炼和提高我自己编程才能和独立解决问题才能的好机会，可以使我增强信心，为我以后的编程开个好头，故我挑选了这个好玩的课题。1. 2 面对的问题1） 解决冲突问题：这个问题包括了行，列，两条对角

6、线。列：规定每一列放一个皇后，不会造成列上的冲突。行：当第 I 行被某个皇后占据后，就同一行上的全部空格都不能再放皇后，要把以 I 为下标的标记置为被占据状态。2） 使用数据结构的学问，用递归法解决问题。2. 需求分析2. 1 涉及到的学问本次课程设计中，用到的主要学问有：递归法的运用，for 语句的敏捷运用， 数据结构中树学问的敏捷运用、栈及数组的把握。2. 2 软硬件的需求可编辑资料 - - - 欢迎下载精品名师归纳总结1）系统要求： win98 以上操作系统。2 语言平台： tc+或 vc+6.0。2. 3 功能需求当运行程序时，在屏幕上显示每一种方法八个皇后的相对位置，要用比较直观的界

7、面显示。3. 概要设计本课件同学是用循环递归循环来实现的，分别一一测试了每一种摆法，并把它拥有的 92 种变化表现出来。在这个程序中，我的主要思路以及思想是这样的：1） 解决冲突问题：这个问题包括了行，列，两条对角线。列：规定每一列放一个皇后，不会造成列上的冲突。行：当第 I 行被某个皇后占据后，就同一行上的全部空格都不能再放皇后，要把以 I 为下标的标记置为被占据状态。对角线：对角线有两个方向。在这我把这两条对角线称为：主对角线和从对角线。在同一对角线上的全部点（设下标为i,j ），要么 i+j 是常数，要么 i-j 是常数。因此，当第 I 个皇后占据了第 J 列后，要同时把以 i+j 、i

8、-j 为下标的标记置为被占据状态。2） 数据结构的实现而对于数据结构的实现，同学就是着重于:数组 aI ： a I 表示第 I 个皇后放置的列。 I 的范畴： 1.8。对角线数组： bj 主对角线 ,cj （从对角线），依据程序的运行，去打算主从对角线是否放入皇后。4. 具体设计和实现4. 1 算法描述及具体流程图可编辑资料 - - - 欢迎下载精品名师归纳总结4.1.1 算法描述A、 数据初始化。B、 从 n 列开头摆放第 n 个皇后（由于这样便可以符合每一竖列一个皇后的要求），先测试当前位置（ n，m）是否等于 0（未被占据）。假如是，摆放第n 个皇后，并宣布占据（记得姚横列竖列斜列一起设

9、置），接着进行递归。假如不是，测试下一个位置（ n，m+1），但是假如当 n8 时，便打印出结果。E、输出函数我使用 printf 输出，运行形式为：第 m 种方法为： * * * * * * * *4.1.2 算法流程图可编辑资料 - - - 欢迎下载精品名师归纳总结5. 代码编写及具体注释#include #include #include #include #include #define QUEENS 8int iCount = 0。 /.记录解的序号的全局变量。int SiteQUEENS。 /.记录皇后在各行上的放置位置的全局数组。可编辑资料 - - - 欢迎下载精品名师归纳总结v

10、oid Queenint n。 /.递归求解的函数。void Output。/.输出一个解。int IsValidint n。/.判定第 n 个皇后放上去之后，是否有冲突。void main /*-Main：主函数。 -*/systemtitle叶青- 递归算法八皇后问题 。cout八皇后的解法： endl 。cout-endl。Queen0 。 /.从第 0 行开头递归摸索。getch。/.按任意键返回。void Queenint n/*-Queen：递归放置第n 个皇后，程序的核心 .*/int i。ifn = QUEENS /.参数 n 从 0 开头，等于 8 时便试出了一个解，将它输出

11、并回溯。Output。return。 fori = 1。 i = QUEENS 。 i+ /.n仍没到 8，在第 n 行的各个行上依次摸索。可编辑资料 - - - 欢迎下载精品名师归纳总结Siten = i。 /.在该行的第 i 行上放置皇后。ifIsValidn/.假如放置没有冲突，就开头下一行的摸索。Queenn + 1。 int IsValidint n /*-IsValid：判定第 n 个皇后放上去之后，是否合法，即是否无冲突。*/int i。fori = 0。 i n。 i+ /.将第 n 个皇后的位置依次于前面 n1 个皇后的位置比较。ifSitei = Siten /.两个皇后在

12、同一列上，返回 0。return 0。ifabsSitei - Siten = n - i /.两个皇后在同一对角线上，返回 0。return 0。 return 1。 /.没有冲突，返回 1。void Output/*-Output：输出一个解，即一种没有冲突的放置方案。*/int i。printfNo.%-5d , +iCount。 /.输出序号。可编辑资料 - - - 欢迎下载精品名师归纳总结fori = 0。 i QUEENS 。 i+/.依次输出各个行上的皇后的位置，即所在的列数。printf%d , Sitei。printfn。6. 程序调试6. 1 调试过程、步骤及遇到的问题在完

13、整程序调试时遇到几个小问题，后经细心改正后才把调试工作做完。例如:当用 printf 输出时,显现了一些错误 ,几经调试后 ,发觉原先是缺少了 stdio.h 这样一个头文件 ,添加了头文件后 , 仍显现了一些问题 ,规律错误导致程序死循环或不循环或循环一小部分 ,但是编译时却没有错误 ,就是没有正确的输出答案 ,一开头我也不知道是怎么回事 ,通过和同学的沟通 ,发觉是规律错误 ,经过改正后 ,程序最终可以运行了.7. 运行与测试7.1 运行演示可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结总结通过了 19 周这个星期的程序设计，我从中得到了很

14、多的体会以及软件设计的一些新的思路。从这个八皇后问题设计以及分析中，本人从中懂得到了数据结构对于运算机软件设计的重要性，它的使用，可以转变一个软件的运行周期，也可以将软件的思路从繁化简，并且都能够通过数据结构的相关引导，将本身以前编程思想进行扩充， 进展。这也是在这次课程设计中我所把握得到的。但由于我的基本学问仍不是那么扎实，也缺乏对软件设计的体会，在这过程中也出现了一些问题，如，八皇后在变成初期由于没真正体会到数据结构中“树”在里面的运用，将程序往大一时c 语言的方向进展，不自觉的采纳了非递归的算法，结果大大增加了程序的复杂程度。并且也让整个程序的时间复杂度变得更大。在后来同学对数据结构的第

15、六章进行了比较深化的研读，才发觉了数据结构树的实际运用的空间是相当的大，并且，通过了重温树的回溯，以及二叉树的遍历，最终将程序进行了一次较大的改造。并且通过摸索，再将以前的数组学问加以运用才最终解决了这个问题，整个程序的算法的可看性也有了相当的改进。课程设计随着时间的推移，也即将终止了，但这个学期数据结构的学习仍是具有相当大的意义，它从一个程度上转变了我们的编程思想，如何将一个程序快速而又预备的进行编写，进行编译，都成为了我们摸索的重点，也通过这一个学期的学习，我们将数据结构的思想带入到了我们以后的编程学习中去。在这个阶段，我也明白了，好的思想，不能提留于字面上的认知，仍需要的是平常多练多写一

16、些相关的程序，并且通过修改，加入新的算法去尝试转变自己的一些编程思想。保持更新算法的速度，这才是关键。课程设计已经接近尾声了，但它给我的不只是程序设计上的满意，更重要的是对自己编程思想的一次更新，以及对算法的一个全新的熟识！我觉得仍可以考虑开发 N 皇后问题 ,在主界面中添加一个 int 型的变量 ,程序一开头要求输入一个数 确定是几皇后问题 ,输入后按下 enter 后,输出各种解 .主程序与八皇后的求解大体相同 .可编辑资料 - - - 欢迎下载精品名师归纳总结致谢在这次课程设计中 ,我遇到了不少问题 ,包括程序上的和课程设计的撰写上的,同学曾给过我很多帮忙 ,在此我表示对他们的忠心感谢。

17、同时，指导老师和试验人员给了我很多上机的机会，给了我一个做课程设计的很好的条件，我才能够顺当的完成，在此，我仅以文字的形式表示忠心感谢，感谢他们这么多天对我的帮忙。可编辑资料 - - - 欢迎下载精品名师归纳总结参考文献1 苏仕华,数据结构课程设计 .-北京:机械工业出版社 ,2005.52 于永彦,赵建洋.课程设计指导书 .淮安：江苏淮阴工学院运算机工程系 ,20063 刘振安,刘燕君，孙忱 . C+ 语言课程设计 .北京：高等训练出版社 ,20034 陈志泊, 张海燕, 王春玲. Visual C+ 程序设计 . 中国铁道出版社 ,20055 吕凤哲,C+语言程序设计（其次版） .北京：电

18、子工业出版社 ,20056 殷人昆，陶永雷等 . 数据结构（用面对对象方法与C+ ）. 北京: 清华高校出版社， 19997 严蔚敏，吴伟民，数据结构北京：清华高校出版社，19978 李春葆. 数据结构考研指导 . 北京: 清华高校出版社 ,20029 陈慧南数据结构 C+语言描述北京：人民邮电出版社， 200503可编辑资料 - - - 欢迎下载精品名师归纳总结指导老师评语学号1061303127姓名叶 青班级信 息 106可编辑资料 - - - 欢迎下载精品名师归纳总结选题名称序号评判内容八 皇 后权重得分（%）可编辑资料 - - - 欢迎下载精品名师归纳总结1 考勤记录、学习态度、工作作风与表现。5自学情形：2 上 网检 索机时数、 文 献阅 读情 况（ 笔10记）。论文选题是否先进，是否具有前沿性或前瞻35性。成果验收：4是否完成设计任务。能否运行、可操作性20如何等。报告的格式规范程度、是否图文并茂、语言规范及流畅程度。主题是否鲜明、重心是否突530出、论述是否充分、结论是否正确。是否提出了自己的独到见解。6 文献引用是否合理、充分、真实。5答辩情形：7 自我陈述、回答疑题的正确性、用语精确25性、规律思维、是否具有独到见解等。合计指导老师（签章）：2021 年 6 月 30 日可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载