回溯算法实验.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)