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

北京邮电大学数据结构试验报告实验名称： 实验二 栈和队列学生姓名： 班 级： 班内序号： 学 号： 日 期： 2014年1月3日1 实验目的 进一步掌握指针、模板类、异常处理的使用 掌握栈的操作的实现方法 掌握队列的操作的实现方法 学习使用栈解决实际问题的能力 学习使用队列解决实际问题的能力2 实验内容2.2题目2 利用栈结构实现八皇后问题。 八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。3 程序分析3.1存储结构栈的存储结构：3.2算法分析八皇后问题可看成是07这八个数满足一定条件的排序1. 判断某位置是否可用于摆放皇后bool check(int position,int data)/position表示行数，所以不会同行，检查是否存在有多个皇后在同一列/对角线的情况int i;int j;for(i=0;iposition;i+)j=EightQueensi;if(j=data) return false; /列数相同，错误if(position-i)=(data-j) return false; /同一对角线，错误if(position-i)=(j-data) return false; /同一对角线，错误return true;2.递归算法找出所有可能的排列void eight_queen(int position)/安排第position行皇后所在的列数 int data;/以data表示列数 for(data=0;data8;data+) if(check(position,data)/判断某位置是否可以放置皇后 EightQueensposition=data;/放置第position行的皇后 if(position=7) /直到完成一种组合 Count+;/完成一种摆法 print();/打印此种摆法 EightQueensposition=0;/恢复到原数组都为零的状态 return; eight_queen(position+1); /递归，安排第position+1行的列数 EightQueensposition=0;/恢复到原数组都为零的状态 3. 打印函数void print()/以07排列组合形式输出每一种情况下棋盘中皇后的摆放情况for(int i=0;i8;i+)coutEightQueensi ;coutendl;4 程序运行结果4.1主函数流程图4.2程序运行框图5 实验心得1. 调试时出现的问题 在解决问题之初未能将八皇后问题的具体思路搞清，没有考虑“如果前次的皇后放置错误导致后面的放置无论如何都不能满足要求”，以至于在设计递归算法总是只显示几种。2. 心得体会 这次实验让我更好地掌握了栈思想以及一维数组等等知识,以及一些书本上没有的东西，让我学会了运用递归算法去解决一些复杂的问题 3. 改进不仅可以设计放置八皇后，也可以是9皇后，10皇后，只要修改N完整源代码 #includeusing namespace std;static int EightQueens8=0,Count=0;void print();/输出每一种情况下棋盘中皇后的摆放情况bool check(int position,int data);/检查插入位置是否与之前插入的皇后在同一列/对角线void eight_queen(int position);int main()eight_queen(0);cout可以的组合一共有：Count种endl;return 0;void print()/输出每一种情况下棋盘中皇后的摆放情况for(int i=0;i8;i+)coutEightQueensi ;coutendl; bool check(int position,int data)/检查是否存在有多个皇后在同一列/对角线的情况int i;int j;for(i=0;iposition;i+)j=EightQueensi;if(j=data) return false; /列数相同，错误if(position-i)=(data-j) return false; /同一对角线，错误if(position-i)=(j-data) return false; /同一对角线，错误return true; void eight_queen(int position) int data; for(data=0;data8;data+) if(check(position,data) EightQueensposition=data; if(position=7) /直到完成