hdu 1016 Prime Ring Problem

Prime Ring Problem

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 18313    Accepted Submission(s): 8197

Problem Description

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.

hdu 1016   Prime Ring Problem
Input

n (0 < n < 20).
 
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. Print solutions in lexicographical order.

You are to write a program that completes above process.

Print a blank line after each case.
 
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
 

 
2013/5/8 17:28:00
这道题之前做过一遍,那一次程序效率比现在这个还要高,但原来怎么做的我已经忘了,遂又找了个时间做了一遍。
由于是做过的第一道DFS(深度优先搜索)的搜索题,所以一定要弄熟。
 
hdu 1016   Prime Ring Problem
 1 #include <iostream>
 2 using namespace std;
 3 int a[21][21];
 4 int q[21];  //定义一个队列q,存储当前确定的素数环 
 5 int main()
 6 {
 7     bool boo_prime(int);
 8     void f(const int ,int ,int q[21]);
 9     int i,j,n,digit;
10     int count=1;
11     //计算20以内的素数矩阵,存储到二维数组a中 
12     for(i=1;i<=20;i++)
13         for(j=1;j<=20;j++)
14             if(boo_prime(i+j))
15                 a[i][j]=1;
16             else
17                 a[i][j]=0;
18     a[1][1]=0;   
19     //循环输入n,输出每一个n所有符合的素数环 
20     while(cin>>n){
21         digit=1;
22         cout<<"Case "<<count<<":"<<endl;
23         f(n,digit,q);   //调用递归函数f(),输出每种符合的情况 
24         cout<<endl;
25         count++;
26     }
27     return 0;
28 }
29 bool boo_prime(int n)     //判断一个整数n是不是素数 
30 {
31     int i;
32     //判断n是不是素数
33     if(n==1) return false;
34     if(n==2) return true;
35     for(i=2;i<n;i++){
36         if(n%i==0) return false;
37     }
38     return true;
39 }
40 void f(const int n,int digit,int q[21]) 
41 {
42     if(digit==1){    //如果确认到第1位
43         q[1]=1;
44         f(n,digit+1,q);
45     } 
46     else if(digit<=n){      //如果确认到第2~n位
47         int i,j;
48         for(j=1;j<=n;j++){      //循环确定当前位数上的数字是谁 
49             if(a[q[digit-1]][j]==1){     //上一个确认的数字和j之和是否为素数。若是素数,继续向下判断 
50                 bool boo=true;
51                 //如果这个数字就是j的话,它需要不能和前面确定的数字重复
52                 for(i=1;i<digit;i++)
53                     if(j==q[i]){    //如果和前面确定的数字重复的话,令boo=false,说明这种情况不可能;若没有重复,boo默认=true,即下个数字可以是j 
54                         boo=false;
55                         break;
56                     }
57                 if(boo){    //如果这个数字可以是j 
58                     q[digit]=j;         //确认这个数字就是j
59                     if(digit==n){
60                         if(a[j][1]==1)
61                             f(n,digit+1,q);
62                     }
63                     else 
64                         f(n,digit+1,q);     
65                 }
66             }
67         }
68     }
69     else if(digit>n){    //搜索到一种符合的情况,输出 
70         int i;
71         for(i=1;i<=n;i++)
72             if(i==n) cout<<q[i]<<endl;
73             else cout<<q[i]<< ;
74     } 
75 }
hdu 1016   Prime Ring Problem
Run ID Submit Time Judge Status Pro.ID Exe.Time Exe.Memory Code Len. Language Author
8262140 2013-05-08 17:24:05 Accepted 1016 890MS 388K 2263 B G++ freecode
 
 

 
2014/1/13 10:23:00
时隔8个月,已经进入了2014年,现在是第二上学期的寒假第四天。
寒假训练比赛上有这道题,遂重新做了一遍,这一次,没有费多大事就AC,思路更加清晰。
下面贴上代码
 
hdu 1016   Prime Ring Problem
 1 #include <iostream>
 2 #include <string.h>
 3 using namespace std;
 4 int a[20];    //存储数 
 5 bool isu[20];    //有没有被用过,默认为false(没有) 
 6 int p[38];    //素数表 
 7 bool prime(int n)    //判断某整数是不是素数
 8 {
 9     if(n==2)
10         return true;
11     for(int i=2;i<n;i++){
12         if(n%i==0)
13             return false;
14     }
15     return true;
16 } 
17 void dfs(int s,int n)     //代表第s个数已经确定 
18 { 
19     if(s>=n){
20         if(!p[a[s]+a[1]])
21             return ;
22         for(int i=1;i<n;i++)
23             cout<<a[i]<< ;
24         cout<<a[n]<<endl;
25     }
26     else{
27         for(int i=2;i<=n;i++){
28             if(isu[i])
29                 continue;
30             if(!p[a[s]+i])
31                 continue;
32             a[s+1]=i;
33             isu[i]=true;
34             dfs(s+1,n);
35             a[s+1]=0;
36             isu[i]=false;
37         }
38     }
39 }
40 int main()
41 {
42     int n,_count=1;
43     p[0]=1;
44     while(cin>>n){
45         memset(isu,0,sizeof(isu));
46         if(p[0]){
47             //计算38以内的素数矩阵 
48             p[0]=0;
49             for(int i=1;i<=38;i++)
50                 if(prime(i))
51                     p[i]=1;
52                 else
53                     p[i]=0;
54         }
55         a[1]=1;isu[1]=true;
56         cout<<"Case "<<_count++<<:<<endl;
57         dfs(1,n); 
58         cout<<endl;
59     }
60     return 0;
61 }
hdu 1016   Prime Ring Problem

 

Run ID Submit Time Judge Status Problem Time Memory Language Author
01616139 2014-01-13 10:12:28 Accepted 1001 875 MS 372 KB GNU C++ freecode

 

Freecode : www.cnblogs.com/yym2013

hdu 1016 Prime Ring Problem

上一篇:mysql授权、远程访问


下一篇:MySQL技术内幕InnoDB存储引擎 读书笔记