UVA 524 素数环Prime Ring Problem (回溯法)

太过爱你忘了你带给我的痛 2024-02-17 19:03 156阅读 0赞

啃爹的输出格式！PE了好几次！

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<cmath>
  4. using namespace std;
  5. const int maxn=16;
  6. int vis[maxn],A[maxn]; 
  7. int n;
  8. bool isp(int temp){                //判断是否为素数，是则返回true; 
  9.     int flag=1;
  10.     for(int i=2;i<=sqrt(temp);i++){
  11.         if(temp%i==0){
  12.             flag=0;break;
  13.         }
  14.     }
  15.     if(flag)return true;
  16.     else return false;
  17. }
  19. void dfs(int cur){
  20.     if(cur==n && isp(A[0]+A[n-1])){    
  21.         printf("%d",A[0]);
  22.         for(int i=1;i<n;i++)printf(" %d",A[i]);
  23.         printf("\n");
  24.     }
  25.     else for(int i=2;i<=n;i++){   //尝试放置每个数i; 
  26.         if(!vis[i] && isp(A[cur-1]+i)){ //如果i没有被使用过，并且与前一个数之和为素数 
  27.             A[cur]=i;
  28.             vis[i]=1;             //使用标志 
  29.             dfs(cur+1);
  30.             vis[i]=0;           //一定要改回 
  31.         }
  32.     }
  33. }
  34. int main(){
  35.     int count=0;
  36.     while(scanf("%d",&n)==1){
  37.         memset(vis,0,sizeof(vis));
  38.         A[0]=1;
  39.         if(count++)printf("\n");
  40.         printf("Case %d:\n",count);
  41.         dfs(1);
  42.     }
  43.     return 0;
  44. }

发表评论

表情：
评论列表 （有 0 条评论，156人围观）

还没有评论，来说两句吧...

相关阅读