rime Ring Problem

A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n 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.

输入

n (0 < n < 20).

输出

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. Print solutions in lexicographical order.

You are to write a program that completes above process.

Print a blank line after each case.

样例输入

6 8

样例输出

Case 1: 1 4 3 2 5 6 1 6 5 2 3 4Case 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

AC代码：

#include<iostream> #include<cstdio> #include<cstring> using namespace std; int prime[40]={0}; int dir[21],ring[21]; void pri() {int i,j;prime[0]=prime[1]=1;for(i=2;i<=6;++i)for(j=i*i;j<40;j+=i)prime[j]=1; } int DFS(int x,int y) {int i;if(x==y+1&&prime[ring[y]+ring[1]]==0){printf("1 ");for(i=2;i<y;++i)printf("%d ",ring[i]);printf("%d\n",ring[y]);return 0;}for(i=2;i<=y;++i){if(!dir[i]&&!prime[i+ring[x-1]]){dir[i]=1;ring[x]=i;DFS(x+1,y);dir[i]=0;}} }int main() {int T=1,n;pri();while(~scanf("%d",&n)){printf("Case %d:\n",T++);if(n==1)printf("1\n");else if(n&1)continue;else {memset(dir,0,sizeof(dir));dir[1]=ring[1]=1;DFS(2,n);}printf("\n");}return 0; }

总结

以上是生活随笔为你收集整理的nyist 132Prime Ring Problem的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。