算法分析与设计.doc

-算法课程设计-算法分析与设计课程设计任务书 课程设计名称：八皇后问题班级：网络091姓名：马金凤学号：09174111概要：八皇后问题最早是由国际西洋棋棋手马克斯贝瑟尔于1848年提出。之后陆续有数学家对其进行研究，其中包括高斯和康托，并且将其推广为更一般的n皇后摆放问题。八皇后问题的第一个解是在1850年由弗朗兹诺克给出的。诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一。1874年，S.冈德尔提出了一个通过行列式来求解的方法，这个方法后来又被J.W.L.格莱舍加以改进。艾兹格迪杰斯特拉在1972年用这个问题为例来说明他所谓结构性编程的能力2。八皇后问题出现在1990年代初期的著名电子游戏第七访客中。八皇后问题是一个以国际象棋为背景的问题：如何能够在 88 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为nn，而皇后个数也变成n。当且仅当 n = 1 或 n 4 时问题有解。其中一种图解： 关键词：八皇后；递归法；回溯法；数组；枚举法。任务内容：要求熟练运用C+语言、基本算法的基础知识，独立编制一个具有中等难度的、解决实际应用问题的应用程序。通过对题意的分析与计算，用递归法回溯法及枚举法解决八皇后是比较适合的。递归是一种比较简单的且比较古老的算法。回溯法是递归法的升华，在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而枚举法，更是一种基础易懂简洁的方法。把它们综合起来，就构成了今天的算法。不论用什么法做这个课题，重要的就是先搞清楚哪个位置是合法的放皇后的位置，哪个不能，要先判断，后放置。设计目的：1. 调研并熟悉八皇后的基本功能、数据流程与工作规程；2. 学习八皇后相关的算法和基于VC+集成环境的编程技术；3. 通过实际编程加深对基础知识的理解，提高实践能力；4. 学习开发资料的收集与整理，学会撰写课程设计报告。详细设计说明：A.问题描述：在一个的棋盘里放置个皇后，要求每个皇后两两之间不相冲（在每一横列竖列斜列只有一个皇后）。B.问题分析：这道题可以用递归循环来做，分别一一测试每一种摆法，直到得出正确的答案。主要解决以下几个问题：1、冲突。包括行、列、两条对角线：（1）列：规定每一列放一个皇后，不会造成列上的冲突；（2）行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；（3）对角线：对角线有两个方向。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。2、数据结构。（1）解数组A。AI表示第I个皇后放置的列；范围：1.8（2）行冲突标记数组B。BI=0表示第I行空闲；BI=1表示第I行被占领；范围：1.8（3）对角线冲突标记数组C、D。CI-J=0表示第（I-J）条对角线空闲；CI-J=1表示第（I-J）条对角线被占领；范围：-7.7DI+J=0表示第（I+J）条对角线空闲；DI+J=1表示第（I+J）条对角线被占领；范围：2.16 C.算法流程：、数据初始化。、从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置(n,m)是否等于（未被占领）:如果是，摆放第n个皇后，并宣布占领(记得要横列竖列斜列一起来哦)，接着进行递归；如果不是，测试下一个位置(n,m+1)，但是如果当n8时，便一一打印出结果。D.结构定义一个类结构class bahuanghou int i; public: bahuanghou(int x) i=x; void solve(int);定义同一类型的对象，提供了可重用性的好处。除了实例变量和方法，类也可以定义类变量和类方法。可以从类的实例中或者直接从类中访问类变量和方法。类方法只能操作类变量 - 不必访问实例变量或实例方法。系统在第一次在程序中遇到一个类时为这个类建立它的所有类变量的拷贝 - 这个类的所有实例共享它的类变量。E. 函数void solve(int);用于找出八皇后的最优值和最优解，并一一列出来。void solve(int i) int j;for(j=1;j8) num+; for(int m=1; m9; m+) for(int n=1; n9; n+)if(LineNumm = n)cout Q;elsecout +;coutendl;for( m=1; m9; m+)for(int n=1; n9; n+)if(LineNumm = n)cout(m,n)t;coutendl; / system(pause); F.主要用到下列算法：递归法：递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。递归算法解决问题的特点： (1) 递归就是在过程或函数里调用自身。 (2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。 (3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。 (4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。递归算法PlaceQueue,完成这样的功能：它寻找第col列后的皇后的安全摆放位置，如果该函数返回了false,表示当前进入了死胡同，需要进行回溯，直到为0-7列都找到了安全位置或者找遍这些列都找不到安全位置的时候终止。回溯法：回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。一般表达可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x1，x2，xn）组成的一个状态空间E=（x1，x2，xn）xiSi ，i=1，2，n，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域，且 |Si| 有限，i=1，2，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。 解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但显然，其计算量是相当大的。枚举法：在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么这结论是可靠的，这种归纳方法叫做枚举法特点：将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，合适就保留，不合适就丢弃。例如： 找出1到100之间的素数。需要将1到100之间的所有整数进行判断。 枚举算法因为要列举问题的所有可能的答案，所有它具备以下几个特点： 1、得到的结果肯定是正确的； 2、可能做了很多的无用功，浪费了宝贵的时间，效率低下。 3、通常会涉及到求极值（如最大，最小，最重等）。 4、数据量大的话，可能会造成时间崩溃。软件使用说明：软件：Visual C+使用说明：打开visual c+，新建一个工程WIN32 Console Application，输入新建工程的名字，在新建一个文件C/C+ ,输入文件的名字，进入工作区后，输入代码，然后开始组建，编译，如果不能成功，则修改内容，直到编译成功，然后执行程序。执行的结果如下：心得与体会：利用递归，回溯法可以解决很多看起来很困难的问题，比起另外的语句要节约很多的时间，在编程的过程中会遇到很多的问题，但只要耐心，都能一一解答，在这期间，网络发挥这很重要的作用，在编程的过程中我发现，善于利用我们课堂中学过的很多算法可以很轻松的解决生活中的很多问题，所以我们要好好的掌握每种算法的思想，以便于我们在以后的日子可以很好的工作！在编程的过程中，会遇到很多的小问题，比如说标点符号的全角与半角，括号等等都能造成程序的不能运行，所以在编程的过程中一定要很仔细！附录1：参考文献计算机算法设计与分析面对程序设计语言附录2：全部源程序清单# include #include int LineNum9; /第i列的皇后要放的行位置（只用其中的列号1到8）bool a9; /ai为1表示第i行上尚未放皇后bool b15; /bi为1表示第i条斜对角线上尚未放皇后（斜对角线指的是/状对角线，该对角线上各点的行列号之和i+j为一个常数）bool c15; /ci为1表示第i条反斜对角线上尚未放皇后（反斜对角线指的是状对角线，该对角线上各点的行列号之差i-j为一个常数）。int num=0; /计数器，用于计算方法总数 class bahuanghou int i; public: bahuanghou(int x) i=x; void solve(int); void bahuanghou:solve(int i)int j;for(j=1;j8) /摆放皇后之后，若i=8即已放满时则递归出口；否则通过solve(i+1);进行递归调用。 num+; for(int m=1; m9; m+)for(int n=1; n9; n+)if(LineNumm = n)cout Q;elsecout +;coutendl; for( m=1; m9; m+)for(int n=1; n9; n+)if(LineNumm = n)cout(m,