NYOJ 488-素数环

时间限制:1000 ms | 内存限制:65535 KB | 难度:2

描述

有一个整数n,把从1到n的数字无重复的排列成环,且使每相邻两个数(包括首尾)的和都为素数,称为素数环。
为了简便起见,我们规定每个素数环都从1开始。例如,下图就是6的一个素数环。

素数环

输入

有多组测试数据,每组输入一个$n(0<n<20),n=0$表示输入结束。

输出

每组第一行输出对应的Case序号,从1开始。
如果存在满足题意叙述的素数环,从小到大输出。
否则输出No Answer。

样例输入

6
8
3
0

样例输出

Case 1:
1 4 3 2 5 6
1 6 5 2 3 4
Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
Case 3:
No Answer

题目来源

http://acm.nyist.net/JudgeOnline/problem.php?pid=488

算法思路

这个素数环有n个位置,每个位置可以填写的整数为1~n,共n种可能,可以对每个位置从1开始进行试探,结束条件是正在试探的数满足如下条件:

  1. 与已经填写到素数环中的整数不重复;
  2. 与前面相邻的整数之和是一个素数;
  3. 最后一个填写到的素数环中的整数与第一个填写的整数之和是一个素数。

在填写第k个位置时,如果满足上述约束条件,则继续填写第k+1个位置;如果1~n都无法填写到第k个位置,则取消对第k个位置的填写,回溯到第k-1个位置。

算法实现

程序1(只求出局部解)

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
#include <iostream>
#include <math.h>
using namespace std;
int *a;
int num = 1;

int Prime(int x){//判断整数x是否为素数
int i,n;
n = (int)sqrt(x);
for(i=2; i<=n; i++)
if(x%i==0) return 0;
return 1;
}
int Check(int k, int n){//判断位置k的填写是否满足约束条件
int flag = 0;
for(int i=0; i<k; i++)//判断是否重复
if(a[i]==a[k]) return 0;
flag = Prime(a[k]+a[k-1]);//判断相邻数之和是否为素数
if(flag==1 && k==n-1)//判断第一个和最后一个之和是否为素数
flag = Prime(a[k]+a[0]);
return flag;
}
void PrimeCircle(int n){//填写1~n共n个整数
int i,k;
a = new int[n]; //初始化数组
for(i=0; i<n; i++) a[i] = 0;
a[0] = 1; k = 1;//指定第0个位置填写1
while(k>=1){
a[k] = a[k]+1;
while(a[k]<=n)
if(Check(k,n)==1) break;//位置k可以填写整数a[k]
else a[k] = a[k]+1;//试探下一个数
if(a[k]<=n && k==n-1){//求解完毕,输出解
cout<<"Case "<<(num++)<<": "<<endl;
for(i=0; i<n; i++) cout<<a[i]<<" ";
cout<<endl;
return;
}
if(a[k]<=n && k<n-1) k = k+1;//填写下一个位置
else a[k--]=0;
}
delete a;
}


int main(){
int n = 1;
while(n){
cin>>n;
PrimeCircle(n);
}
}

问题

  1. 并没有真正找到所有满足题意叙述的素数环,只是找到部分解而已。
  2. 要真正找到所有解,应该加入一串标记,标记1~n哪些数被用过。
  3. 对数组a使用了太多次的newdelete,最后可能超时。

程序2(正确程序~)

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

#include <iostream>
#include <math.h>
using namespace std;
int n,flag,a[21],res[21];//res用来判断是否重复使用

int Prime(int x){//判断整数x是否为素数
if(x==1) return 0;
for(int i=2; i<=x/2; i++)
if(x%i==0) return 0;
return 1;
}
void PrimeCircle(int now){
int i;
if(now==n&&Prime(a[n-1]+a[n])){//求解完毕,输出解
flag = 0;
for(i=0; i<n; i++) cout<<a[i]<<" ";
cout<<endl;
}else{
for(i=2; i<=n; i++){
if(!res[i]&&Prime(i+a[now-1])){
res[i] = 1;
a[now] = i;
PrimeCircle(now+1);//一直递归下去,进行搜索
res[i] = 0;//无论是否搜索到,后续将回溯
}
}
}
}

int main(){
int num = 1;
while(cin>>n,n){
flag = 1;
a[0] = a[n] = 1;//最后一个数即为第一个数
cout<<"Case "<<(num++)<<":"<<endl;
if((n-1)&1||n==1)//(n-1)&1 表示n-1与1按位相与,判断n-1是否为奇数
PrimeCircle(1);
if(flag) cout<<"No Answer"<<endl;
}
return 0;
}

改进

  1. 加入了res用来标记判断1~n哪些被重复使用;
  2. 数组a固定长度,且最后一个数a[n]即为第一个数a[0],只有这两个数重复,对后续判断有利。
  3. 利用位操作符可以排除奇数个数n【因为只有奇数和偶数相加才会是素数, 所以总数为奇数的素数环,不可能存在】,对解空间树再剪枝,提高效率。
  4. 活用递归搜索与res数组,才能找到所有的解。
  5. 其实20以内两两相加的素数可以直接求出来,存为一串数组,效率将更高。

参考资料

算法设计与分析(第2版)
题目488优秀程序:运行号381387——刘玉涛

文章目录
  1. 1. 算法思路
  2. 2. 算法实现
    1. 2.1. 程序1(只求出局部解)
    2. 2.2. 程序2(正确程序~)
  • 参考资料
  • 20160318-acm-9/

    本页二维码