八皇后问题实验报告递归非递归javaC语言+分析.doc
《八皇后问题实验报告递归非递归javaC语言+分析.doc》由会员分享,可在线阅读,更多相关《八皇后问题实验报告递归非递归javaC语言+分析.doc(41页珍藏版)》请在咨信网上搜索。
1、- .数据构造课程设计题目:八皇后问题 指导教师:* 学生院系: 数学学院 学生班级:信计*班 学生XX:黎*文 学生学号: 14070204*2016年12月30日目录一.功能以及需求分析31.1 问题的由来和背景31.2 问题的根本解决思路31.3 问题的应用3二.总体设计42.1 运行环境42.2 程序框架42.3 算法分析42.3.1 总体算法分析42.3.2 非递归算法分析62.3.3 递归算法的分析6三.详细设计63.1 递归法的详细设计63.2 非递归法的详细设计7四.具体实现及运行104.1 QueenMainl类的实现:104.2 QueenNR类:104.3 QueenRS
2、类:114.4 C语言程序:11五. 总结12六.代码清单136.1 Java代码:136.2 C语言源代码:20一.功能以及需求分析1.1 问题的由来和背景八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯贝瑟尔于1848年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。计算机创造后,有多种计算机语言可以解决此问题。八皇后问题是一个以国际象棋为背景的问题:如何
3、能够在 88 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了到达此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为nn,而皇后个数也变成n。当且仅当 n = 1 或 n 4 时问题有解。1.2 问题的根本解决思路 八皇后问题最早是由国际西洋棋棋手马克斯贝瑟尔于1848年提出。之后陆续有数学家对其进展研究,其中包括高斯和康托,并且将其推广为更一般的n皇后摆放问题。八皇后问题的第一个解是在1850年由弗朗兹诺克给出的。诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一。1874年,S.冈德尔提出了一
4、个通过行列式来求解的方法。 八皇后问题出现在1990年代初期的著名电子游戏第七访客中。设置一个三维数组,第一个下标是皇后的行坐标,第二个下标是皇后的列坐标,第三个下标是残卷号。相当于有N叠在一起的8*8棋盘,每棋盘只在复制前面棋盘及皇后后加放置一个皇后。直到放满8皇后后才是一完整的8皇后图,称完卷。这里实际操作时多加一行多加一列即第0行第0列,但这一行/列不作输出,只是作此行/列有无皇后的参考。 总的来说现在解八皇后问题的总体算法都是采用回溯法,也叫作穷搜法,再穷搜的时候去掉分支,减少不必要的运算,对于八皇后问题的求解,一般只能做出15皇后问题,有局部算法高手在有精良设备的情况下算出了25皇后
5、的解。受算法和硬件计算能力的影响,因为计算量为O(n!),而且回溯法使用的存空间特别大,所以此问题的求解还有很多可以探究的地方,尤其是算法上的改良。1.3 问题的应用八皇后问题可以用来解决地图的着色问题,以及迷宫的求解问题,同时,八皇后问题是一个典型的回溯法求解问题,可以用它来类比很多和回溯法有关的问题。对于现在的DNA序列问题也可以从中得到启发。二.总体设计2.1 运行环境 1编译环境:JDK 1.8 ,以及eclipse ,Mars 4.5.2,Visual C+ 6.0 2电脑系统: Windows server 2003 32位 3编译语言:Java,C语言2.2 程序框架 1Main
6、Queen:实现可视化界面,可以选择递归和非递归两种算法得到八皇后问题的解,并将答案打印出来。 2QueenNR:采用非递归方法求解问题。 3QueenRS: 采用递归方法求解问题。 4编译C语言程序。2.3 算法分析2.3.1 总体算法分析算法的核心是回溯法,也称为试探法,它并不考虑问题规模的大小,而是从问题的最明显的最小规模开场逐步求解出可能的答案,并以此慢慢地扩大问题规模,迭代地逼近最终问题的解。这种迭代类似于穷举并且是试探性的,因为当目前的可能答案被测试出不可能可以获得最终解时,那么撤销当前的这一步求解过程,回溯到上一步寻找其他求解路径。为了能够撤销当前的求解过程,必须保存上一步以来的
7、求解路径。当撤销之后满足条件,就一直做下去,直到试探完所有的可能解。 总结如下:(1)设置初始化的方案给变量赋初值,读入数据等。(2)变换方式去试探,假设全部试完那么转(7)。(3)判断此法是否成功通过约束函数,不成功那么转(2)。(4)试探成功那么前进一步再试探。(5)正确方案还未找到那么转(2)。(6)已找到一种方案那么记录并打印。(7)退回一步回溯,假设未退到头那么转(2)。(8)已退到头那么完毕或打印无解 另外一个关键就是对于每一个局部解的判定,可归纳问题的条件为: 1.不在同一行列上 2.不在同一斜线上 3.不在同一反斜线上 具体到八皇后的问题,我们可以逐行或者逐列来进展可行摆放方案
8、的遍历,每一行或列遍历出一个符合条件的位置,接着就到下一行或列遍历下一个棋子的适宜位置,这种遍历思路可以保证我们遍历过程中有一个条件是绝对符合的就是下一个棋子的摆放位置与前面的棋子不在同一行或列。接下来,我们只要判断当前位置是否还符合其他条件,如果符合,就遍历下一行或列所有位置,看看是否继续有符合条件的位置,以此类推,如果某一个行或列的所有位置都不适宜,就返回上一行或列继续该行或列的其他位置遍历,当我们顺利遍历到最后一行或列,且有符合条件的位置时,就是一个可行的8皇后摆放方案,累加一次八皇后可行方案的个数,然后继续遍历该行其他位置是否有适宜的,如果没有,那么返回上一行,遍历该行其他位置,依此下
9、去。这样一个过程下来,我们就可以得出所有符合条件的8皇后摆放方案了。这是一个深度优先遍历的过程,同时也是经典的递归思路。 接下来,我们以逐列遍历,具体到代码,进一步说明。首先,从第一列开场找第一颗棋子的适宜位置,我们知道,此时第一列的任何一个位置都是适宜的,当棋子找到第一个适宜的位置后,就开场到下一列考虑下一个适宜的位置,此时,第二列的第一行及第二行显然就不能放第二颗棋子了,因为其与第一个棋子一个同在一行,一个同在一条斜线上。第二列第三行成为第二列第一个适宜的位置,以此类推,第三列的第5行又会是一个适宜位置,这个过程中,我们注意到,每一列的适宜位置都是受到前面几列的位置所影响,归纳如下: 假设
10、前面1列的棋子放在第3行,那当前列不能放的位置就一定是3行,2行,4行。因为如果放在这三行上就分别跟前一列的棋子同在一行、同在斜线、同在反斜线上,不符合我们的要求。现在我们用cols数组来表示8个列棋子所放的行数,数组下标从0开场,其中数组下标表示列数,数组的元素值表示该列棋子所在行数,当前列为NN=0,N=0,m=0 ,与第m列的棋子不在同一斜线上) colsN != colsm + (N-m) (=8-1,与第m列的棋子不在同一反斜线上) 为了使此程序能够解决N皇后的问题,一般将参数改成N,已解决N皇后的问题,当然,这还和计算机性能和算法差异有关,此程序一般能解决到15皇后的问题。在Jav
11、a程序中以实现N皇后问题。2.3.2 非递归算法分析 程序首先对N行中的每一行进展探测,寻找该行中可以放置皇后的位置,具体方法是对该行的每一列进展探测,看是否可以放置皇后,如果可以,那么在该列放置一个皇后,然后继续探测下一行的皇后位置。如果已经探测完所有的列都没有找到可以放置皇后的列,此时就应该回溯,把上一行皇后的位置往后移一列,如果上一行皇后移动后也找不到位置,那么继续回溯直至某一行找到皇后的位置或回溯到第一行,如果第一行皇后也无法找到可以放置皇后的位置,那么说明已经找到所有的解程序终止。如果该行已经是最后一行,那么探测完该行后,如果找到放置皇后的位置,那么说明找到一个结果,打印出来。但是此
12、时并不能再此处完毕程序,因为我们要找的是所有N皇后问题所有的解,此时应该去除该行的皇后,从当前放置皇后列数的下一列继续探测。2.3.3 递归算法的分析 第1次考虑把皇后放在第1行的某个位置, 第2次放的时候就不用去放在第一行了,因为这样放皇后间是可以互相攻击的。 第2次我就考虑把皇后放在第2行的某个位置,第3次我考虑把皇后放在第3行的某个位置, 这样依次去递归。每计算1行,递归一次,每次递归里面考虑8列, 即对每一行皇后有8个可能的位置可以放。找到一个与前面行的皇后都不会互相攻击的位置, 然后再递归进入下一行。找到一组可行解即可输出,然后程序回溯去找下一组可靠解。 用一个一维数组来表示相应行对
13、应的列,比方colsi=j表示, 第i行的皇后放在第j列。如果当前行是r,皇后放在哪一列呢?colsr列。 一共有8列,所以我们要让colsr依次取第0列,第1列,第2列一直到第7列, 每取一次我们就去考虑,皇后放的位置会不会和前面已经放了的皇后有冲突。 怎样是有冲突呢?同行,同列,对角线。由于已经不会同行了,所以不用考虑这一点。 只有满足了当前皇后和前面所有的皇后都不会互相攻击的时候,才能进入下一级递归。三.详细设计3.1 递归法的详细设计 1 定义一个cols数组,存储八皇后问题中每一列j对应放置的皇后的位置i。 2 定义getArrangement(int n) 递归函数,其中定义一个b
14、oolean型 rows数组,记录每一行能够正常放置的位置,如果能放置,设置为true,默认为null。函数中,先找出每列适宜的的第一个位置。然后判断是不是最后一列,是最后一列就输出,不是就进入递归。如果该列没找到一个适宜的位置,跳出此次递归,进入上一次递归。具体函数如下: public void getArrangement(int n)/遍历该列所有不合法的行,并用rows数组记录,不合法即rowsi=true boolean rows = new booleanMAXQUEEN; /判断该点是不是合法 ,如果有合法的,不赋值为 null for(int i=0;i= 0) rowscol
15、si-d=true; if(colsi+d = MAXQUEEN-1) rowscolsi+d=true; for(int i=0;iMAXQUEEN;i+) /判断该行是否合法 合法就跳出 选出第一个可以添加的行 if(rowsi)continue; colsn = i; /设置当前列合法棋子所在行数 if(nMAXQUEEN-1) /当前列不为最后一列时 getArrangement(n+1); else num+; /累计方案个数 printChessBoard();/打印棋盘信息 3定义输出函数public void printChessBoard(),输出函数比拟简单,利用全部赋值之
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 皇后 问题 实验 报告 递归 javaC 语言 分析
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【二***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【二***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。