524 - Prime Ring Problem
Time limit: 3.000 seconds
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=465
A ring is composed of n (even number) circles as shown in diagram. Put natural numbers
into each circle separately, and the sum of numbers in two adjacent circles should be a prime.
Note: the number of first circle should always be 1.
Input
n (0 < n <= 16)
Output
The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements.
You are to write a program that completes above process.
Sample Input
68
Sample Output
Case 1:1 4 3 2 5 61 6 5 2 3 4
Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
完整代码:
/*0.268s*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int n, A[50], isp[50], vis[50];
int is_prime(int x)
{
for (int i = 2; i * i <= x; i++)
if (x % i == 0)
return 0;
return 1;
}
void dfs(int cur)
{
if (cur == n && isp[A[0] + A[n - 1]])///递归边界,别忘了测试第一个数和最后一个数
{
printf("%d", A[0]);
for (int i = 1; i < n; i++)
printf(" %d", A[i]);///打印方案
putchar('\n');
}
else
{
for (int i = 2; i <= n; i++)///尝试放置每个数i
if (!vis[i] && isp[i + A[cur - 1]])///如果i没有用过,并且与前一个数之和为素数
{
A[cur] = i;
vis[i] = 1;///使用此数并传入后续计算
dfs(cur + 1);
vis[i] = 0;///撤销此数的使用
}
}
}
int main(void)
{
int k = 0;
int first = 0;
while (~scanf("%d", &n))
{
if (first)
putchar('\n');
printf("Case %d:\n", ++k);
memset(A, 0, sizeof(A));
memset(isp, 0, sizeof(isp));
for (int i = 2; i <= n * 2; i++)
isp[i] = is_prime(i);
memset(vis, 0, sizeof(vis));
A[0] = 1;
dfs(1);
first = 1;
}
return 0;
}