hdoj 1016 Prime Ring Problem【素数环】

痛定思痛。 2022-08-08 15:58 180阅读 0赞

# Prime Ring Problem #

**Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 35007    Accepted Submission(s): 15506**  
题目大意：输入一个整数n，表示有n个数【从1 到 n】，然后把这 n 个数排在一个圆环上，使得相邻的两个数之和为一个素数；

要求求出所有的排序，并打印出来；

每个案例间有个空行；

![1016-1.gif][]

思路：首先，遍历会超时，所以选择dfs；

因为规定输出第一个为1，从2开始；先定义三个数组arr\[\](存放素数环)，vis\[\](记录数字是否已被访问)，pn\[\](素数表)；

先打素数表，然后arr与vis清零；

因为第一位是1，所以第二位必定是偶数，则奇数位是奇数，偶数位为偶数；

第二位从i=2 开始，遍历到i<=n，

如果与前一位之和为素数，把该数表位已访问，接着判断下一位（第三位）

如果与前一位之和不是素数，则i+=2;

第三位从i=3开始，遍历到i<=n;

if(arr\[i-1\]+arr\[i\]是素数)\{  vis\[i\]=1;  dfs(i+1); .....\}

.类推

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

已Accept代码【c++提交】

#include <cstdio>
    #include <cstring>
    using namespace std;
    int n, m;
    int arr[22];			//存放素数环 
    int vis[22];			//记录元素是否已访问 
    int pn[41];			//素数表 
    
    void PN() {				//大表--素数表 
    	memset(pn, 0, sizeof(pn));
    	pn[1] = 1;
    	for(int i = 2; i * i < 41; i++)
    		for(int j = i * i; j < 41; j +=i)
    			pn[j] = 1;
    }
    
    void dfs(int i) {
    	int k, e;
    	if(i == n) {			//若当前位是第n位 
    		for(e = 2; vis[e] != 0; e++);
    		if(pn[e + 1] == 0 && pn[e + arr[i - 1]] == 0) { //判断该位与第一位&&与前一位的和是否都是素数 
    			arr[n] = e;
    			for(int p = 1; p < n ; p++)
    				printf("%d ", arr[p]);
    			printf("%d\n", arr[n]);
    			arr[n] = 0;
    			return ;
    		}
    		return ;
    	}
    	if(i % 2) {				//当前是奇数位 
    		for(int j = 3;  j <= n; j += 2) {
    			if(vis[j] == 1)
    				continue;		//如果已被访问，结束本次循环 
    			k = arr[i - 1] + j; 
    			if(pn[k] == 0) {	//判断当前位于前一位的和是否为素数 
    				vis[j] = 1;
    				arr[i] = j;
    				dfs(i + 1);
    				vis[j] = 0;
    				arr[i] = 0;
    			}
    		}
    	}
    	else {					//当前是偶数位
    		for(int t = 2; t <= n; t += 2) {
    			if(vis[t] == 1)
    				continue;		//如果已被访问，结束本次循环 
    			k = arr[i - 1] + t;
    			if(pn[k] == 0) {	//判断当前位于前一位的和是否为素数 
    				vis[t] = 1;
    				arr[i] = t;
    				dfs(i + 1);
    				vis[t] = 0;
    				arr[i] = 0;
    			}
    		}
    	}
    }
    
    int main() {
    	int q = 1;
    	PN();
    	while(scanf("%d", &n) != EOF) {
    		printf("Case %d:\n", q++);
    		memset(arr, 0, sizeof(arr));
    		arr[1] = 1;
    		dfs(2);
    		printf("\n");			//注意输出格式 
    	}
    	return 0;
    }

[1016-1.gif]: /images/20220731/58560ae4e1974c059d328a46a77ae38a.png