北邮数据结构试验报告 八皇后问题

《北邮数据结构试验报告 八皇后问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京邮电大学数据结构试验报告实验名称：实验二栈和队列学生姓名：班级：班内序号：学号：日期：2014年1月3日1实验目的Ø进一步掌握指针、模板类、异常处理的使用Ø掌握栈的操作的实现方法Ø掌握队列的操作的实现方法Ø学习使用栈解决实际问题的能力Ø学习使用队列解决实际问题的能力2实验内容2.2题目2利用栈结构实现八皇后问题。八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。3程序分析3.1 存储结构栈的存储结构：3.2 算法分析八皇后问题

2、可看成是0—7这八个数满足一定条件的排序1.判断某位置是否可用于摆放皇后boolcheck(intposition,intdata)//position表示行数，所以不会同行，检查是否存在有多个皇后在同一列/对角线的情况{inti;intj;for(i=0;i

3、eturntrue;}2.递归算法找出所有可能的排列voideight_queen(intposition)//安排第position行皇后所在的列数{intdata;//以data表示列数for(data=0;data<8;data++){if(check(position,data))//判断某位置是否可以放置皇后{EightQueens[position]=data;//放置第position行的皇后if(position==7)//直到完成一种组合{Count++;//完成一种摆法print();//打印此种摆法EightQueens[position]=0;//恢复到

4、原数组都为零的状态return;}eight_queen(position+1);//递归，安排第position+1行的列数EightQueens[position]=0;//恢复到原数组都为零的状态}}}3.打印函数voidprint()//以0—7排列组合形式输出每一种情况下棋盘中皇后的摆放情况{for(inti=0;i<8;i++){cout<

5、面的放置无论如何都不能满足要求”，以至于在设计递归算法总是只显示几种。2.心得体会这次实验让我更好地掌握了栈思想以及一维数组等等知识,以及一些书本上没有的东西，让我学会了运用递归算法去解决一些复杂的问题3.改进不仅可以设计放置八皇后，也可以是9皇后，10皇后，只要修改N完整源代码#includeusingnamespacestd;staticintEightQueens[8]={0},Count=0;voidprint();//输出每一种情况下棋盘中皇后的摆放情况boolcheck(intposition,intdata);//检查插入位置是否与之前插入的皇

6、后在同一列/对角线voideight_queen(intposition);intmain(){eight_queen(0);cout<<"可以的组合一共有："<

7、htQueens[i];if(j==data)returnfalse;//列数相同，错误if((position-i)==(data-j))returnfalse;//同一对角线，错误if((position-i)==(j-data))returnfalse;//同一对角线，错误}returntrue;}voideight_queen(intposition){intdata;for(data=0;data<8;data++){if(check(position,data)){EightQu