问题链接：CCF NOI1153 素数环。
时间限制: 1000 ms 空间限制: 262144 KB
题目描述
输入n(2<=n<=20),把1到n这n个数摆成一个环，要求相邻的两个数的和是一个素数。输出任意一个合法答案。
输入
输入一行一个数n。
输出
输出1到n的一个排列，表示一个环。如果无解，则输出-1。
样例输入
4
样例输出
1 2 3 4
数据范围限制
2<=n<=20
提示
问题分析
该问题与《UVA524 UVALive5270 HDU1016 ZOJ1457 Prime Ring Problem》几乎是同一问题，只是有解的话输出一个解，输出格式不同。
程序说明
参见参考链接。
要点详解
- DFS是常用的解题方法。
参考链接：UVA524 UVALive5270 HDU1016 ZOJ1457 Prime Ring Problem。
100分通过的C语言程序：
#include <stdio.h>
#include <math.h>
#include <string.h>#define N 20int prime[N * 2];int ans[N];
int visited[N];
int n, flag;// Eratosthenes筛选法
void sieveofe(int p[], int n)
{int i, j;p[0] = 0;p[1] = 0;p[2] = 1;// 初始化for(i=3; i<n; i++) {p[i++] = 1;p[i] = 0;}int max = sqrt(n);for(i=3; i<=max; i++){if(p[i]) {for(j=i+i; j<=n; j+=i) //进行筛选p[j]=0;}}
}void print_result()
{int i;for(i=1; i<=n; i++) {if(i != 1)printf(" ");printf("%d", ans[i]);}printf("n");
}void dfs(int count)
{int i;if(count == n) {if(prime[ans[count] + ans[1]]) {print_result(); // 输出结果flag = 0;}} else {for(i=2; flag && i<=n; i++)if(!visited[i] && prime[i + ans[count]]) {ans[count + 1] = i;visited[i] = 1;dfs(count + 1);visited[i] = 0;}}
}int main(void)
{sieveofe(prime, N * 2 -1);// 初始化标志memset(visited, 0, sizeof(visited));scanf("%d", &n);if(n % 2 == 1)printf("-1n");else {// 深度优先搜索并且输出结果ans[1] = 1;visited[1] = 1;flag = 1;dfs(1);if(flag)printf("-1n");}return 0;
}