大家好，欢迎来到IT知识分享网。
题目链接 ：http://acm.xidian.edu.cn/problem.php?cid=1041&pid=4
dfs题目，关键在于剪枝，题目要求两相邻数之和为素数，已知奇数加奇数，偶数加偶数一定非素数，若n为奇数，围成环后定会有两个相邻数为奇数，所以n为奇数可直接减掉；
在dfs内，可对上一个数进行奇偶判断，在下一个数放置时分别放置奇偶，**最后一个数还要与初始数判断，因为是环状，且按字典序输出，所以可以将第一个数直接定为1；
题目n的范围较小，可用一个数组直接记录所有素数；
1 #include<stdio.h> 2 #include<memory.h> 3 4 int n; 5 int vis[20]; 6 int A[20]; 7 8 int Prime[30] = {0}; 9 10 void dfs(int cur) 11 { 12 if(cur == n) //判断是否用完所有数字 13 { 14 if(A[cur] % 2 == 0 && Prime[A[cur]+ 1]) //环尾数字要和换首判断 15 { 16 for (int i = 1;i <= n;i++) //输出 17 { 18 if(i == 1) //处理数据间空格 19 printf("%d",A[i]); 20 else 21 printf(" %d",A[i]); 22 } 23 printf("\n"); 24 } 25 } 26 if(A[cur] % 2 == 0) //奇偶判断剪枝 27 { 28 for(int i = 3;i <= n;i = i + 2 ) 29 { 30 if(Prime[A[cur]+ i]&& vis[i] == 0) 31 { 32 A[cur + 1] = i; 33 vis[i] = 1; //被使用后标记 34 dfs(cur+1); 35 vis[i] = 0; //恢复 36 } 37 } 38 } 39 if(A[cur] % 2 != 0) 40 { 41 for(int i = 2;i <= n;i = i + 2 ) 42 { 43 if(Prime[A[cur]+ i]&& vis[i] == 0) 44 { 45 A[cur + 1] = i; 46 vis[i] = 1; 47 dfs(cur+1); 48 vis[i] = 0; 49 } 50 } 51 } 52 53 } 54 55 56 57 58 int main() 59 { 60 Prime[3] = Prime[5] = Prime[7] = Prime[11] = Prime[13] = Prime[17] = Prime[19] = Prime[23] = Prime[29] = Prime[31] = 1; 61 int T = 0; 62 while(scanf("%d",&n) != EOF) 63 { 64 memset(vis,0,sizeof(vis)); 65 if(T != 0) 66 printf("\n"); //处理两组数据间空一行 67 printf("Case %d:\n",++T); 68 if(n % 2 != 0) 69 { 70 continue; 71 } 72 A[1] = 1; //环首直接标1 73 vis[1] = 1; 74 dfs(1); 75 } 76 return 0; 77 }
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/32248.html
