033：Prime RingProblem素环问题
Problem DescriptionA ring is composeof n circles as shown in diagram. Put natural number 1, 2, ..., n into eachcircle separately, and the sum of numbers in two adjacent circles should be aprime.
Note: the number of first circle should always be 1.
环是组合成n个圆圈所示的图。把自然数1，2，...，n为进分别各圈，和数字中的两个相邻圈之和应该是一个素数。
注意：第一圈的数量始终应为1。
Input
n (0 < n <20).
Output
The output formatis shown as sample below. Each row represents a series of circle numbers in thering beginning from 1 clockwisely and anticlockwisely. The order of numbersmust satisfy the above requirements. Print solutions in lexicographical order.
You are to write a program that completes above process.
Print a blank line after each case.
输出格式如下图所示的样品。每一行代表一个系列的圆形数字的环从1开始顺时针和按逆时针方向。号的顺序，必须满足上述要求。在字典顺序打印解决方案。
请你写一个程序，完成上述过程。
打印每个案例后，一个空行。
Sample Input
6
8
Sample Output
Case 1:
1 4 3 2 5 6
1 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 计算规模并不庞大，使用dfs和递归最容易不过
#include<cstdio>
#include<cstring>
#define N 20
using namespace std;
int ans;
bool hash;
int n;
int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41};
bool judge(int x)
{
for(int i=0;i<13;i++)
if(prime==x)
return true;
return false;
}
void check()
{
if(judge(ans+ans)==false)
return ;
for(int i=1;i<=n;i++)
{
if(i!=1)
printf(" ");
printf("%d",ans);
}
printf("\n");
}
void DFS(int num)
{
if(num>1)
if(judge(ans+ans)==false)
return ;
if(num==n)
{
check();
return ;
}
for(int i=2;i<=n;i++)
{
if(hash==false)
{
hash=true;
ans=i;
DFS(num+1);
hash=false; //关键！！！回溯！！！
}
}
}
int main()
{
int cas=0;
while(scanf("%d",&n)!=EOF)
{
cas++;
for(int i=0;i<N;i++)
hash=false;
ans=1;
printf("Case %d:\n",cas);
hash=true;
DFS(1);
printf("\n");
}
return 0;
}
页:
[1]