大数据结构课程设计八皇后问题.doc

《大数据结构课程设计八皇后问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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模块的功能需求-10-2.2.3软硬件的需求-10-2.2.4面对的问题-10-2.3概要设计-11

2、-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-第一章八皇后问题概述1.1课题的描述八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的。八皇后问题是在8*8的国际象棋棋盘上，安放8皇后，要求没有一个皇后能够“吃掉”任何其他一个皇后，即没有两个或两个以上的皇后占据棋盘上的同一行、同一列、或同一对角线。到了现

3、代，随着计算机技术的飞速发展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上。运用所学计算机知识来试着解决这个问题是个锻炼和提高我自己编程能力和独立解决问题能力的好机会，可以使我增强信心，为我以后的编程开个好头，故我选择了这个有趣的课题。1.2需求分析1.2.1涉及到的知识本次课程设计中，用到的主要知识有：递归法的运用，for语句的灵活运用，数据结构中树知识的灵活运用、栈及数组的有关知识的掌握。要求熟练运用C++语言、基本算法的基础知识，独立编制一个具有中等难度的、解决实际应用问题的应用程序。通过对题意的分析与计算，用递归法回溯法及枚举法解决八皇后是比较适合的。递归是一种比较简单的且

4、比较古老的算法。回溯法是递归法的升华，在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而枚举法，更是一种基础易懂简洁的方法。把它们综合起来，就构成了今天的算法。不论用什么法做这个课题，重要的就是先搞清楚哪个位置是合法的放皇后的位置，哪个不能，要先判断，后放置。1.2.2模块的功能要求当运行程序时，在屏幕上显示每一种方法八个皇后的相对位置，要用比较直观的界面显示。列：规定每一列放一个皇后，不会造成列上的冲突；行：当第I行被某个皇后占领后，则同一行所不能再放皇后，要把以I为下标的标记置为被占领状态；对角线：对角线有两个方向。在这我把这两条对角线称为：主对角线和从对角线。在

5、同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。用数组a[I]：a[I]表示第I个皇后放置的列；I的围：1-8;对角线数组：b[j](主对角线),c[j]（从对角线），根据程序的运行，去决定主从对角线是否放入皇后。1.2.3软硬件的需求（1）系统要求：win98以上操作系统；（2）语言平台：tc++或vc++6.0；1.2.4面对的问题(1)列：规定每一列放一个皇后，不会造成列上的冲突；行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为

6、下标的标记置为被占领状态；对角线：对角线有两个方向。在这我把这两条对角线称为：主对角线和从对角线。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。（2）使用数据结构的知识，用递归法解决问：。数组a[I]：a[I]表示第I个皇后放置的列；I的围：1..8;对角线数组：b[j](主对角线),c[j]（从对角线），根据程序的运行，去决定主从对角线是否放入皇后；1.3概要设计1.3.1结构设计理念（1）从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求

7、），先测试当前位置（n，m）是否等于0（未被占领）。如果是，摆放第n个皇后，并宣布占领，接着进行递归；如果不是，测试下一个位置（n，m+1），但是如果当n<=8，m=8时，发现此时已无法摆放时，便要进行回溯。从问题的某一种可能出发，搜索从这种情况能出发，继续搜索，这种不断“回溯”的寻找解的方法，称为“回溯法”。（2）使用数组实现回溯法的思想。（3）当n>8时，便打印出结果。1.3.2算法流程图图1