《课程设计说明书NO.1》由会员分享，可在线阅读，更多相关《课程设计说明书NO.1（73页珍藏版）》请在金锄头文库上搜索。
1、课程设计说明书 NO.1八皇后问题八皇后问题一一 课程设计目的课程设计目的数据结构课程设计是计算机科学与技术专业集中实践性环节之一，本次课程设计是学习完数据结构课程后进行的一次全面的综合练习。其目的是：(1)要达到理论与实际应用相结合，能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。(2)在实践中认识为什么要学习数据结构，掌握数据结构、程序设计语言程序设计技术、软件工程、数据库技术之间的关系。通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。(3)通过对一
2、些实际问题的分析，加深理解，将课本的理论运用到实践中，提高独立思考和理解问题的能力，加强动手能力，增加学习心得。二二 需求分析需求分析2.12.1 问题描述问题描述设在初始状态下在国际象棋上没有任何棋子。然后顺序在第 1 行，第 2 行，第 8 行上布放棋子。在每一行中有 8 个可选择位置，但在任一时刻，棋盘的合法布局都必须满足 3 个限制条件：即任何两个棋子不得放在棋盘上的同一行、或者同一列、或者同一斜线上。2.2 基本要求基本要求用回溯法。在第 n 行第 j 列安放一个棋子时，需要记录在行方向、列方向、正斜线方向、反斜线方向的安放状态，若当前布局合法，可向下一行递规求解，否则可移走这个棋子
3、，回复安放此棋子前的状态，试探本行的 j1 列。3 概要设计概要设计3.1 基本思想基本思想沈 阳 大 学课程设计说明书 NO.2首先定义一个递归找全部解的递归函数 FindQueens(int i)，设有一个参数 i， 表示在 1 至 i-1 行都已有皇后合理放置的情况下，寻找第 i 行的合理放置。在 i 行上，有8 种可能的放置，列 iColumn 顺次选择第 1 列、第 2 列直至第 8 列。当 i 行iColumn 列的放置是合理的时候，就设置与 i 行 iColumn 列相对应的列、斜线有皇后的标志，并在 i=7(i 从 0 开始计算)的情况下，输出解；否则递归调用 FindQuee
4、ns(i+1)，在第 i+1 行上寻找合理的放置。一列试探结束，再试探下一列之前，清除已设置的与i 行 iColumn 列相对应的列、斜线有皇后的标志，让 iColumn 增加 1，在下一列寻找解。要关心的是一个皇后是否已经合理的沿着每一行、每一列的斜线安置。因此在每一列上恰好安置一个皇后，引入一个二维数组（设数组为 Queen ） ，QueeniiColumn表示在棋盘的第 i 行、第 iColumn 列方格上有一个皇后。另外，为了使程序在检查皇后放置的合理性方面简易方便，引入以下三个工作数组（k 仅代表其中一个元素）： 数组 a ，ak=1 表示第 k 列上有皇后； 数组 b ，bk=1
5、表示第 k 条主对角线上有皇后； 数组 c ，ck=1 表示第 k 条反对角线上有皇后；棋盘中的行与列有如下规律：同一条主对角线上的方格，它们的行号与列号之间的关系：i-iColumn+7 均相等；同一条反对角线上的方格，它们的行号与列号之间的关系：i+iColumn 均相等。初始化时，所有行和斜线上均没有皇后。在第 i 行的 iColumn 列方格放置一个合理的皇后后，准备考察第 i+1 行时,应在数组 a ，b ，c 中为第 i 行、第 iColumn 列的方格设定有皇后的标志；如果前次的皇后放置导致后面的放置无论如何都不能满足要求，则回溯，重置，这时，应先清除原先在数组 a ，b ，c
6、中设置的关于第 i 行、第 iColumn 列有皇后的标志；一个皇后在第 i 行、第 iColumn 列方格内放置是合理的，由数组 a ，b ，c 对应位置都没有皇后来确定。沈 阳 大 学课程设计说明书 NO.33.2 递归算法递归算法递归查找全部解的算法描述如下：void FindQueens(int i)for(iColumn=0;iColumnjudge;coutnum;cout92-iQueenNum)cout=92)cout 92-iQueenNum调用函数 choose()退 出case3 case2case1 defaultcase4exit结 束NY沈 阳 大 学课程设计说明书
7、 NO.106.3 函数函数 FindQueens()沈 阳 大 学进 入iColumniColumn+iColumn using namespace std; static char Queen88;/标记皇后 static int a8;/标记列 static int b15;/标记主对角钱 static int c15;/标记反对角钱 static int iQueenNum=0; /记录总的棋盘状态数 char judge;/用户选择的判断 int num;/第 3 项操作的计数 void choose(void); /用户选择操作 void FindQueens(int i); /八
8、皇后递归求解，参数 i 代表行 void display(void); int main() int iLine,iColumn;coutjudge;coutnum;cout92-iQueenNum)cout=92)coutendl“演示结束，请按任意键退出。 “endlendl;exit(0);coutendl“请选择下一步操作“endl; choose(); break;default:break; 沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大
9、学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.
10、沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳 大 学课程设计说明书 NO.沈 阳
