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

发表于 | 分类于 | 阅读次数:
字数统计: 483 字

题目链接：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");
	}
}