n皇后问题MFC人机界面程序流程图.ppt_第1页
n皇后问题MFC人机界面程序流程图.ppt_第2页
n皇后问题MFC人机界面程序流程图.ppt_第3页
n皇后问题MFC人机界面程序流程图.ppt_第4页
n皇后问题MFC人机界面程序流程图.ppt_第5页
已阅读5页，还剩11页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

皇 后 问 题 小组成员 陈华鑫 黄燕舞 刘建福 王志兴 贾卓 商贵宝 郭云梅 林岩 八皇后问题是一个古老而著名的问题 它是回溯算法的典型例题 该问题是十九世纪德国著名数学家高斯于1850年提出的 在8行8列的国际象棋棋盘上摆放着八个皇后 使他们之间不能互相攻击 若两个皇后位于同一行 同一列或同一对角线上 则它们之间就可以互相攻击 后来人们从8皇后问题延伸到了n皇后问题 问题背景 一 在一个n n的棋盘中放置最多的皇后 使这些皇后互相之间无法攻击对方 二 求出在n n的棋盘中总共有多少种符合要求放置皇后的方法 最 终 目的 问题求解与博弈 由于每行 每列最多只能放置一个皇后 所以 在n n的棋盘上最多只能放置n个皇后 由于每行只能放置一个皇后 我们不妨从第一列开始放置皇后 从第二列开始依次判断所要放置皇后之前所在的行 列 对角线上是否存在皇后 总 体 思 路 我们选择使用回溯法即经典的递归法来求解n皇后问题 这个算法将在棋盘上一列一列地摆放皇后直到n个皇后在不相互攻击的情况下都被摆放在棋盘上 算法便终止 当一个新加入的皇后因为与已经存在的皇后之间相互攻击而不能被摆在棋盘上时 算法便发生回溯 一旦发生这种情况 就试图把最后放在棋盘上的皇后移动到其他地方 这样做是为了让新加入的皇后能够在不与其它皇后相互攻击的情况下被摆放在棋盘的适当位置上 方案制定 例如图中所示的情况 尽管第7个皇后不会与已经放在棋盘上的任何一皇后放生攻击 但仍然需要将它移除并发生回溯 因为无法为第8个皇后在棋盘上找到合适的位置 算法的回溯部分将尝试移动第7个皇后到第7列的另外一个位置来为第8个皇后在第8列寻找一个合适的位置 如果第7个皇后由于在第7列找不到合适的位置而无法被移动 那么算法就必须去掉它然后回溯到第6列的皇后 最终算法不断重复着摆放皇后和回溯的过程直到找到问题的解为止 总体流程图 类及其实现 在本程序中主要的是两个类即CEightQueenDlg和QueenPanel 在下面表格中给出了这两个类的相关成员变量和函数 表一是CEightQueenDlg类的相关成员变量
人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论