UVa 524 Prime Ring Problem【回溯】

题意：给出n,把从1到n排成一个环，输出相邻两个数的和为素数的序列

照着紫书敲的，大概就是这个地方需要注意下，初始化的时候a[0]=1,然后dfs(1),从第1个位置开始搜

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<stack>

 #include<vector>

 #include<map>

 #include<queue>

 #include<algorithm>

 #define mod=1e9+7;

 using namespace std;

 typedef long long LL;

 int a[],vis[],isp[];

 int n;

 void is_prime(){

     isp[]=isp[]=;

     for(int i=;i<=;i++){

         if(isp[i]==){

             for(int j=i*;j<=;j+=i)

             isp[j]=;

         }

     }

 }

 void dfs(int cur){

     int i;

     if(cur==n&&!isp[a[]+a[n-]]){

         for( i=;i<n-;i++) printf("%d ",a[i]);

         printf("%d\n",a[i]);

     }

     else for(i=;i<=n;i++)

     if(!vis[i]&&!isp[i+a[cur-]]){

         a[cur]=i;

         vis[i]=;

         dfs(cur+);

         vis[i]=;

     }

 }

 int main(){

     int t=;

     is_prime();

     while(cin>>n){

         memset(vis,,sizeof(vis));

        a[] = ;

         vis[] = ;

         if(t) printf("\n");

         printf("Case %d:\n", ++t);

         dfs();

     }

     return ;

 }

自己写的时候，直接是dfs(0),什么都输不出来，可是为什么是这样呢= = 学习回溯的第一题目 = = 再好好理解- -

巴特西

UVa 524 Prime Ring Problem【回溯】

最新文章

热门文章