1.素数环
题目(http://coder.buct.edu.cn/oj/Problem.aspx?pid=1630)
要保持序列最小，第一个必为1
那么可以如下剪枝：
1.奇数位为偶数 偶数位为奇数
2.输入的n必为偶数，奇数无解
3.注意边缘数据 1
code
#include<iostream>
using namespace std;
int circle[22];
int n,cLength,j;
int used[21];
bool finished;
//prime set
int prim[]={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,0,
1,0
};
void DFS()
{
if(cLength==n)
if(prim[circle[n-1]+circle[0]])
{
finished=true;
j=0;
for(int k=0;k<cLength;k++)
{
if(j>0)
printf(" ");
printf("%d",circle[k]);
j++;
}
printf("\n");
return ;
}
for(int i=2;i<=n && !finished;i++)
{
if(!used[i] && ((cLength+i)%2) && prim[circle[cLength-1]+i])
{
used[i]=1;
circle[cLength++]=i;
DFS();
cLength--;
used[i]=0;
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d",&n)==1)
{
if(n==1)
printf("%d\n",1);
else if(!(n%2))//odd number
{
finished=false;
cLength=0;
memset(used,0,sizeof(used));
memset(circle,0,sizeof(circle));
circle[0]=1;
used[1]=1;
cLength++;
DFS();
}
}
return 0;
}