首页 > 代码库 > HDU-1016【素数环】
HDU-1016【素数环】
题意：本题题意就是构成一个素数环。即相邻两数之和要为素数。环的元素个数在1到20之间。
素数-只能被1和它本身整除的数
输入6就是1-6排成一个相邻数相加是素数；环，第一个和最后一个加起来也要是素数
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
/*su shu huan*/#include <iostream>#include <stdio.h>#include <string.h>#include <math.h>int a[22],n,b[22]={1},k;int num[12] = {2,3,5,7,11,13,17,19,23,29,31,37},nu[40];int dfs2(int m){ int i; if(m==n+1&&nu[b[1]+b[n]]==1) { for(i=1;i<n;i++) printf("%d ",b[i]); printf("%d\n",b[n]); } else { for(i=2;i<=n;i++) { if(a[i]==1&&nu[i+b[m-1]]) { //m++; b[m++]=i; a[i]=0; dfs2(m); a[i]=1; m--; } } } return 0;}int dfs(int m){ int t=0,i; for(i=1;i<=n;i++) { if(a[i]==1) { t=1;break; //printf("-A-");break; } } //printf("t=%d\n",t); if(t==0&&nu[b[1]+b[n]]==1) { for(i=0;i<n-1;i++) printf("%d ",b[i+1]); printf("%d\n",b[n]); } if(t==0) { for(i=2;i<=n;i++) b[i]=0; k=1;b[1]=1; return 0; } for(i=2;i<=n;i++) { if(a[i]==1&&nu[i+m]==1) {printf("-%d-\n",i); a[i]=0; b[++k]=i; dfs(i); a[i]=1; b[k]=0; k--; } } for(i=2;i<=n;i++) b[i]=0; k=1;b[1]=1; return 0;}int main(){ int i; k=1;b[1]=1; for(i=0;i<12;i++) nu[num[i]]=1; scanf("%d",&n); for(i=2;i<=n;i++) a[i]=1; a[1]=0;b[1]=1; dfs2(2); return 0;}
//全部搜索后符合题意的输出，然后回退一步，在回退一部，直到回到第一步，并且第一步全部循环了
//核心思想，回退的时候所有状态都还原
HDU-1016【素数环】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。