回溯算法试验

1、精品文档实验五 回溯算法的应用 . 2一、实验目的 . 2二、实验内容 . 2三、实验步骤 . 3一实验目的 . 4二问题描述 . 4三算法设计 . 4程序调试及运行结果分析 . 5实验总结 . 61欢。迎1下载精品文档实验五回溯算法的应用一、实验目的1 掌握回溯算法的基本概念2 熟练掌握回溯算法解决问题的基本步骤。3 学会利用回溯算法解决实际问题。二、实验内容1问题描述：题目一：N 皇后问题要在 n*n 的国际象棋棋盘中放 n 个皇后，使任意两个皇后都不能互相吃掉 规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。求所有的解要求：键盘输入皇后的个数 n (n 13)输出有多少种放置方法输

2、入输出实例：2欢迎下载精品文档题目二：素数环问题编写一简单程序实现素数环问题： 把从 1 到 20 这 20 个数摆成一个环，要 求相邻两个数的和是一个素数。要求：键盘输出结果2.数据输入 ：个人设定，由键盘输入。3. 要求 ：1）上述题目全做。上机前，完成程序代码的编写2）独立完成实验及实验报告三、实验步骤1. 理解算法思想和问题要求；2. 编程实现题目要求；3. 上机输入和调试自己所编的程序；4. 验证分析实验结果；5. 整理出实验报告。3欢。迎3下载精品文档附：实验报告的主要内容一. 实验目的二. 问题描述三. 算法设计包含：数据结构与核心算法的设计描述、函数调用及主函数设计、主要算法流

3、程图等N 皇后问题解决思路是运用深度优先搜索，并能在不满足约束条 件是及时回溯。而回溯是由函数调用结束自动完成的。Main 函数 调用 queen2 函数4欢迎下载精品文档素数环问题解决思路为 Checkl 判断是否重复， check2 判断 x 是 否为素数，先进行数据初始化然后递归填数。找到目标则打印，如图。程序调试及运行结果分析N 皇后问题：解决错误，运行程序，输入数据n 之后，如图成功输出结果D:VCM icrosoft Visual &tudioMyProjectsacniDebugl,exe请输入n513524142S3241352S31431425352414135242

4、5315241353142Press anto coint inu.e5欢迎下载精品文档素数环问题：素数环问题主要就是用 Checkl 判断是否重复，check2 判断 x 是否 为素数，先进行数据初始化然后递归填数。成功运行程序后，显示结果。DCMicrasoh Visual StudioMyProje出算法设计Debug数环巨C.exe123476111219185892017141516131012347611121918581514172MV10131612347611121918S1417209815161310123476111219181310920171458151612347

5、611i2191813161bB514172tlV101234761118589201714151S13101V12123476111858151492017121V1013161234761118514158920171219101316123476111851417209815161310191212347611181310191258920171415161234761118131019125141720981516123476111813101912172098514151612347611181310191217209145815161234761118131615851492017

6、1219101234761118131615851417209101912实验总结本次实验主要运用回溯算法，我学会了通过对问题的分析，找出一个解决问 题的线索，然后沿着这个线索往前试探，若试探成功，就得到解，若试探失败， 就逐步往回退，换别的路线再往前试探。实际上是广度与深度搜索结合的搜索， 深度搜索过程中碰到条件不满足，则退回上一层，在每一层上也进行全面的搜索。 回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷 举式搜索法。这种方法适用于解一些组合数相当大的问题。 而回溯的指导思想就 是走不通，就掉头。所以我也感觉到这是一种很高效的算法， 但在本次实验中我 还不能够熟练

7、的应用，我会在课下时间多对这种算法加以练习。 以是将来能够熟 练的应用。6欢迎下载精品文档附录：程序清单 (程序过长，可附主要部分)N 皇后问题代码如下：#includeusing namespace std;int a20,n;int backdate(int n);int check(int k);void output();int main()void queen2();queen2();return 0;void queen2()cout请输入nn;backdate(n);int backdate (int n)int k; a1=0; k=1; while(k0)ak=ak+1; w

8、hile (ak=n)&(check(k)=0) /搜索第k个皇后位置ak=ak+1;if(ak=n)if(k=n)output(); /找到一组解/elsek=k+1;ak=0; /注意下一个皇后一定要从头开始搜索/继续为第k+1个皇后找到位置/elsek=k-1;return 0;int check(int k)7欢迎7下载精品文档int i;for(i=1;i=k-1;i+)if(abs(ai-ak)=abs(i-k)|(ai=ak) return 0;return 1;void output()int i; for(i=1;i=n;i+) coutai;coutendl;素数环

9、问题代码如下：#include #include using namespace std;int a20,k; void try1 (int i); check1(int j,int i); check3(int j,int i); void output(); void main( )cout请依次输入数字：120endl;for(k=1;kak;a1=1;try1(2);void try1 (int i)int k; for(k=2;k=20;k+)if (check1(k,i)=1&check3(k,i)=1)ai=k;if (i=20)output(); else8欢。迎8下载精品文档try1(i+1);ai=0;check1(int j,int i)int k;for (k=1;k=i-1;k+)if (ak=j) return(0);return(1);check2(int x)int k,n;n=sqrt(x);for (k=2;k=n;k+)if (x%k=0) return(0);return(1);check3(int j,int i)if (i20)return(check2(j+ai-1);else return