2018年实训周作业——图_HDU 1016 B - Prime Ring Problem

原题链接http://acm.hdu.edu.cn/showproblem.php?pid=1016

Prime Ring Problem

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

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.

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

Source
Asia 1996, Shanghai (Mainland China)

Recommend
JGShining
题意：这个题很经典，对于一个数n，要求是编程找到所有的序列，从1~n的排列，使满足相邻两个数相加都是素数，其中第一个数永远是1，所以这里需要注意的是判断最后一个放的数和第一个数相加是不是素数。
这个题解法是DFS加回溯记忆路径，也有的题目是输出序列个数，这就需要认真读题了哦~
我的解法：
（1）首先，需要素数打表，对于本题而言，可以把素数都放在一个数组里，即int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41}（最大的数是19+20=39，所以打表到41肯定够用的）；
此外也可以用普通判断素数的办法，也就是朴素筛素数法，从2开始到根号n或者n/2枚举，如果模是0，说明有因子，那么该数就是合数（这个题数据范围很小，不会超时的）；
如果这个数据范围变大的话，我们是可以用素数筛来打表的，素数筛有四种：朴素线性筛，埃氏筛，欧拉筛和区间筛。关于四种筛法的学习，这里有详解https://blog.csdn.net/u011469138/article/details/80906423
（2）其次，我们需要路径数组和标记数组，是动态变化的，对于每一个序列要更新路径数组和该点的标记，每次对于当前点进行深搜的时候是需要恢复标记的，这样不会影响下一次搜索。
（3）在DFS中，分两块，一是判断当前路径数组里是不是达到n，这时判断一下路径数组里最后一个加第一个数1是不是素数，如果是，那么打印该序列；二是找当前位置可以放的下一个数，如果找到的话，就把这个数放进路径数组，并对该点继续深搜，找下一组解，之后，我们需要将标记恢复，找下一个当前位置的解。
（4）小技巧：就是在DFS的时候可以剪枝：如果n是奇数，是不存在素数环的，如果n是奇数的话，奇数个数多1，那么两个奇数加肯定是偶数，一定不存在宿舍环，这样减少判断，减少搜索，会快一些。

我的代码：（埃氏筛法+DFS+剪枝）

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

int prime[50];     //素数表，若为素数，则值为1，否则为0
int num[20];       //记录满足题意的路径数组，大小随n变化
int vis[20];       //标记数组，记录该点是否被访问过
int n;             //用户输入数值，表示数组总元素个数

//素数筛，1代表是素数，0代表不是素数
int getprime()
{
    for(int i=1;i<=50;i++)
    {
        prime[i] = 1;           //先将所有的都初始化为1
    }
    prime[1] = 0;               //1不是素数
    for(int i=2;i<=50;i++)      //从2开始找素数
    {
        if(prime[i]==1)         //素数的所有倍数都是合数，置为0
        {
            for(int j=i*i;j<=50;j+=i)
            {
                if(prime[j]==1)
                prime[j] = 0;
            }
        }
    }
    /*for(int i=1;i<=20;i++)
    {
        cout<<i<<" "<<prime[i]<<endl;
    }*/
}

//打印满足题意的一个解
void print()
{
    for(int i=1;i<n;i++)
    {
        cout<<num[i]<<" ";
    }
    cout<<num[n]<<endl;   //打印一个解
}

//深度优先搜索加回溯
void dfs(int cur,int cnt)   //cur代表当前已经存入数组的节点，cnt代表当前数组中的元素个数
{
    int i,j;
    //寻找没有标记的并且与当前节点相加为素数的节点
    for(i=1;i<=n;i++)
    {
        if(prime[cur+i]==1 && vis[i]==0)
        {
            vis[i] = 1;     //如果1~n中的某个数i与当前节点的值cur相加仍是素数，标记该节点，并将其加入数组
            cnt++;          //长度相应加1
            num[cnt] = i;   //将该节点i加入到路径数组num中
            dfs(i,cnt);     //搜索刚加入的节点为当前节点的下一个符合条件的节点
            vis[i] = 0;     //下一层返回时，释放刚加入的那个结点
            cnt--;          //并将其移出路径数组，数组长度键1
        }
    }
    if(cnt==n && prime[num[cnt]+1]==1)
    //如果路径中已经有n个元素，并且最后一个元素与第一个元素1的和也是素数，输出这个解
    {
        print();
    }
    //上面的函数执行完后会返回上一层
}

//主函数
int main()
{
    int count=0;
    getprime();
    while(cin>>n)
    {
        memset(vis,0,sizeof(vis));
        memset(num,0,sizeof(num));
        int cnt=1;   //记录数组长度
        vis[1]=1;    //第一个数字是1，并将该节点标记
        num[1]=1;    //路径数组中第一个数是1
        count++;     //count初值是0，每次有新的n值的时候，Case值加一
        cout<<"Case "<<count<<":"<<endl;
        if(n==1)     //如果n值是1，直接输出1
        cout<<"1"<<endl;
        if(n%2==0&&n>0)
        {
            dfs(1,1); //剪枝，当n值为偶数时才存在素数环
        }
        cout<<endl;   //格式，每种情况后输出一空行
    }
    return 0;
}