题目地址:http://xcacm.hfut.edu.cn/problem.php?id=1004

题目描述

如图所示,一个环由n个圆圈组成。把自然数1,2,…,n填入每个圆圈中,使得相邻两个圈内的数字之和为素数。

注意:第一个圆圈的数字总是1。
http://xcacm.hfut.edu.cn/oj/upload/201405/1016-1.gif

思路

我刚开始做的时候是用三层嵌套循环来做的,太复杂了也没搞出来= =

然后上网参考了一下答案,用递归比较合适。

AC代码

/*************************************************************************
    > File Name: 1004.cpp
    > Author: Netcan
    > Mail: 1469709759@qq.com 
    > Created Time: 2015/5/1 10:26:13
 ************************************************************************/

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;


static bool prime[25];
static int ans[20];
static bool mark[20];
int n=0;
void DFS(int cur) {
    if(cur == n && prime[ans[0]+ans[n-1]]) { // 如果是最后一层就输出符合要求的串
        for(int i=0; i<n; ++i)
            printf("%d ", ans[i]);
        puts("");
        return;
    }
    else 
        for(int i=2; i<=n; ++i) { // 从2开始
            if(mark[i] && prime[i+ans[cur-1]]) { // 如果当前数未被使用且符合题意
                ans[cur] = i; // 将当前数放入当前层中 
                mark[i] = false; // 标记当前数已使用
                DFS(cur+1); // 进入下一层
                mark[i] = true;
            }
        }
}
int main() {
    for(int i=1; i<=25; ++i) { // 素数打表
        int m=sqrt(i);
        int j=2;
        for(j=2;j<=m;++j) 
            if(i%j==0)
                break;
        if(j>m)
            prime[i] = true;
        else
            prime[i] = false;
    }
    int Case=0;
    memset(mark, 1, sizeof(mark));
    ans[0] = 1;
    while(scanf("%d", &n) == 1) {
        Case++;
        printf("Case %d:\n", Case);
        DFS(1);
    }
}