回溯算法实验样本.doc

试验五回溯算法应用 2一、试验目标 2二、试验内容 3三、试验步骤 5程序调试及运行结果分析 6试验总结 7试验五回溯算法应用一、。。二、:题目一:N皇后问题要在n*n国际象棋棋盘中放n个皇后,使任意两个皇后全部不能相互吃掉。规则:皇后能吃掉同一行、同一列、同一对角线任意棋子。求全部解要求:键盘输入皇后个数n(n≤13)输出有多少种放置方法输入输出实例:题目二:素数环问题编写一简单程序实现素数环问题:把从1到20这20个数摆成一个环,要求相邻两个数和是一个素数。要求::个人设定,由键盘输入。:1)上述题目全做。上机前,完成程序代码编写2)独立完成试验及试验汇报三、;;;;。附::数据结构和关键算法设计描述、函数调用及主函数设计、关键算法步骤图等N皇后问题处理思绪是利用深度优先搜索,并能在不满足约束条件是立即回溯。而回溯是由函数调用结束自动完成。Main函数调用queen2函数输入数据n调用backdate函数搜索第K个皇后位置找到打印结果从头继续搜素素数环问题处理思绪为Check1判定是否反复,check2判定x是否为素数,优异行数据初始化然后递归填数。找到目标则打印,图。Main函数循环输入数据数据初始化判定第i种可能是否正当进行下一个可能填数是否判定是否达成目标递归填下一个是否打印结果程序调试及运行结果分析N皇后问题:处理错误,运行程序,输入数据n以后,图成功输出结果。素数环问题:素数环问题关键就是用Check1判定是否反复,check2判定x是否为素数,优异行数据初始化然后递归填数。成功运行程序后,显示结果。试验总结此次试验关键利用回溯算法,我学会了经过对问题分析,找出一个处理问题线索,然后沿着这个线索往前试探,若试探成功,就得到解,若试探失败,就逐步往回退,换别路线再往前试探。实际上是广度和深度搜索结合搜索,深度搜索过程中碰到条件不满足,则退回上一层,在每一层上也进行全方面搜索。回溯法基础做法是搜索,或是一个组织得井井有条,能避免无须要搜索穷举式搜索法。这种方法适适用于解部分组合数相当大问题。而回溯指导思想就是走不通,就掉头。所以我也感觉到这是一个很高效算法,但在此次试验中我还不能够熟练应用,我会在课下时间多对这种算法加以练习。以是未来能够熟练应用。附录:程序清单(程序过长,可附关键部分)N皇后问题代码以下:#include<iostream>usingnamespacestd;inta[20],n;intbackdate(intn);intcheck(intk);voidoutput();intmain(){ voidqueen2(); queen2(); return0; }voidqueen2(){ cout<<"请输入n"<<endl; cin>>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]<=n) if(k==n) output();//找到一组解/ else { k=k+1; a[k]=0; }//注意下一个皇后一定要从头开始搜索/继续为第k+1个皇后找到位置/ else k=k-1; } return0;}intcheck(intk){ inti; for(i=1;i<=k-1;i++) { if((abs(a[i]-a[k])==abs(i-k))||(a[i]==a[k])) return0; } return1;}voidoutput(){ inti; for(i=1;i<=n;i++) cout<<a[i]; cout<<endl;}素数环问题代码以下:#include<iostream>#include<>usingnamespacestd;inta[20],k;voidtry1(inti);check1(intj,inti);check3(intj,inti);voidoutput();voidmain(){cout<<"请依次输入数字:1~20"<<endl; for(k=1;k<=20;k++) cin>>a[k]; a[1]=1; try1(2);}voidtry1(