//输入一个正整数,比如6,输出
//1 4 3 2 5 6
//1 6 5 2 3 4
//可以形成一个环,相邻的数的和是质数
#include <cstdio>
#include <cmath>
bool B[33],fuck[17][17];
int ay[17]={16,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
void output(int *p,int i)
{
if(p[1]==1)
{
for(int j=1;j<=i;++j)
{
if(j!=1)
printf(" %d",p[j]);
else
printf("%d",p[1]);
}
printf("\n");
}
}
void swap(int &i,int &j){int t=i;i=j,j=t;}
void backtrack(int i,int n)
{
int j;
if(i>n)
{
if(fuck[ay[1]][ay[n]])
output(ay,n);
return;
}
for(j=i;j<=n;++j)
{
swap(ay[i],ay[j]);
if(fuck[ay[i-1]][ay[i]])
backtrack(i+1,n);
swap(ay[j],ay[i]);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int i,j;
B[1]=false;
for(i=2;i<33;++i) B[i]=true;
for(i=2;i<=(int)sqrt((double)33);++i)
for(j=2;i*j<33;++j)
B[i*j]=false;
for(i=1;i<17;++i)
{ for(j=1;j<17;++j)
if(B[i+j]) fuck[i][j]=true;
else fuck[i][j]=false;
}
int flag=1,n;
while(scanf("%d",&n)!=EOF)
{
printf("Case %d:\n",flag++);
if(n==1)
{
printf("\n");
continue;
}
backtrack(1,n);
printf("\n");
}
return 0;
}
要是想输出更大数的质数环,方法一样
用深度搜索
^_^
再来一个代码欣赏,多多指教