实验6_迭代实现_物联1301班_刘悦_201308080112

1、算法分析与设计实验报告第 6 次实验姓名刘悦学号201308080112班级物联1301班时间12.12上午地点工训楼C栋309 实验名称回溯法实验(八皇后问题)实验目的1) 掌握回溯法求解问题的思想。2) 学会利用其原理求解相关问题。实验原理使用迭代实现回溯法。从第一行开始放置皇后，第一行从第一列开始放置。之后放置第二行，与已放置的皇后冲突的位置不再考虑。之后再放置后面行的皇后，一旦某一行无位置可放，就退回到上一行，选择后面的其他位置进行放置。之后再重复上面的过程。一旦到达最后一行，就求得了解，记录这个时候的放置的信息。实验步骤 放置第一行的皇后。 放置后面行的皇后，与已放置的皇后在同一直线

2、、横线、斜线的位置不能放置。 放置后面的皇后。一旦某一行无位置可放，就返回到上面一行，选择其他位置放置皇后。 一旦到达最后一行，意味着找到了一个可行解，就记录这个放置方案。 重复过程，直至找到所有可能的放置解。关键代码/*=定义Queen类来存储皇后的信息。 =*/class Queenfriend int nQueen(int);private:bool Place(int k);void Backtrack(void);int n;/皇后个数 int *x;/当前解 long sum;/当前已找到的可行方案数 ;/*=Place函数进行可行性约束。若当前的位置已经与之前放置的皇后位置冲突，

3、返回false;否则返回true。 若两皇后的斜率为-1或1则表示在同一斜线上就冲突，返回false。 *k表示当前放置的皇后的行数。xk表示第k行皇后放置的列数。即第k个皇后放在第xk列。 =*/ bool Queen:Place(int k)for(int j=1;j<k;j+)/abs(k-j)=abs(xj-xk)时,两皇后在同一斜线上 if(abs(k-j)=abs(xj-xk)|(xj=xk)return false;return true;/*=Backtrack函数迭代求皇后放置的位置。如果已经放完最后一行，就将放置方案数加一，并将各个皇后放置的位置输出到记事本中否则，就

4、找一个可以放置的位置，然后进行下一行的放置。这里使用迭代实现，使用k来记录当前的行数如果某一行无位置可放，将回溯到前面一行，即k- ,选择其他位置放置皇后。 *k表示当前放置的皇后的行数。xk表示第k行皇后放置的列数。即第k个皇后放在第xk列。 =*/ void Queen:Backtrack(void)x1=0;int k=1;while(k>0)xk+=1;/第k行的放置皇后为第一列 /如果不满足约束条件就继续找后面一列看是否可放皇后 while(xk<=n)&&!(Place(k)xk+=1;/当前行有位置可放 if(xk<=n)/已经放完最后一行的皇后

5、if(k=n)sum+;/找到的放置方案数+1 /将具体放置方案写到记事本文件【N皇后_迭代.txt】中 static ofstream fout("N皇后_迭代.txt");fout<<"第"<<sum<<"种方案："<<endl;for(int i=1;i<=n;i+)for(int j=1;j<=n;j+)if(j=xi)fout<<"x "/x表示皇后放置的位置 else fout<<"* "/*表示没有

6、放置皇后的位置fout<<endl; /没有放完最后一行else k+;/继续放下一行 xk=0;/下一行刚开始为0位置，这样循环之后+1就可以从第1列开始看 /没有位置可放，就回溯到前面一行 else k-;/*=nQueen函数进行初始化，并方案数目返回。主要为调用Backtrack函数。 *n表示皇后数。 =*/ int nQueen(int n)Queen X;/初始化X X.n=n;X.sum=0;int *p=new intn+1;for(int i=0;i<=n;i+)pi=0;X.x=p;/调用函数 X.Backtrack();/删除动态分配内存 delete

7、p;return X.sum;测试结果Ø 8皇后输出共有多少种放置方案。输入皇后个数。具体放置方案在记事本中显示。 记事本中的结果如上所示。可以看到实现了方案的输出。8皇后问题的时候，算法的时间不如之前的写过的算法的性能好，这里主要是因为，在算法中实现了将结果写入到记事本中，浪费了很多时间。Ø 9皇后Ø 10皇后Ø 11皇后Ø 12皇后Ø 13皇后可以清楚的发现，N皇后问题，皇后越多，时间越多，当13皇后的时候这个时间已经非常大了，这里是因为算法实现的过程中要找到所有的情况，要将树全部遍历晚，皇后数目越多的时候树的结点就越多，遍历越慢

8、，所以耗费很长时间。与前面的递归实现相比，对应的N皇后的时间都差不多的，就是最后13皇后的时候，迭代实现比递归实现慢的很明显。实验心得因为前面已经使用递归实现了回溯法求N皇后问题，使用迭代实现的思路与使用递归实现的思路是一样的，代码的大体框架都是类似的，所以编写过程中没有什么大问题。这里主要是写一下迭代的代码来看一下区别。写完之后可以发现，其实思路都是一样的。递归的话，因为只要调用函数自身，传一个层数的参数进去就可以，所以代码显得十分简洁。但是就我们本身来说，看到一个完全不知道什么编写思路的代码如果使用了递归的话，我们理解起来可能会很有难度。我个人认为递归的代码实现比较容易出错。迭代的话，看到

9、代码会很容易读懂，但是会要增加另外的变量来表示到了哪一层，就会使代码显得比较冗长。就我个人来说，我一般喜欢写递归的实现，因为我是在已知思路的情况下进行代码编写，所以递归实现起来并不难。实验得分助教签名附录：完整代码#include<iostream>#include<cmath>#include<fstream>#include<time.h>#include<iomanip>#include<stdlib.h>using namespace std;/*=定义Queen类来存储皇后的信息。 =*/class Queenf

10、riend int nQueen(int);private:bool Place(int k);void Backtrack(void);int n;/皇后个数 int *x;/当前解 long sum;/当前已找到的可行方案数 ;/*=Place函数进行可行性约束。若当前的位置已经与之前放置的皇后位置冲突，返回false;否则返回true。 若两皇后的斜率为-1或1则表示在同一斜线上就冲突，返回false。 *k表示当前放置的皇后的行数。xk表示第k行皇后放置的列数。即第k个皇后放在第xk列。 =*/ bool Queen:Place(int k)for(int j=1;j<k;j+)

11、/abs(k-j)=abs(xj-xk)时,两皇后在同一斜线上 if(abs(k-j)=abs(xj-xk)|(xj=xk)return false;return true;/*=Backtrack函数迭代求皇后放置的位置。如果已经放完最后一行，就将放置方案数加一，并将各个皇后放置的位置输出到记事本中否则，就找一个可以放置的位置，然后进行下一行的放置。这里使用迭代实现，使用k来记录当前的行数如果某一行无位置可放，将回溯到前面一行，即k- ,选择其他位置放置皇后。 *k表示当前放置的皇后的行数。xk表示第k行皇后放置的列数。即第k个皇后放在第xk列。 =*/ void Queen:Backtra

12、ck(void)x1=0;int k=1;while(k>0)xk+=1;/第k行的放置皇后为第一列 /如果不满足约束条件就继续找后面一列看是否可放皇后 while(xk<=n)&&!(Place(k)xk+=1;/当前行有位置可放 if(xk<=n)/已经放完最后一行的皇后if(k=n)sum+;/找到的放置方案数+1 /将具体放置方案写到记事本文件【N皇后_迭代.txt】中 static ofstream fout("N皇后_迭代.txt");fout<<"第"<<sum<<&qu

13、ot;种方案："<<endl;for(int i=1;i<=n;i+)for(int j=1;j<=n;j+)if(j=xi)fout<<"x "/x表示皇后放置的位置 else fout<<"* "/*表示没有放置皇后的位置fout<<endl; /没有放完最后一行else k+;/继续放下一行 xk=0;/下一行刚开始为0位置，这样循环之后+1就可以从第1列开始看 /没有位置可放，就回溯到前面一行 else k-;/*=nQueen函数进行初始化，并方案数目返回。主要为调用Back

14、track函数。 *n表示皇后数。 =*/ int nQueen(int n)Queen X;/初始化X X.n=n;X.sum=0;int *p=new intn+1;for(int i=0;i<=n;i+)pi=0;X.x=p;/调用函数 X.Backtrack();/删除动态分配内存 deletep;return X.sum;/*=main函数是主函数。输入皇后的个数，调用之前的回溯法函数求出有多少种放置方案。输出有多少种放置方案。 *n表示皇后的个数。sum表示放置方案数。 =*/ int main()int n;int sum； /输入皇后的个数n cout<<"please input n:"cin>>n;/开始计时 clock_t start,end,over;start=clock();end=clock();over=end-start;start=clock();/调用函数 sum=nQueen(n);/结束计时 end=clock();/输出放置方案数 cout<<e