UVa-524 题意：要求把1，2，3，……，n排列，围成一个环，相邻两个数和为素数。以1为首，顺时针输出所有可能。 思路：A[0]=1，然后搜索下一个位置的数字，直到用完n个数字，注意判断第一个和最后一个数字和也为素数。题目很简单，但要理解回溯的思想。
#include<cstdio> #include<cstring> using namespace std; const int maxn = 35; int prime[maxn],A[20],vis[20]; int n; void dfs(int cur) { if(cur == n && !prime[A[cur-1]+A[0]]){ for(int i = 0; i < n-1; i++){ printf("%d ",A[i]); } printf("%d\n",A[n-1]); return; } else{ for(int i = 2; i <= n; i++){ if(!vis[i] && !prime[A[cur-1]+i]){ A[cur] = i; vis[i] = 1; dfs(cur+1); vis[i] = 0; } } } return; } int main() { memset(prime,0,sizeof(prime)); prime[0] = prime[1] = 1; for(int i = 2; i < maxn; i++){ if(!prime[i]) for(int j = 2; i*j < maxn; j++){ prime[i*j] = 1; } } int cas = 1; while(~scanf("%d",&n)){ memset(vis,0,sizeof(vis)); if(cas != 1) printf("\n"); printf("Case %d:\n",cas++); memset(A,0,sizeof(A)); vis[1] = A[0] = 1; dfs(1); } return 0; }