回溯法解决n后问题

回溯法解决n后问题

ID:15092089

大小:1.23 MB

页数:10页

时间:2018-08-01

回溯法解决n后问题_第1页
回溯法解决n后问题_第2页
回溯法解决n后问题_第3页
回溯法解决n后问题_第4页
回溯法解决n后问题_第5页
资源描述:

《回溯法解决n后问题》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、算法设计技巧与分析论文题目:回溯法解决N后问题实验报告院系:计算机与通信工程学院班级:计算机科学与技术08-1班姓名:***学号:20080701****回溯法解决N后问题实验名称随机与回溯结合解决八皇后问题课程名称算法分析与设计姓名***专业班级学号计算机08-1班20080701****日期2011.06.15地点西一楼207成绩教师***,***一、实验目的1.掌握回溯法的设计思想。2.设计回溯算法完成N后问题求解。3.考察回溯法求解问题的有效程度。二、实验要求1.输入皇后个数N。2.用回溯法解决N后问题的所有解,并表示出来。3.输出解决N后问

2、题所需时间。三、实验内容(1)为解决这个问题,我们把棋盘的横坐标定为i,纵坐标定为j,i和j的取值范围是从1到8。当某个皇后占了位置(i,j)时,在这个位置的垂直方向、水平方向和斜线方向都不能再放其它皇后了。(2)为第i个皇后选择位置的算法如下:for(j=1;j<=8;j++)/*第i个皇后在第j行*/if((i,j)位置为空))/*即相应的三个数组的对应元素值为1*/-9-{占用位置(i,j)/*置相应的三个数组对应的元素值为0*/ifi<8为i+1个皇后选择合适的位置;else输出一个解}一、实验结果皇后个数为1:皇后个数为2:皇后个数为3:皇

3、后个数为4:-9-皇后个数为8时:-9--9-一、实验心得本实验是在别人代码的基础上,结合自己对回溯算法的理解改的。在最初的时候,遇到了很大的麻烦,毕竟是改的别人的代码,对代码的理解不是很透彻,出现了很多错误,但在同学们的帮助下,通过自己的一个下午加一个晚上的修改,终于调试成功。在做实验的过程中,我不知道怎么获得系统时间,通过查阅资料和上网搜索,得到了答案:intiStart,iEnd;-9-iStart=GetTickCount();//得到系统时间nQueen(n);iEnd=GetTickCount();//得到系统时间cout<<"Itnee

4、d"<#include#include#includeclassQueen{friendintnQueen(int);private:boolPlace(intk);voidBacktrack(intt);voidOutput();intn,//皇后个数*x;//当前解longsum;//当

5、前已找到的可行性方案数};boolQueen::Place(intk){for(intj=1;j

6、

7、(x[j]==x[k]))-9-{returnfalse;}}returntrue;}voidQueen::Backtrack(intt){if(t>n){sum++;Output();}else{for(inti=1;i<=n;i++){x[t]=i;if(Place(t)){Backtrack(t+1);}}}}intnQueen(intn){QueenX;-9-X.n=n;

8、X.sum=0;int*p=newint[n+1];for(inti=0;i<=n;i++){p[i]=0;}X.x=p;X.Backtrack(1);delete[]p;returnX.sum;}voidQueen::Output(){cout<<"*****第"<

9、";cout<<"⊙",x[i]+1;cout<<"│";for(j=x[i];j<=n-1;j++)cout<<"│";cout<<"";if(in-1){cout<<"└";//end行for(k=1;k>n;i

10、ntiStart,iEnd;iStart=GetTickCount();//得到系统时间nQueen(n);

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。