本题题意就是构成一个素数环。即相邻两数之和要为素数。环的元素个数在1到20之间。
同样是DFS，不过本题无需剪枝。为了提高效率呢，我使用了hash。即保存了一个素数表。最终运行结果是171ms。感觉还是不够快啊
#include <iostream>
using namespace std;
int prime[]={2,3,5,7,11,13,17,19,23,29,31,37};
bool isprime[40];
bool used[21];
int num[21],n;
bool dfs(int count,int cur)
{
num[count]=cur;
if(count==n-1)
{
if(!isprime[cur+1])
return false;
for(int i=0;i<n-1;i++)
printf("%d ",num[i]);
printf("%d
",num[n-1]);
return false;
}
for(int i=2;i<=n;i++)
{
if(used[i])
continue;
used[i]=true;
if(isprime[cur+i]&&dfs(count+1,i))
return true;
used[i]=false;
}
return false;
}
int main()
{
memset(isprime,false,sizeof(isprime));
for(int i=0;i<12;i++)
isprime[prime[i]]=true;
int Case=1;
while(scanf("%d",&n)!=EOF)
{
printf("Case %d:
",Case++);
memset(used,false,sizeof(used));
used[1]=true;
dfs(0,1);
printf("
");
}
return 0;
}