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

c++编程 八皇后问题 实验报告

XX级数据结构实验报告

实验名称： 实验二——栈和队列

学生姓名：

班 级：

班内序号：

学 号：

日 期：

1．实验要求

【实验目的】

1、 进一步掌握指针、模板类、异常处理的使用

2、 掌握栈的操作的实现方法

3、 掌握队列的操作的实现方法

4、 学习使用栈解决实际问题的能力

5、 学习使用队列解决实际问题的能力

【实验内容】

利用栈结构实现八皇后问题。

八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。

提示：

1、可以使用递归或非递归两种方法实现

2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上

2. 程序分析

2.1 存储结构

存储结构：栈（递归）

c++编程 八皇后问题 实验报告

2.2 关键算法分析

【设计思想】

由于八皇后问题，可以分解成算法相同的子问题，所以使用递归的方法

【伪代码】

1、 输入皇后个数n

2、 k=1

3、 判断k是否大于n

3.1 是：打印一组可能

3.2 否：循环行位置1~n

判断该位置是否符合要求，若符合记录q[k]的坐标y值

k+1 重复3

【关键算法】

1、递归

void Queen::Queens(int k,int n)//计算出皇后的排列，k是当前皇后数量，n是数量上限

{ int i;

if(k>n)//如果达到里要求的数量输出皇后排列

{ Print(n);

count();

}

else //否则在适当的位置添加一个新皇后

{

for(i=1;i<=n;i++)

if(Check(i,k)) //判断该行中该位置放置'皇后'是否符合要求

{

q[k]=i; //记录改行中该点的位置

Queens(k+1,n); //放置下一行的'皇后'

}

}

}

c++编程 八皇后问题 实验报告

时间复杂度：O(n²)

2、判断皇后放置位置是否符合要求

int Queen::Check(int i,int k)

{

} int j; j=1; while(j<k) { } return 1; //符合返回 if((q[j]==i) || abs(q[j]-i)==abs(j-k)) //判断列，判断斜线 j++; return 0; //不符合返回0

2.3 其他

源代码：

时间复杂度：O(n)

#include<iostream>

#include<cmath>

using namespace std;

#define N 10

class Queen

{

public:

Queen(){num=-1;} void Print(int n);//输出皇后的排列，打出的数字为每个皇后的坐标 int Check(int i,int k);//判断位置是否符合要求 void Queens(int k,int n);//递归调用 int count();//计数

c++编程 八皇后问题 实验报告

private:

};

void main()

{

}

void Queen::Queens(int k,int n)//计算出皇后的排列，k是当前皇后数量，n是数量上限 { int i;

if(k>n)//如果达到里要求的数量输出皇后排列 { Print(n); } else //否则在适当的位置添加一个新皇后 { for(i=1;i<=n;i++) if(Check(i,k)) //判断该行中该位置放置'皇后'是否符合要求 { count(); Queen Q; int n; cout<<"请输入Queen的数目(n>0):"<<endl; cin>>n; if(n>0) { } else cout<<"ERROR输入数字错误"<<endl; cout<<"Queen可能的位置坐标:"<<endl; Q.Queens(1,n); cout<<"共有 "<<Q.count()<<" 种方法放置Queen"<<endl; int q[N]; int num;

c++编程 八皇后问题 实验报告

} } } q[k]=i; //记录改行中该点的位置 Queens(k+1,n); //放置下一行的'皇后'

void Queen::Print(int n) {

}

int Queen::Check(int i,int k) {

}

int Queen::count() {

} num++; return num; int j; j=1; while(j<k) { } return 1; //符合返回 if((q[j]==i) || abs(q[j]-i)==abs(j-k)) //判断列，判断斜线 j++; return 0; //不符合返回0 int i; for(i=1;i<=n;i++) cout<<"("<<i<<","<<q[i]<<")"; cout<<endl;

c++编程 八皇后问题 实验报告

3. 程序运行结果

（1）测试主函数流程

（2）测试条件 n取值大于0小于10 本题中一般取n=8

（3）测试结论 测试正常，如图

c++编程 八皇后问题 实验报告

c++编程 八皇后问题 实验报告

4. 总结