hdu1016 素数环

xiaoxiao2021-02-28  16

第一种:DFS法

#include<stdio.h>

int num[21],mark[21],n; int prime_num[12]={2,3,5,7,11,13,17,19,23,29,31,37}; int is_prime(int a) { for(int i=0;i<12;i++) if(a==prime_num[i]) return 1; return 0; } void print_num() { for(int i=1;i<n;i++) printf("%d ",num[i]); printf("%d",num[n]); } int dfs(int pre,int post,int flag) { //如果不符合,直接返回 if(!is_prime(pre+post)) return 0; num[flag]=post; if(flag==n&&is_prime(post+1))//判断长度是否达到n且最后一个数加上环的起点1是否是素数  { print_num(); printf("\n"); return 1; mark[post]=0;//把这个数字标记成0表示已经用过了 for(int i=2;i<=n;i++)//开始搜索下一位  if(mark[i]!=0&&dfs(post,i,flag+1)) break; mark[post]=1;//标记位回复原状,因为没用上  return 0; } int main() { int ca=1; while(scanf("%d",&n)!=EOF&&n) { printf("Case %d:\n",ca++); for(int i=1;i<=n;i++) mark[i]=1;//初始化标记数组  num[1]=1; if(n==1) printf("1\n"); else if(n%2)//不存在长度大于1的奇数环  printf("No Answer\n"); else { for(int i=2;i<=n;i++) dfs(1,i,2);//(前面的数,之后的数,序数(长度))  } } return 0;

}

第二种 回溯法

#include<iostream>#include<string.h>#define N 25#define M 40using namespace std;bool is_prime[M],Visited[N];int n,test,ans[N];bool prime(int n){ if(n==1) return false; if(n==2||n==3) return true; int i; for(i=2;i<n;i++)   if(n%i==0)      return false; return true;}void work(int k){ int i; if(k==n+1)//搜索到了足够的元素,结束并输出。  { if(!is_prime[ans[n]+ans[1]]) return ; for(i=1;i<=n-1;i++) cout<<ans[i]<<" "; cout<<ans[i]<<endl; return; } for(i=2;i<=n;i++) { if(!Visited[i]&&is_prime[ans[k-1]+i]) { Visited[i]=true;//把这个数字标记成true表示已经用过了 ans[k]=i; work(k+1); Visited[i]=false;//标记恢复原状,因为没用上   } }   int main() { int i;  test=1;   for(i=1;i<M;i++) is_prime[i]=prime(i);  while(cin>>n)  { ans[1]=1; memset(Visited,false,sizeof(Visited)); cout<<"Case "<<test<<":"<<endl; work(2); test++; cout<<endl;  }   return 0; }

转载请注明原文地址: https://www.6miu.com/read-2450379.html

最新回复(0)