回溯算法实验

《回溯算法实验》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验五回溯算法的应用2一、实验目的2二、实验内容3三、实验步骤4一．实验目的5二．问题描述5三．算法设计5程序调试及运行结果分析6实验总结79实验五回溯算法的应用一、实验目的1．掌握回溯算法的基本概念2．熟练掌握回溯算法解决问题的基本步骤。3．学会利用回溯算法解决实际问题。二、实验内容1.问题描述：题目一：N皇后问题要在n*n的国际象棋棋盘中放n个皇后，使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。求所有的解要求：键盘输入皇后的个数n(n≤13)输出有多少种放置方法输入输出实例：9题目二：素数环问题编写一简单程序实现素数环问题：把从1到20这20个数摆

2、成一个环，要求相邻两个数的和是一个素数。要求：键盘输出结果2.数据输入：个人设定，由键盘输入。3.要求：1）上述题目全做。上机前，完成程序代码的编写2）独立完成实验及实验报告三、实验步骤1.理解算法思想和问题要求；2.编程实现题目要求；3.上机输入和调试自己所编的程序；4.验证分析实验结果；5.整理出实验报告。9附：实验报告的主要内容一．实验目的二．问题描述三．算法设计包含：数据结构与核心算法的设计描述、函数调用及主函数设计、主要算法流程图等N皇后问题解决思路是运用深度优先搜索，并能在不满足约束条件是及时回溯。而回溯是由函数调用结束自动完成的。Main函数调用queen2函数输入数据n调用

3、backdate函数搜索第K个皇后位置找到打印结果从头继续搜素9素数环问题解决思路为Check1判断是否重复，check2判断x是否为素数，先进行数据初始化然后递归填数。找到目标则打印，如图。Main函数循环输入数据数据初始化判断第i种可能是否合法进行下一种可能填数是否判断是否达到目标递归填下一个是否打印结果程序调试及运行结果分析N皇后问题:解决错误，运行程序，输入数据n之后，如图成功输出结果。9素数环问题:素数环问题主要就是用Check1判断是否重复，check2判断x是否为素数，先进行数据初始化然后递归填数。成功运行程序后，显示结果。实验总结本次实验主要运用回溯算法，我学会了通过对问题

4、的分析，找出一个解决问题的线索，然后沿着这个线索往前试探，若试探成功，就得到解，若试探失败，就逐步往回退，换别的路线再往前试探。实际上是广度与深度搜索结合的搜索，深度搜索过程中碰到条件不满足，则退回上一层，在每一层上也进行全面的搜索。回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。而回溯的指导思想就是走不通，就掉头。所以我也感觉到这是一种很高效的算法，但在本次实验中我还不能够熟练的应用，我会在课下时间多对这种算法加以练习。以是将来能够熟练的应用。9附录：程序清单（程序过长，可附主要部分）N皇后问题代码如下：#incl

5、udeusingnamespacestd;inta[20],n;intbackdate(intn);intcheck(intk);voidoutput();intmain(){voidqueen2();queen2();return0;}voidqueen2(){cout<<"请输入n"<>n;backdate(n);}intbackdate(intn){intk;a[1]=0;k=1;while(k>0){a[k]=a[k]+1;while((a[k]<=n)&&(check(k)==0))//搜索第k个皇后位置a[k]=a[k]+1;if(a[k

6、]<=n)if(k==n)output();//找到一组解/else{k=k+1;a[k]=0;}//注意下一个皇后一定要从头开始搜索/继续为第k+1个皇后找到位置/elsek=k-1;}return0;}intcheck(intk){inti;9for(i=1;i<=k-1;i++){if((abs(a[i]-a[k])==abs(i-k))

7、

8、(a[i]==a[k]))return0;}return1;}voidoutput(){inti;for(i=1;i<=n;i++)cout<#inclu

9、deusingnamespacestd;inta[20],k;voidtry1(inti);check1(intj,inti);check3(intj,inti);voidoutput();voidmain(){cout<<"请依次输入数字：1~20"<>a[k];a[1]=1;try1(2);}voidtry1(inti){intk;for(k=2