1457优化的几个途径

小康

这道题的意思大概如下.

小康

1..n个数字组成的环,要求任意两个数字的和为素数.

http://acm.zju.edu.cn/show_problem.php?pid=1457

一般做法,就是深度搜索,然后在搜索过程,判断某个数能否放在一个位置,即与前一个数相加的和是否为素数.
素数的判断,为第一个优化,如果每次都判断某个素是否为素数,那将浪费很多时间,我们可以实现把素数求出来.

第二个优化方式,我们可以发现,某个数,在n的范围内,他就与某几个数字和为素数.这样,我们可以在搜索过程中,搜索某个点的时候,直接搜索和他和相加为素数的素.

第三个优化,还有更快的方式,想不到.

#include<stdio.h>
int dep,n;
int can[41][41]={0};
int an[81];
int use[81];
int yes[80];
void finds()
{
int i,j,k;
k=an[dep];
dep++;
  for (i=1;i<can[k][0]+1;i++) if (use[can[k]]==1)
   {
        use[can[k]]=0;
        an[dep]=can[k];
         if (dep==n)
         {
          if (yes[an[dep]+an[1]]==1)
          {
          for (j=1;j<n;j++)
           printf(\"%d \",an[j]);
          printf(\"%d\\n\",an[n]);

           }
         } else
         finds();
        use[can[k]]=1;
   }
dep--;
}
int main(int argc, char* argv[])
{
int ncase=0,i,j,u,k;
for (i=1;i<20;i++) for (j=0;j<20;j++)     can[j]=0;
for (i=1;i<40;i++)
  {
   yes=1;
   for (j=2;j<=i /2 ;j++) if (i%j==0) {yes=0;break;};

  }

for (i=1;i<20;i++)
  for (j=i+1;j<20;j++)
  {
    k=i+j;
    if (yes[k]==1) {
     can[0]++;//
     can[can[0]]=j;//
     can[j][0]++;
     can[j][can[j][0]]=i;
    };
  }
  while ( scanf(\"%d\",&n)!=EOF)
  {
        //  if(n>17) continue;
  ncase++;
  printf(\"Case %d:\\n\",ncase);
  for (i=0;i<=20;i++) use=0;
  for (i=0;i<=n;i++) use=1;
  i=1;an=1;use[1]=0;
  dep=1;
  if (n&1==1) {
   
  } else
  finds();
  printf(\"\\n\");
  }
        return 0;
}

小康

奇数的时候是没有结果的,这个也可以节省很多时间

剑乱

#include<stdio.h>
int n;
int a[20]={1};
int prime[40];
int b[20];
void print()
{ int i;
  for(i=0;i<n-1;i++)
          printf(\"%d \",a);
  printf(\"%d\\n\",a[n-1]);



}
void search(int dep){
  int i;
  if(dep==n&&prime[a[0]+a[n-1]])
          print();
  for(i=1;i<=n;i++)
          if(!b&&prime[i+a[dep-1]]){b=1;a[dep]=i;search(dep+1);b=0;}
  




}
int main()
{
int i,dep,k=0;
  for(i=0;i<40;i++)
  prime=0;
  for(i=0;i<20;i++)
  b=0;
  b[1]=1;
  prime[1]=1;prime[2]=1;prime[3]=1;prime[5]=1;prime[7]=1;prime[11]=1;prime[13]=1;prime[17]=1;
  prime[19]=1;prime[23]=1;prime[29]=1;prime[31]=1;prime[37]=1;
while(scanf(\"%d\",&n)!=EOF)
{
  printf(\"Case %d:\\n\",++k);
  if(n&1){}
  else {

      search(1);
      printf(\"\\n\");
  }
}
return 0;
}

sheep426

还有一定是奇数和偶数相隔的，这也是为什么n为奇数时没有解得原因