算法分析与设计

《算法分析与设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、--算法课程设计--《算法分析与设计》——课程设计任务书课程设计名称：八皇后问题班级：网络091姓名：马金凤学号：09174111--13----算法课程设计--概要：八皇后问题最早是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出。之后陆续有数学家对其进行研究，其中包括高斯和康托，并且将其推广为更一般的n皇后摆放问题。八皇后问题的第一个解是在1850年由弗朗兹·诺克给出的。诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一。1874年，S.冈德尔提出了一个通过行列式来求解的方法，这个方法后来又被J.W.L.格莱舍加以改进。艾兹格·迪杰斯特拉在1972年用

2、这个问题为例来说明他所谓结构性编程的能力2。八皇后问题出现在1990年代初期的著名电子游戏第七访客中。八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n=1或n≥4时问题有解。其中一种图解：--13----算法课程设计--关键词：八皇后；递归法；回溯法；数组；枚举法。任务内容：要求熟练运用C++语言、基本算法的基础知识，独

3、立编制一个具有中等难度的、解决实际应用问题的应用程序。通过对题意的分析与计算，用递归法回溯法及枚举法解决八皇后是比较适合的。递归是一种比较简单的且比较古老的算法。回溯法是递归法的升华，在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而枚举法，更是一种基础易懂简洁的方法。把它们综合起来，就构成了今天的算法。不论用什么法做这个课题，重要的就是先搞清楚哪个位置是合法的放皇后的位置，哪个不能，要先判断，后放置。设计目的：1.调研并熟悉八皇后的基本功能、数据流程与工作规程；2.学习八皇后相关的算法和基于VC++集成环境的编程技术；3.通过实际

4、编程加深对基础知识的理解，提高实践能力；4.学习开发资料的收集与整理，学会撰写课程设计报告。--13----算法课程设计--详细设计说明：A.问题描述：在一个８×８的棋盘里放置８个皇后，要求每个皇后两两之间不相"冲"（在每一横列竖列斜列只有一个皇后）。B.问题分析：这道题可以用递归循环来做，分别一一测试每一种摆法，直到得出正确的答案。主要解决以下几个问题：1、冲突。包括行、列、两条对角线：（1）列：规定每一列放一个皇后，不会造成列上的冲突；（2）行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；（3）对角线

5、：对角线有两个方向。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。2、数据结构。（1）解数组A。A[I]表示第I个皇后放置的列；范围：1..8（2）行冲突标记数组B。B[I]=0表示第I行空闲；B[I]=1表示第I行被占领；范围：1..8（3）对角线冲突标记数组C、D。C[I-J]=0表示第（I-J）条对角线空闲；C[I-J]=1表示第（I-J）条对角线被占领；范围：-7..7D[I+J]=0表示第（I+J）条对角线空闲；

6、D[I+J]=1表示第（I+J）条对角线被占领；范围：2..16C.算法流程：１、数据初始化。２、从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置(n,m)是否等于０（未被占领）:--13----算法课程设计--如果是，摆放第n个皇后，并宣布占领(记得要横列竖列斜列一起来哦)，接着进行递归；如果不是，测试下一个位置(n,m+1)，但是如果当n<=8,m=8时，却发现此时已经无法摆放时，便要进行回溯。３、当n>8时，便一一打印出结果。D.结构定义一个类结构classbahuanghou { inti; public: bah

7、uanghou(intx) { i=x; } voidsolve(int); }; 定义同一类型的对象，提供了可重用性的好处。除了实例变量和方法，类也可以定义类变量和类方法。可以从类的实例中或者直接从类中访问类变量和方法。类方法只能操作类变量-不必访问实例变量或实例方法。系统在第一次在程序中遇到一个类时为这个类建立它的所有类变量的拷贝-这个类的所有实例共享它的类变量。E.函数voidsolve(int);用于找出八皇后的最优值和最优解，并一一列出来。voidsolve(inti) {intj; for(j=1;j<9;j++) --13----算法课程设计-

8、-{ { LineNum[i]=j;a[j]=fal