nyist 488 素数环（搜索+回溯） - c++编程基础

素数环

时间限制：1000 ms | 内存限制：65535 KB 难度：2

描述

有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。

为了简便起见，我们规定每个素数环都从1开始。例如，下图就是6的一个素数环。

输入

有多组测试数据，每组输入一个n(0 输出

每组第一行输出对应的Case序号，从1开始。
如果存在满足题意叙述的素数环，从小到大输出。
否则输出No Answer。

样例输入

样例输出

Case 1:
1 4 3 2 5 6
1 6 5 2 3 4
Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
Case 3:
No Answer

来源

hdu改编

上传者

ACM_丁国强

这道题应该算是比较简单的题了，提交了好几次都是TLE，我就郁闷了。。。看来基础还是不扎实啊。。。最后用素数的哈希表终于AC了。。。先前是各种TLE，程序优化真的很重要啊。这就是算法的魅力所在~

#include 
      
       
#include 
       
         #define MAXN 40 int A[MAXN]; int vis[MAXN]; int n; int isprime[40]={ 0,0,1,1,0,1,0,1,0,0, 0,1,0,1,0,0,0,1,0,1, 0,0,0,1,0,0,0,0,0,1, 0,1,0,0,0,0,0,1,0,0, };//素数的哈希表，1代表就是素数 void dfs(int cur)//搜索+回溯（回溯其实也是根据树的深度搜索来的） { int i; if(cur==n && isprime[A[0]+A[n-1]])//递归边界，对第一个和最后一个数进行测试 { for(i=0;i
         
         这里我应该还是钻了空子，还是不太严谨，20一类的偶数都能够成素数环，大于20就不一定了，还是有待改进啊。。





 
          
          本来是想用筛选发筛选出素数的，各种TLE啊。。。 （感觉筛选法效率挺高的啊） 
         
          
          
           for(i=2;i<=MAXN;i++)
       {
       	   isprime[0]=isprime[1]=1;
           if(isprime[i]==0)
            for(j=i+i;j
           
            还是应该多学习别人的优秀算法，学无止境啊。 多学习别人的经验
            ，keep moving！！！！