c++利用栈解决八皇后问题-数据结构实验报告

XX级数据结构实验报告实验名称：实验二——栈和队列学生姓名：班级：班内序号：学号：日期：1．实验要求【实验目的】进一步掌握指针、模板类、异常处理的使用掌握栈的操作的实现方法掌握队列的操作的实现方法学习使用栈解决实际问题的能力学习使用队列解决实际问题的能力【实验内容】利用栈结构实现八皇后问题。八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。提示：1、可以使用递归或非递归两种方法实现2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2.程序分析2.1存储结构存储结构：栈（递归）2.2关键算法分析【设计思想】由于八皇后问题，可以分解成算法相同的子问题，所以使用递归的方法【伪代码】输入皇后个数nk=1判断k是否大于n3.1是：打印一组可能3.2否：循环行位置1~n判断该位置是否符合要求，若符合记录q[k]的坐标y值k+1重复3【关键算法】1、递归voidQueen::Queens(intk,intn)//计算出皇后的排列，k是当前皇后数量，n是数量上限{inti; if(k>n)//如果达到里要求的数量输出皇后排列 {Print(n); count(); } else//否则在适当的位置添加一个新皇后 { for(i=1;i<=n;i++) if(Check(i,k))//判断该行中该位置放置'皇后'是否符合要求 { q[k]=i;//记录改行中该点的位置 Queens(k+1,n);//放置下一行的'皇后' } }}时间复杂度：O(n²)2、判断皇后放置位置是否符合要求intQueen::Check(inti,intk){ intj; j=1; while(j<k) { if((q[j]==i)||abs(q[j]-i)==abs(j-k))//判断列，判断斜线 return0;//不符合返回0 j++; } return1;//符合返回}2.3其他源代码：时间复杂度：O(n)#include<iostream>#include<cmath>usingnamespacestd;#defineN10classQueen{public: Queen(){num=-1;} voidPrint(intn);//输出皇后的排列，打出的数字为每个皇后的坐标 intCheck(inti,intk);//判断位置是否符合要求 voidQueens(intk,intn);//递归调用 intcount();//计数private: intq[N]; intnum;};voidmain(){ QueenQ; intn; cout<<"请输入Queen的数目(n>0):"<<endl; cin>>n; if(n>0) { cout<<"Queen可能的位置坐标:"<<endl; Q.Queens(1,n); cout<<"共有"<<Q.count()<<"种方法放置Queen"<<endl; } else cout<<"ERROR输入数字错误"<<endl;}voidQueen::Queens(intk,intn)//计算出皇后的排列，k是当前皇后数量，n是数量上限{inti; if(k>n)//如果达到里要求的数量输出皇后排列 {Print(n); count(); } else//否则在适当的位置添加一个新皇后 { for(i=1;i<=n;i++) if(Check(i,k))//判断该行中该位置放置'皇后'是否符合要求 { q[k]=i;//记录改行中该点的位置 Queens(k+1,n);//放置下一行的'皇后' } }}voidQueen::Print(intn){ inti; for(i=1;i<=n;i++) cout<<"("<<i<<","<<q[i]<<")"; cout<<endl;}intQueen::Check(inti,intk){ intj; j=1; while(j<k) { if((q[j]==i)||abs(q[j]-i)==abs(j-k))//判断列，判断斜线 return0;//不符合返回0 j++; } return1;//符合返回}intQueen::count(){ num++; returnnum;}3.程序运行结