POJ 2034 Anti-prime Sequences 素数+DFS回溯

题目链接:http://poj.org/problem?id=2034

题意

给出一个序列: {n,n+1,n+2,…,m} 现在对这个序列进行重新排序,使得每相邻2、3、。。。、d个数都是合数

题解

考虑使用回溯法,从第一个开始往后排。判断一个数num是否能够排在pos位置的方法(pos前面的数已经确定好了)是从这个数开始不断向前加一个数,只要这个和是素数就可以得到这个位置不能排这个数。
回溯法套用的就是生成全排列的那种方法。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
ol is_prime[maxp];
int prime[maxp],num;
int n,m,d;
bool visit[maxn];
int ans[maxn];
void init()
{
num=0;
memset(is_prime,true,sizeof(is_prime));
is_prime[0]=is_prime[1]=false;
for(int i=2;i<maxp;i++)
{
if(is_prime[i]) prime[num++]=i;
for(int j=0;j<num && i*prime[j]<maxp;j++)
{
is_prime[i*prime[j]]=false;
if(i%prime[j]==0) break;
}
}
}
bool judge(int pos,int nu) //判断pos位置放置num值是否可行
{
if(pos==0)
return true;
int l=pos-d+1;
if(l<0)
l=0;
int sum=nu;
for(int i=pos-1;i>=l;i--)
{
sum+=ans[i];
if(is_prime[sum])
return false;
}
return true;
}
bool dfs(int u)
{
if(u==m-n+1)
return true;
for(int i=n;i<=m;i++) //枚举每个可以插入的数
{
if(!visit[i] && judge(u,i))
{
ans[u]=i; //记录下来为考虑后面的数做准备
visit[i]=true;
if(dfs(u+1))
return true;
visit[i]=false; // 回溯
}
}
return false;
}
void solve()
{
init();
while(scanf("%d %d %d",&n,&m,&d)!=EOF)
{
if(n==0&&m==0&&d==0)
break;
memset(visit,false,sizeof(visit));
memset(ans,0,sizeof(ans));
if(dfs(0))
{
for(int i=0;i<m-n+1;i++)
{
printf("%d",ans[i]);
if(i!=m-n)
printf(",");
}
printf("\n");
}
else
printf("No anti-prime sequence exists.\n");
}
}