MYF

UVa 524 Prime Ring Problem

Posted on | In | | Visitors

题目链接

UVa 524

方法：DFS

题目分析

题目大意

一个数字n，将1～n这n个数排成一个环，使任意两个相邻的数字相加为一个素数。

解析

怎么想到的DFS，我也不知道。
思路是这样：先建一个类似于邻接表的表g[][]，比如g[i]这一行，就储存所有和i相加为素数的数，g[i］这一行的元素个数储存在head[i]中。因为这个环一定是从1开始的，所以从1开始dfs。每次dfs将数字标记上已访问，记录层数，也就是DFS参数中的moves，并且将数字放在结果数组ans[]中。如果到最后一层，也就是n个数全部访问之后，判断最后一个数字和第一个数(也就是1)相加是不是素数，如果是素数，输出这一串数字。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define PI acos(-1)
#define debug         printf("Hi----------\n")
#define eps 1e-8
#define INF 0x3f3f3f3f
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
#define maxn 10005
int vis[50];
int n,pos;
int g[32][32];
int head[32];
int ans[32];
int isPrime(int num)
{
    if(1 == num || 0 == num)
        return 0;
    int s,t;
    s = sqrt(num);
    for (t = 2; t <= s; t++)
        if (num%t==0) break;
    if (t >= s + 1) return 1;
    else return 0;
}
void init(){
    memset(g, 0, sizeof(g));
    memset(head, 0, sizeof(head));
    memset(vis, 0, sizeof(vis));
    memset(ans, 0, sizeof(ans));
    vis[1]=0;
    pos=2;
    
    int index;
    for (int i=1; i<=n; i++) {
        index=1;
        for (int j=1; j<=n; j++) {
            if (i!=j&&isPrime(i+j)) {
                g[i][index++]=j;
            }
        }
        head[i]=index;
    }
}
void showans(){
    for (int i=1; i<=n; i++) {
        printf("%d",ans[i]);
        if (i!=n) {
            printf(" ");
        }
        else
            printf("\n");
    }
}
void dfs(int x,int moves){
    vis[x]=1;
    ans[moves]=x;
    if (moves==n&&isPrime(x+1))
        showans();
    for (int i=1; i<head[x]; i++) {
        int tmp=g[x][i];
        if (vis[tmp]==0) {
            dfs(tmp, moves+1);
        }
    }
    vis[x]=0;
}
int main(){
    bool flag=false;
    int cas=1;
    while (scanf("%d",&n)!=EOF) {
        if (flag) printf("\n");
        printf("Case %d:\n",cas++);
        init();
        dfs(1, 1);
        flag=true;
    }
    return 0;
}