现在的位置: 首页 > 综合 > 正文

1016 Prime Ring Problem

2013年10月08日 ⁄ 综合 ⁄ 共 1961字 ⁄ 字号 评论关闭

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;   
}

 

 

抱歉!评论已关闭.