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

目 录 第一章 八皇后问题概述 - 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.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皇后，要求没有一个皇后能够“吃掉”任何其他一个皇后，即没有两个或两个以上的皇后占据棋盘上的同一行、 同一列、或同一对角线。 到了现代，随着计算机技术的飞速发展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上。运用所学计算机知识来试着解决这个问题是个锻炼和提高我自己编程能力和独立解决问题能力的好机会，可以使我增强信心，为我以后的编程开个好头，故我选择了这个有趣的课题。 1.2 需求分析 1.2.1 涉及到的知识 本次课程设计中，用到的主要知识有：递归法的运用，for语句的灵活运用，数据结构中树知识的灵活运用、栈及数组的有关知识的掌握。 要求熟练运用C++语言、基本算法的基础知识，独立编制一个具有中等难度的、解决实际应用问题的应用程序。通过对题意的分析与计算，用递归法回溯法及枚举法解决八皇后是比较适合的。递归是一种比较简单的且比较古老的算法。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被有哪些信誉好的足球投注网站遍才结束。。 序图1-1 1.4详细设计和实现 #include conio.h #include math.h #include stdlib.h #include stdio.h #include iostream.h #define QUEENS 8 int iCount = 0; //!记录解的序号的全局变量。 int Site[QUEENS]; //!记录皇后在各行上的放置位置的全局数组。 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(int n) /*-----------------Queen：递归放置第n个皇后，程序的核心!----------------*/ { int i; if(n == QUEENS) //!参数n从0开始，等于8时便试出了一个解，将它输出并回溯。 { Output(); return; } for(i = 1 ; i = QUEENS ; i++) //!n还没到8，在第n行的各个行上依次试探。 { Site[n] = i; //!在该行的第i行上放置皇后。