欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU 1016 Prime Ring Problem

程序员文章站 2022-07-10 09:18:44
...

原题传送门: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): 25493    Accepted Submission(s): 11369


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
            
    
    博客分类: ACM HDU1016DFS回溯递归 
 

 

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
 

 

Recommend
JGShining
 
分析:这道题目就是用深度优先遍历的方式来解决的。首先构造素数表,这个我就不多解释了,网上代码和解释多的是。由于环的开始点被定死的,都是1,1先入栈,标记为访问过的数字,用for循环遍历给定范围内的所有数字,遇到与1相加是素数的,停止,就将它放入栈中,标记为访问过的数字,进入DFS函数操作,DFS函数也就是一个迭代过程,用for 循环遍历所有未访问过的 数字,如果与栈顶元素相加为素数,则停止,放入栈中,标记为访问过的数字,一直迭代下去,一直到没有可以用的数字为止(PS:没有可以用的数字就是 情况1:所有数字都被访问过,也就是全部入栈 ;情况2:不是所有数字都被访问过,但是剩下的数字中没有能够和栈顶元素相加和为素数的了)如果此时栈内元素==n,那么说明当前序列符合题目要求,则从栈底到栈顶依次输出所有元素。如果此时栈内元素!=n,说明当前序列不可能是符合题意的子序列,因此必须回溯!!!
回溯是在DFS()后,回溯必须注意要把visit[]中相应的元素还原为未访问(比如说你从1 2 3 4 5 中5不合题意,回溯那么5必须标记为未访问,因为你要得到的序列是 1 2 3 4),并且弹出栈顶元素。
源代码:
//深度优先搜索(DFS)
#include <stdio.h>
#include <string.h>
#include <stack>
using namespace std;

const int MAXN = 50;
const int MAXNA = 21;
bool isPrime[MAXN];
bool isVis[MAXNA];
int arstack[MAXNA];
int total,n;
stack<int> ans;
stack<int> temp;
//初始素数表
void initPrime(){
    memset(isPrime,1,sizeof(isPrime));
    isPrime[0] = false;
    isPrime[1] = false;
    for(int i=2;i<MAXN;i++){
        if(isPrime[i]){
            for(int j = 2;j*i<=MAXN;j++)
            isPrime[j*i] = false;
        }
    }
}
void DFS(int x,int count){
    if(count == n && isPrime[x+1]){
        int i=0;
        temp = ans;
        while(!temp.empty()){

            arstack[i++]= temp.top();
            temp.pop();
        }
        for(int j=i-1;j>0;j--){
            printf("%d ",arstack[j]);
        }
        printf("%d\n",arstack[0]);
        return;
    }
    else{

        for(int d=1;d<=n;d++){
            if(!isVis[d] && isPrime[d+x]){
                isVis[d]=1;
                ans.push(d);
                DFS(d,count+1);
                ans.pop();
                isVis[d]=0;

            }
        }
    }
}
main(){
    initPrime();
    int k=1;
    while(scanf("%d",&n)!=EOF){
        while(!ans.empty())ans.pop();
        memset(isVis,0,sizeof(isVis));
        printf("Case %d:\n",k++);
        isVis[1] = 1;
        ans.push(1);
        for(int i=2;i<=n;i++){
            total = 1;
            if(!isVis[i]&&isPrime[1+i]){
                isVis[i] = 1;
                ans.push(i);
                DFS(i,total+1);
                ans.pop();
                isVis[i] = 0;
            }
        }
        printf("\n");
    }

}