回溯法解决素数环

算法分析实验报告回溯法-素数环学生姓名：专业：计算机科学与技术班级：学号:指导教师：2023年6月12日目录一、实验题目2二、实验目的2三、实验要求2四、实现过程31、实验设计：32、调试分析：73、运行结果：84、实验总结：8五、参考文献9一、实验题目回溯法-素数环二、实验目的1．掌握回溯法的设计思想。2．了解和掌握各种经典问题的回溯思想。三、实验要求1.[问题描述]：把整数{1、2、3、····、20}填写到一个环中，要求每个整数只能填写一次，并且相邻的两个整数之和是一个素数。2.[算法]：回溯法：在包含问题的所有可能解的解空间树中，从根节点出发，按照深度优先遍历的策略进行搜索，对于解空间树种的某个节点，如果该节点满足问题的约束条件，那么进入该子树继续进行搜索，否那么将以该节点为根节点的子树进行剪枝。回溯法常常可以防止所有的可能解，所以，适用于求解组合数中较大的问题。回溯法从解空间树的根节点出发，按照深度优先遍历策略搜索满足约束条件的解。在搜索至树种某节点时，先判断该节点对应的局部是否满足约束条件，也就是判断该节点是否包含问题的〔最优〕解，如果肯定不包含，那么跳过该节点为跟的子树，即所谓剪枝；否那么，进入以该节点为跟的子树，继续按照深度优先遍历策略进行搜索。四、实现过程1、实验设计：1.这个素数环有20个位置，每个位置可以填写的整数位1~20，共20种可能，可以对每个位置从1开始进行探索，约束条件是正在试探的数满足如下约束条件：与已经填写的素数环中的整数不重复；与前面相邻的整数之和是一个素数；最后一个填写到素数环中的整数与第一个填写的整数之和是一个素数。在填写第K个位置时，如果满足上述约束条件，那么继续填写第Ｋ＋１个位置；如果１～２０都无法填写到第Ｋ个位置，那么取消对第Ｋ个位置的填写，回溯到第Ｋ＋１个位置。2.图解过程以下以{1、2、3、4}为例进行图解分析：由上图可知有两种结果：{1、2、3、4} {1、4、3、2}3.算法实现intPrime(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个位置填1 while(k>=1) { a[k]=a[k]+1; while(a[k]<=n) { if(check(k)==1)//位置k可以填写数a[] break; else a[k]=a[k]+1;//试探下一个数 } if(a[k]<=n&&k==n-1)//求解完毕输出解 { for(i=0;i<n;i++) { cout<<a[i]<<""<<endl; } return; } if(a[k]<=n&&k<n-1)//填写下一个位置 k=k+1; else a[k--]=0;//回溯 }2、调试分析：设要填写1—n共n个整数，由于每个位置可以填写的情况有n种，因此，素数环问题的解空间数是一棵完全n叉树，且树的深度为n+1，因此，最坏情况下的时间性能为O〔nⁿ〕。3、运行结果：4、实验总结：通过本次实验加深了我对回溯算法所给的模式的理解，同时对用回溯算法解决一个实际问题有了一个更深层次的认识。回溯算法非递归的模式通用，用它解决一个问题的关键是找出合法解与局部解的判断条件，在合法解时书写相应程序段，在局部解时书写相应程序段。另外注意有些条件局部解和合法解都要满足，此时要排除掉非法解，即要给它剪去。另外需要注意的是回溯的过程。总之，通过本次实验使我掌握了回溯算法非递归的一般模式，以后在解决一类问题时可以照着这个模式编写程序。通过本次试验，自己根本上掌握上述算法原