数据结构课程设计 八皇后问题.doc
《数据结构课程设计 八皇后问题.doc》由会员分享,可在线阅读,更多相关《数据结构课程设计 八皇后问题.doc(29页珍藏版)》请在沃文网上搜索。
1、目 录第一章 八皇后问题概述- 1 -1.1 课题的描述- 1 -1.2 需求分析- 1 -1.2.1 涉及到的知识- 1 -1.2.2 模块的功能要求- 1 -1.2.3 软硬件的需求- 2 -1.2.4 面对的问题- 2 -1.3 概要设计- 2 -1.3.1 结构设计理念- 2 -1.3.2 算法流程图- 3 -1.4详细设计和实现- 4 -1.5 程序调试- 6 -1.5.1 问题思考及改进设想- 6 -1.5.2运行与测试- 7 -1.6 课设总结- 9 -第二章 n阶魔阵问题概述- 10 -2.1课题的描述- 10 -2.2 需求分析- 10 -2.2.1 涉及到的知识- 10 -
2、2.2.2 模块的功能需求- 10 -2.2.3 软硬件的需求- 10 -2.2.4 面对的问题- 10 -2.3 概要设计- 11 -2.3.1算法设计理念- 11 -2.3.2 函数逻辑功能调用图- 11 -2.3.3 算法流程图- 12 -2.4详细设计和实现- 12 -2.4.1代码编写及详细设置- 12 -2.5 程序调试- 15 -2.5.1 问题思考及改进设想- 15 -2.5.2 运行与测试- 15 -2.6 课设总结- 18 -参考文献- 19 -结束语- 20 -附 录- 21 -I第1章 八皇后问题概述第一章 八皇后问题概述1.1 课题的描述 八皇后问题是一个古老而著名的
3、问题,该问题是十九世纪著名的数学家高斯1850年提出的。八皇后问题是在8*8的国际象棋棋盘上,安放8皇后,要求没有一个皇后能够“吃掉”任何其他一个皇后,即没有两个或两个以上的皇后占据棋盘上的同一行、 同一列、或同一对角线。到了现代,随着计算机技术的飞速发展,这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上。运用所学计算机知识来试着解决这个问题是个锻炼和提高我自己编程能力和独立解决问题能力的好机会,可以使我增强信心,为我以后的编程开个好头,故我选择了这个有趣的课题。1.2 需求分析1.2.1 涉及到的知识本次课程设计中,用到的主要知识有:递归法的运用,for语句的灵活运用,数据结构中树知
4、识的灵活运用、栈及数组的有关知识的掌握。要求熟练运用C+语言、基本算法的基础知识,独立编制一个具有中等难度的、解决实际应用问题的应用程序。通过对题意的分析与计算,用递归法回溯法及枚举法解决八皇后是比较适合的。递归是一种比较简单的且比较古老的算法。回溯法是递归法的升华,在用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束。而枚举法,更是一种基础易懂简洁的方法。把它们综合起来,就构成了今天的算法。不论用什么法做这个课题,重要的就是先搞清楚哪个位置是合法的放皇后的位置,哪个不能,要先判断,后放置。1.2.2 模块的功能要求 当运行程序时,在屏幕上显示每一种方法八个皇后的相对位置,
5、要用比较直观的界面显示。列:规定每一列放一个皇后,不会造成列上的冲突; 行:当第I行被某个皇后占领后,则同一行所不能再放皇后,要把以I为下标的标记置为被占领状态;对角线:对角线有两个方向。在这我把这两条对角线称为:主对角线和从对角线。在同一对角线上的所有点(设下标为(i,j)),要么(i+j)是常数,要么(i-j)是常数。因此,当第I个皇后占领了第J列后,要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。 用数组aI:a I表示第I个皇后放置的列;I的范围:1-8;对角线数组:bj(主对角线),cj(从对角线),根据程序的运行,去决定主从对角线是否放入皇后。1.2.3 软硬件的需求(
6、1)系统要求:win98以上操作系统; (2)语言平台:tc+或vc+6.0;1.2.4 面对的问题 (1)列:规定每一列放一个皇后,不会造成列上的冲突; 行:当第I行被某个皇后占领后,则同一行上的所有空格都不能再放皇 后,要把以I为下标的标记置为被占领状态; 对角线:对角线有两个方向。在这我把这两条对角线称为:主对角线和从对角线。在同一对角线上的所有点(设下标为(i,j)),要么(i+j)是常数,要么(i-j)是常数。因此,当第I个皇后占领了第J列后,要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。(2)使用数据结构的知识,用递归法解决问:。数组aI:a I表示第I个皇后放置的列
7、;I的范围:1.8; 对角线数组:bj(主对角线),cj(从对角线),根据程序的运行,去决定主从对角线是否放入皇后;1.3 概要设计1.3.1 结构设计理念(1)从n列开始摆放第n个皇后(因为这样便可以符合每一竖列一个皇后 的要求),先测试当前位置(n,m)是否等于0(未被占领)。如果是,摆放第n个皇后,并宣布占领,接着进行递归;如果不是,测试下一个位置(n,m+1),但是如果当n8时,便打印出结果。1.3.2 算法流程图图1-1 算法流程图 序图1-11.4详细设计和实现#include #include #include #include #include #define QUEENS 8
8、int iCount = 0; /!记录解的序号的全局变量。int SiteQUEENS; /!记录皇后在各行上的放置位置的全局数组。void Queen(int n); /!递归求解的函数。void Output();/!输出一个解。int IsValid(int n); /!判断第n个皇后放上去之后,是否有冲突。void main() /*-Main:主函数。-*/ system(title 管理102孙海龙 八皇后问题 );cout 八皇后问题:endl;cout -endl; Queen(0); /!从第0行开始递归试探。 getch();/!按任意键返回。 void Queen(in
9、t 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;
10、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+)/!依次输出各个
11、行上的皇后的位置,即所在的列数。 printf(%d , Sitei); cout” ”endl; 1.5 程序调试1.5.1 问题思考及改进设想在完整程序调试时由于太急于求成导致程序进行循环时出现无法运行的问题,逻辑错误导致程序死循环或不循环或循环一小部分,后经细心改正后才把调试工作做完。做程序真的不是三两下就能完美的做好的,正应了那句话“心急吃不了热豆腐啊”。但对于这个程序我由于c+语言学的不到位以至于有些掺杂了c语言的有关算法,要是都用c+来编写就再好不过了。在编写代码时,我希望能随机选择一数 X(192)后,能输出该种情况所对应的八个皇后的摆放方式和每个皇后所在的位置,但想了好久,就是
12、无法实现。而且,当92种情况都输出时,前面的几十种情况无法看到,要想让摆放皇后的图形和所在具体的位置一起输出,就得修改程序让使她们一个一个地输出,这样显然比较麻烦。倘若有一种既能把八皇后的所在位置和把皇后所有情况连续输出,我感觉就应该算是一个完美的程序了,这还需要我一致的探索发掘下去才行。1.5.2运行与测试 (1)由于在编写代码时漏写了某个函数导致程序不能正常运行出现了错误提示;图1-1 错误警告(2)在同学帮助下成功的运行了该程序; 图1-2 成功运行(3)最后输出了最终八皇后问题的结果。 图1-3 输出八皇后结果 1.6 课设总结通过这次的课程设计,让我了解了八皇后这一经典的问题。同时让
13、我更好地掌握了栈思想以及一维数组等等知识,以及一些书本上没有的东西,这对我以后的学习生涯以及将来步入社会起到很大的帮助。这次课程设计虽然花了我很多时间和精力,但很值得,因为它对我能力提高起到很大帮助。这次课程设计也提醒我以前知识的匮乏,它给我敲响了警钟,让我意识到自己基础的不扎实.当然这次实验还是有很多问题的。比如程序设计的界面不够好,一些程序并非自己所写,而是修改某些程序而成,但这些不该,在下次课程设计时不会再发生.针对八皇后这个课题,也许表层只局限于对八个皇后的摆放,但还可以对更多的情况进行探讨分析,比如九皇后,十皇后等等。在报告正文中已经多次提到关于N皇后的设计方法,但只是一带而过,有些
14、问题很难通过一个报告设计就轻而易举的得到解决,还需要花费更多的时间。- 9 -经济管理学院本科课程设计论文第二章 n阶魔阵问题概述2.1课题的描述 n阶魔阵问题在我国古代被称作“纵横图”,其主要设计要求是对于给定的一个奇数n,构造一个n阶魔阵。n阶魔阵是一个n阶方阵,其元素由自然数1,2,3,n2组成。魔阵每一行元素之和,每一列元素之和,以及主,副对角线员素质和均相等。2.2 需求分析2.2.1 涉及到的知识 本次课程设计中,用到的主要知识有:二维数组的使用方法和一些基本的设计思路以及数据结构与数据存储的的有关知识。2.2.2 模块的功能需求 (1)void main()函数,主函数,调用以下
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
20 积分
下载 | 加入VIP,下载更划算! |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构课程设计 八皇后问题 数据结构 课程设计 皇后 问题