首页 > 代码库 > HDU 1016 素数环问题

HDU 1016 素数环问题

2024-07-24 10:15:31   219人阅读

题目大意:

给定1-n这n个数，组成以1开头的素数环，保证相邻两个数相加均为素数

 

题目用dfs搜索再回溯，这样碰到不成立的立刻退出递归，就减少了很多步骤，不然暴力来就是n！次复杂度，肯定是超时的

每次添入数据都要判断是否相邻数相加为素数，所以我们可以提前打个素数表，这样使自己判断素数更加方便

 

 1 #include <cstdio> 2 #include <cstring> 3  4 using namespace std; 5  6 #define N 22 7 int n , a[N] , visit[N] , prime[41]; 8  9 void prime_table()10 {11     memset(prime,0,sizeof(prime));12     for(int i = 2;i<40;i++){13         if(!prime[i]){14             for(int j=i+i;j<40;j+=i)15                 prime[j] = 1;16         }17     }18 }19 20 void dfs(int x,int cnt)21 {22     visit[x] = 1;23     if(cnt == n && !prime[a[0]+a[cnt-1]]){24         printf("%d",a[0]);25         for(int i=1;i<cnt;i++)26             printf(" %d",a[i]);27         printf("\n");28     }29 30     for(int i=1;i<=n;i++){31         if(!visit[i]&& !prime[a[cnt-1]+i]){32             a[cnt] = i;33             dfs(i,cnt+1);34             visit[i]=0;//回溯35         }36     }37 }38 39 int main()40 {41     int t = 1;42     prime_table();43     while(~scanf("%d",&n))44     {45         printf("Case %d:\n",t);46 47         memset(visit,0,sizeof(visit));48         a[0] = 1;49         dfs(1,1);50         //这里一组数据做完记得换行，题目要求51         printf("\n");52         t++;53     }54 }

 

HDU 1016 素数环问题


联系
我们