回溯法解决素数环.doc

算法分析实验报告回溯法-素数环学生姓名:专  业:计算机科学与技术班  级:学  号: 指导教师:2017年6月12日目录一、实验题目  2二、实验目的  2三、实验要求  2四、实现过程  31、实验设计:  32、调试分析:  73、运行结果:  84、实验总结:  8五、参考文献  9一、实验题目回溯法-素数环二、。。三、实验要求1.[问题描述]:把整数{1、2、3、····、20}填写到一个环中,要求每个整数只能填写一次,并且相邻的两个整数之和是一个素数。2.[算法]:回溯法: 在包含问题的所有可能解的解空间树中,从根节点出发,按照深度优先遍历的策略进行搜索,对于解空间树种的某个节点,如果该节点满足问题的约束条件,则进入该子树继续进行搜索,否则将以该节点为根节点的子树进行剪枝。回溯法常常可以避免所有的可能解,所以,适用于求解组合数中较大的问题。回溯法从解空间树的根节点出发,按照深度优先遍历策略搜索满足约束条件的解。在搜索至树种某节点时,先判断该节点对应的部分是否满足约束条件,也就是判断该节点是否包含问题的(最优)解,如果肯定不包含,则跳过该节点为跟的子树,即所谓剪枝;否则,进入以该节点为跟的子树,继续按照深度优先遍历策略进行搜索。四、实现过程1、实验设计:,每个位置可以填写的整数位1~20,共20种可能,可以对每个位置从1开始进行探索,约束条件是正在试探的数满足如下约束条件:(1)与已经填写的素数环中的整数不重复;(2)与前面相邻的整数之和是一个素数;(3)最后一个填写到素数环中的整数与第一个填写的整数之和是一个素数。在填写第K个位置时,如果满足上述约束条件,则继续填写第K+1个位置;如果1~20都无法填写到第K个位置,则取消对第K个位置的填写,回溯到第K+1个位置。{1、2、3、4}为例进行图解分析:由上图可知有两种结果:{1、2、3、4}{1、4、3、2}(intx)//判断整数x是否素数{inti,n;n=(int)sqrt(x);for(i=2;i<n;i++)if(x%i==0)  return0;return1;}intcheck(intk){intflag=0,n;for(inti=0;i<k;i++){if(a[i]==a[k])//判断是否重复return0;}flag=Prime(a[k]+a[k-1]);if(flag==1&&k==n-1)//判断第一个和最后一个是否素数flag=Prime(a[k]+a[0]);returnflag;}voidprimecircle(intn){inti,k;for(i=0;i<n;i++){a[i]=0;//将数组a[]初始化为0  }a[0]=1;k=1;//指定第0个位置填1while(k>=1){a[k]=a[k]+1;while(a[k]<=n){if(check(k)==1)//位置k可以填写数a[]break;elsea[k]=a[k]+1;//试探下一个数}i