uva-524 Prime Ring Problem 回溯法
程序员文章站
2022-06-08 17:57:39
...
回溯法搜索+素数判断
本题的输出格式及其坑,需要注意
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int vis[20];
int cur=0;
int ans[20];
int n;
bool prime(int x)
{
if(x==2) return 1;
if(x%2==0||x<2) return 0;
else
for(int i=3;i<=sqrt(x+1);i+=2)
{
if(x%i==0)
return 0;
}
return 1;
}
void dfs(int cur)
{
if(cur==n&&prime(ans[0]+ans[n-1])) //最末尾和最前元素
{ printf("%d",ans[0]);
for (int i = 1;i < n;i++) printf(" %d",ans[i]);
printf("\n");
}
else for(int i=2;i<=n;i++)
{
if(prime(i+ans[cur-1])==1&&!vis[i])
{ ans[cur]=i;
vis[i]=1;
dfs(cur+1);
vis[i]=0;
}
}
}
int main()
{
int kase=0;
while(~scanf("%d",&n))
{
memset(vis,0,sizeof(vis));
if(kase)
cout<<endl;
printf("Case %d:\n",++kase);
ans[0]=1;
dfs(1);
}
return 0;
}