Prime ring problem

Description

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.

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

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

这个先用深搜求n个数的全排列，这样就枚举了每一种情况，在对素数打表，以进行快速判断。

这个UVA上需要注意输出的最后一组数据不能有多余的空行

#include"iostream"
#include"cstring"
#include"cstdio"
using namespace std;
int n,book[21],a[21];
int ca=1;
int dic[52]={0,1,1,1,0,1,
0,1,0,0,0,
1,0,1,0,0,
0,1,0,1,0,
0,0,1,0,0,
0,0,0,1,0,
1,0,0,0,0,
0,1,0,0,0,
1,0,1,0,0,
0,1,0,0,0,
0
};

void dfs(int step)
{
    if ((step == n) && dic[a[1] + a[n]])
    {
        for(int i=1; i<n; i++)  cout<<a[i]<<' ';
        cout<<a[n]<<endl;
        return;
        return;
    }
    for(int i=2; i<=n; i++)
        if(!book[i] && dic[a[step] + i])
        {
            a[step+1]=i;
            book[i]=1;
            dfs(step+1);
            book[i]=0;
        }
}
int main()
{
    int x=1;
    while(scanf("%d",&n)!=EOF)
    {
        a[1]=1;
        if(x>1) cout<<endl;
        x++;
        cout<<"Case "<<ca++<<':'<<endl;
        dfs(1);
    }
    return 0;
}

View Code

也可以用暴力的方法求数全排，不过会超时，暂且贴上来吧

#include"iostream"
#include"cstring"
#include"cstdio"
using namespace std;
int n,book[21],a[21];
int ca=1;
int dic[52]={0,1,1,1,0,1,
0,1,0,0,0,
1,0,1,0,0,
0,1,0,1,0,
0,0,1,0,0,
0,0,0,1,0,
1,0,0,0,0,
0,1,0,0,0,
1,0,1,0,0,
0,1,0,0,0,
0
};

void print(int step)
{
if ((step == n+1))
{
int okk=1;
for(int k=1;k<n;k++) if(dic[a[k]+a[k+1]]==0) okk=0;
if(dic[a[n]+a[1]]==0) okk=0;
if(okk)
{
for(int i=1;i<n;i++) cout<<a[i]<<' ';
cout<<a[n]<<endl;
}
}

for(int i=1;i<=n;i++)
{
int ok=1;
for(int j=1;j<step;j++)
if(a[j]==i) ok=0;
if(ok)
{
a[step]=i;
print(step+1);
}
}
}

int main()
{
int x=1;
while(scanf("%d",&n)!=EOF)
{
memset(a,0,sizeof(a));
a[1]=1;
if(x>1) cout<<endl;x++;
cout<<"Case "<<ca++<<':'<<endl;
print(2);
}
return 0;
}

View Code