hdu1016_Prime_Ring_Problem(经典dfs)

本文主要是介绍hdu1016_Prime_Ring_Problem(经典dfs)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定一个n，将1到n的数字填入一个圈中。相邻的数字之和必须为素数。输出有一个要求就是先将所有的情况的顺时针数列输出，之后将所有的情况的逆时针情况输出。开始的想法是必须将结果存起来才能使得输出满足要求。在编程过程中发现并不一定要将符合条件的结果存起来，因为在深度优先遍历的过程中每一位的可能情况是有小到大的所以所有的情况都能得到无论是顺时针的还是逆时针的都可以。而且满足题目的要求先顺时针后逆时针。对于1 和 2 这种特殊的情况，只有一种结果因此不能输出两次，这是题目的意思没有讲到位的缘故。hdu1016

#include<iostream>
#include<algorithm>
using namespace std;int n;
int case_num = 0;
int ans[22];
bool flag[22];void dfs(int t)
{if(t>n-1){int re = ans[n-1]+1;if(re==3||re==5||re==7||re==11||re==13||re==17||re==19||re==23||re==29||re==31||re==37){                                           for(int i=0;i<n-1;i++)printf("%d ",ans[i]);printf("%d\n",ans[n-1]);}return ;}bool jo = ans[t-1]%2;int i=jo+1;for(;i<=n;i+=2)if(flag[i]){int sum=ans[t-1]+i;if(sum==3||sum==5||sum==7||sum==11||sum==13||sum==17||sum==19||sum==23||sum==29||sum==31||sum==37){flag[i]=false;ans[t]=i;dfs(t+1);flag[i]=true;                                                              }       }
}int main()
{ans[0]=1;while(scanf("%d",&n)!=EOF){case_num++;printf("Case %d:\n",case_num);flag[1]=false;for(int i=2;i<=n;i++)flag[i]=true;dfs(1);putchar(10);}return 0;
}