1457优化的几个途径
这道题的意思大概如下. 1..n个数字组成的环,要求任意两个数字的和为素数.http://acm.zju.edu.cn/show_problem.php?pid=1457
一般做法,就是深度搜索,然后在搜索过程,判断某个数能否放在一个位置,即与前一个数相加的和是否为素数.
素数的判断,为第一个优化,如果每次都判断某个素是否为素数,那将浪费很多时间,我们可以实现把素数求出来.
第二个优化方式,我们可以发现,某个数,在n的范围内,他就与某几个数字和为素数.这样,我们可以在搜索过程中,搜索某个点的时候,直接搜索和他和相加为素数的素.
第三个优化,还有更快的方式,想不到.
#include<stdio.h>
int dep,n;
int can={0};
int an;
int use;
int yes;
void finds()
{
int i,j,k;
k=an;
dep++;
for (i=1;i<can+1;i++) if (use]==1)
{
use]=0;
an=can;
if (dep==n)
{
if (yes+an]==1)
{
for (j=1;j<n;j++)
printf("%d ",an);
printf("%d\n",an);
}
} else
finds();
use]=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=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==1) {
can++;//
can]=j;//
can++;
can]=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=0;
dep=1;
if (n&1==1) {
} else
finds();
printf("\n");
}
return 0;
} 奇数的时候是没有结果的,这个也可以节省很多时间 #include<stdio.h>
int n;
int a={1};
int prime;
int b;
void print()
{ int i;
for(i=0;i<n-1;i++)
printf("%d ",a);
printf("%d\n",a);
}
void search(int dep){
int i;
if(dep==n&&prime+a])
print();
for(i=1;i<=n;i++)
if(!b&&prime]){b=1;a=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;
prime=1;prime=1;prime=1;prime=1;prime=1;prime=1;prime=1;prime=1;
prime=1;prime=1;prime=1;prime=1;prime=1;
while(scanf("%d",&n)!=EOF)
{
printf("Case %d:\n",++k);
if(n&1){}
else {
search(1);
printf("\n");
}
}
return 0;
} 还有一定是奇数和偶数相隔的，这也是为什么n为奇数时没有解得原因
页:
[1]