3901130814肖翰算法实验报告5.docVIP

算法分析与设计 实验报告 项目名称 回溯算法 专业班级 软件工程1303 学 号座机电话号码14 姓 名 肖翰 实验成绩： 批阅教师： 年 月 日 实验5《回溯算法》 实验学时： 2 实验地点： 二综202 实验日期： 2014..12.2 一、实验目的 1）通过实例理解深度优先策略和回溯机制。 2）用2-3个实例验证算法和时间复杂度。 二、实验内容 1）编程实现n皇后问题迭代回溯算法和递归算法。 三、实验方法 回溯法：在包含问题的所有解的解空间树中，按照深度优先有哪些信誉好的足球投注网站的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先有哪些信誉好的足球投注网站算法）。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被有哪些信誉好的足球投注网站遍才结束。 而若使用回溯法求任一个解时，只要有哪些信誉好的足球投注网站到问题的一个解就可以结束 2、对于第二行，从第一个空格开始寻找不与第一行的皇后冲突的空格。找到的第一个不冲突的空格是第2个。 3、对于第三行，这时已经找不到与之前放置的两个皇后不冲突的空格了。把当前行恢复初始状态，返回到上一行。 4、在当前行皇后所占的空格之后寻找一个不与之前皇后冲突的位置。有两种情况，如果找打了则把当前行的皇后移动到该位置，然后处理下一行。如果直到最后当前行的最后一个空格也没有找合适的位置，则把当前行恢复初始状态，继续回溯到上一行。 5、把最后一个皇后成功安置在最后一行，代表找到了一种可行解。返回步骤4。 6、当需要回溯到第0行（表格之外）的时候代表已经找遍了所有可能的可行解。 代码： 非递归： #include using namespace std; int sum 0;//解的个数 //判断该位置是否可以 bool place int k,int x[] for int j 1;j k;j++ if abs k - j abs x[k] - x[j] || x[k] x[j] return false; return true; //输出解 void print int x[],int n cout n 皇后的第 sum 个解为: ; for int i 1; i n; i++ cout x[i] ; cout endl; void Queens int n,int x[] int k 1; x[1] 0; while k 0 x[k] + 1; while x[k] n ! place k,x x[k] + 1; if x[k] n if k n sum++; print x,n ; else k++; x[k] 0; else k--; int main int n;//皇后的个数 cout 请输入皇后的个数: ; cin n; //每一列放皇后的位置 int *x new int[n + 1]; for int i 0; i n; i++ x[i] 0; Queens n,x ; if sum 0 cout n 皇后无解! endl; return 0; 递归： #include using namespace std; int sum 0;//解的个数 //判断该位置是否可以 bool place int k,int x[] for int j 1;j k;j++ if abs k - j abs x[k] - x[j] || x[k] x[j] return false; return true; //输出解 void print int x[],int n cout n 皇后的第 sum 个解为: ; for int i 1; i n; i++ cout x[i] ; cout endl; void Queens int t,int x[],int n if t n sum++; print x,n ; else for int i 1; i n; i++ x[t] i; if place t,x Queens t+1,x,n ; int main int n;//皇后的个数 cout 请输入皇后的个数: ; cin n; //每一列放皇后的位置 int *x new int[n + 1]; for int i