UVA524 素数环 Prime Ring Problem
题目大意
从1到n这n个数摆成一个环，要求相邻两个数的和是一个素数。
题解
一道简单的回溯题，递归填数，判断第i个数是否合法。如果合法，填数，判断是否n个已填满，如果填满且与第一位相加也是素数，输出结果，回溯；否则递归填下一个。
此题中n较小，如果n较大可以使用欧拉筛提前筛出素数，n1查询。
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int n,a[25],tot; bool v[25]; bool pd(int x) { for(int i=2;i<=x-1;i++) if(x%i==0)return 1; return 0; } void dfs(int x) { tot++;a[tot]=x;v[x]=1; if(tot==n) { if(!pd(1+a[n])) { for(int i=1;i<=n;i++)printf("%d ",a[i]); printf(" "); } return ; } for(int i=2;i<=n;i++) { if(v[i]==1)continue; else { int ans=x+i; if(pd(ans))continue; else { dfs(i); v[i]=0;a[tot]=0;tot--; } } } } int main() { int t=0; while(scanf("%d",&n)!=EOF) { memset(v,0,sizeof(v)); memset(a,0,sizeof(a)); t++; printf("Case %d: ",t); tot=0; dfs(1); printf(" "); } return 0; }