1016 Prime Ring Problem
这道题是简单的搜索,但是题目还是不错的
本来想用STACK来实现,但是发现不是很好控制
就是就用DFS实现回溯,一次AC
AC CODE :
// 1016 Prime Ring Problem BY JQ, 2009.5.20 23:53:00
#include <iostream.h>
int stack[21];
#define N 15;
bool a[15];
int p[15];
int top,n;
bool hash[50]; //记录某数是否为素数
bool used[50];
void Prime2(int n) //线性法,参数表示要打多少内的素数
{
memset(a, 0, n*sizeof(a[0]));
memset(hash,0,sizeof(hash));
int num = 0, i, j;
for(i = 2; i < n; ++i)
{
if(!(a[i]))
{
p[num++] = i;
hash[i] = 1;
}
for(j = 0; (j<num && i*p[j]<n); ++j)
{
a[i*p[j]] = 1;
if(!(i%p[j])) break;
}
}
}
//1 3 5 7 11 13 17 19 23 29 31 37 41
int table[21][20];
int tlen[21];
void output()
{
int i;
for (i=0;i<n-1;i++)
printf("%d ",stack[i]);
printf("%d/n",stack[n-1]);
}
void dfs(int x) //传入栈顶的数
{
int i;
used[x] = 1;
stack[top++] = x;
if (top == n) //如过数的用了
{
//那么判断是不是合法解,如果是,输出,如果否,回溯
if (hash[stack[top-1] + 1]) //如果是和是素数 ,那么合法,输出
output();
return;
}
//遍历下一跳
for (i=0;i<tlen[x];i++)
{
if (!used[table[x][i]]) // 如果下一条没有用过
{
dfs(table[x][i]);
// 回溯:
used[table[x][i]] = 0;
top--;
}
}
}
int main()
{
int i,j,k,m,t;
Prime2(45);
// for (i=0;i<13;i++) printf("%d ",p[i]);
//记录跳法:
int cas = 0;
while (scanf("%d",&n)!=EOF)
{
int cnt;
for (i=1;i<=n;i++)
{
cnt = 0;
if (i%2) j = 2; else j =1;
for (;j<=n;j+=2)
{
if (hash[i+j]) //如果是素数,那么记录一下
table[i][cnt++] = j;
}
tlen[i] = cnt;
}
cas ++;
printf("Case %d:/n",cas);
if (n == 1) {printf("1/n");continue;}
memset(used,0,sizeof(used));
top = 0;
//一种剪枝策略:
//在配对的时候一定是奇偶数交叉配对,这样便简化问题到10!的规模
//以此可的推广出素数跳的剪枝
//如1的时候可以得旁边的数为2,4,6,10,12, ...
//可求到20的跳法,记录起来,打表---这样保证了第次选择都是合法的
//只要判断最后一个是否合法
//回溯法,递归实现所有情况的遍历
dfs(1);
printf("/n");
}
return 0;
}