我前面的版本就是将数据拆分成数千个文件的,不过效果不好.所以现在改成少量几个大文件,然后用一个很大的hash值决定保存在文件的位置,不过结果效果同样不好.
没有想到移植到windows以后,速度又低了很多倍,看来这方面的确Windows不行.
如果用小文件
比如，仅考虑前两组4字母组合
显然，每个文件的总可能解是能计算得到的
用个大文件，对每组双4字母组合与刘足够的空间
遇到需要保存的
建立个索引文件，保存每个组在大文件里的位置偏移
:)
不过这个文件可能比较大了
编了一个小程序，会随机产生一些解（只产生大于等于23的解），我的机器太慢了，而且最近编程总是犯错误，所以请大家测试一下。
直接运行就可以了，我这里一般1小时产生一个23的解。
原帖由 zgg___ 于 2008-11-12 17:24 发表 http://bbs.emath.ac.cn/images/common/back.gif
编了一个小程序，会随机产生一些解（只产生大于等于23的解），我的机器太慢了，而且最近编程总是犯错误，所以请大家测试一下。
直接运行就可以了，我这里一般1小时产生一个23的解。
是产生问题二的解吧?
问题在于边数比较多的时候,问题二的解是问题一的解的概率非常低.
以前面17颗树情况为例子,我曾用贪心法产生了数万个16行的问题二的解,结果没有一个是问题一的解,这也是为什么我前面会猜测17颗树时最多15行
是问题一的解。
我尝试了一种方法，用来判断某种的组合（下面简称）是不是能画出来，也就是能不能满足问题一。这也就是我为什么想要一些测试数据。
求解的过程是：
=空;
for(;;)
{
第一步：将随机增加一组XXXX，使之依旧满足问题二；如果不能再增加了，就输出;
第二步：判断是不是满足问题一；如果不满足就重做上一步；
}
就这样得到1组结果。我刚才将程序运行了大约1个小时，随机搜索了100000组解，从18到22的解分布为：272,14464,60830,23775,659，其它的解没有。
我建议与其搜索20颗树情况，不如现在先搜索18颗19颗树的问题。
你判断是否能够满足问题一用什么方法？如果有比较高效的方法很重要，我觉得我现在的程序太慢了一些。
另外对于各种情况，通常平均多少个问题2的结果可以有对应的问题2的解呢？
是否能简化问题二的解
把同构的去掉
另外，是否总有一些模式无解
如果有很多模式
能快速的淘汰一批解
我把代码贴上来吧。编写的比较乱。上面发的可执行文件去掉了写盘的部分。
其中conf()和ssn()是用来判断的部分。
现在还是不敢确定算法判断是不是正确，但是如果和mathe程序的判断结果一致就比较对了。呵呵。// n-13.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<conio.h>
#include<stdlib.h>
#include<time.h>
#define M 4845
unsigned ddy={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288};
unsigned z_xs,z_ans,z_z,z_x;
int z_xsn,z_ansn,z_zn;
int show(unsigned d)
{
unsigned i;
for(i=0;i<20;i++)if(d&ddy)printf("%c",'A'+i);
return 0;
}
int shows(unsigned *d,int dn)
{
int i;
printf("[");
if(dn>0)
{
for(i=0;i<dn-1;i++){show(d);printf("-");}
show(d);
}
printf("]\n");
return 0;
}
int fshow(FILE *fp,unsigned d)
{
unsigned i;
for(i=0;i<20;i++)if(d&ddy)fprintf(fp,"%c",'A'+i);
return 0;
}
int fshows(FILE *fp,unsigned *d,int dn)
{
int i;
fprintf(fp,"[");
if(dn>0)
{
for(i=0;i<dn-1;i++){fshow(fp,d);fprintf(fp,"-");}
fshow(fp,d);
}
fprintf(fp,"]\n");
return 0;
}
int init()
{
int i1,i2,i3,i4;
z_zn=0;
for(i1=0;i1<17;i1++)
for(i2=i1+1;i2<18;i2++)
for(i3=i2+1;i3<19;i3++)
for(i4=i3+1;i4<20;i4++)
{
z_z=ddy|ddy|ddy|ddy;
z_zn++;
}
return 0;
}
int ssn(unsigned *qtx,int qtxn,unsigned *ans)
{
unsigned lxz,sxz1,sxz2,sxz3,sjx,sjd1,sjd2,sjxl1,sjxl2,sjxl3;
int i,i1,i2,i3,k1,k2,lxzn,sjxn,ansn;
unsigned z,zz,z1,z2,z3,sa1,sa2,sa3,sb1,sb2,sb3;
ansn=0;
for(z=1;z<=524288;z*=2)
{
lxzn=0;for(i=0;i<qtxn;i++)if(z&qtx){lxz=qtx^z;lxzn++;}
for(i1=0;i1<lxzn-2;i1++)
for(i2=i1+1;i2<lxzn-1;i2++)
for(i3=i2+1;i3<lxzn;i3++)
{
sxz1=lxz;sxz2=lxz;sxz3=lxz;
sjxn=0;
for(z1=1;z1<=524288;z1*=2)
{ if((z1&sxz1)==0)continue;
for(z2=1;z2<=524288;z2*=2)
{ if((z2&sxz2)==0)continue;
for(z3=1;z3<=524288;z3*=2)
{ if((z3&sxz3)==0)continue;
zz=z1|z2|z3;
for(i=0;i<qtxn;i++)if(zz==(zz&qtx))break;if(i<qtxn)continue;
for(i=0;i<qtxn;i++)if(((z2&qtx)!=0)&&((z3&qtx)!=0)){sjxl1=qtx&(~z2)&(~z3);break;}if(i==qtxn)continue;
for(i=0;i<qtxn;i++)if(((z1&qtx)!=0)&&((z3&qtx)!=0)){sjxl2=qtx&(~z1)&(~z3);break;}if(i==qtxn)continue;
for(i=0;i<qtxn;i++)if(((z1&qtx)!=0)&&((z2&qtx)!=0)){sjxl3=qtx&(~z1)&(~z2);break;}if(i==qtxn)continue;
sjx=zz;sjxn++;
}}}
for(k1=0;k1<sjxn-1;k1++)
for(k2=k1+1;k2<sjxn;k2++)
{
sjd1=sjx;sjd2=sjx;
if(sjd1&sjd2)continue;
sa1=sjxl1;sa2=sjxl2;sa3=sjxl3;
sb1=sjxl1;sb2=sjxl2;sb3=sjxl3;
if((sa1&sb1)!=0&&(sa2&sb2)!=0&&(sa3&sb3)!=0){zz=(sa1&sb1)|(sa2&sb2)|(sa3&sb3);
for(i=0;i<qtxn;i++)if(zz==(zz&qtx))break;if(i==qtxn){ans=zz;ansn++;}}
}
}
}
return ansn;
}
int ztoz(unsigned *z0,unsigned *z,int zn)
{
int i;
for(i=0;i<zn;i++)z=z0;
return zn;
}
int sdcd(unsigned *z,int zn)
{
int i,j,rn;
if(zn<=1)return zn;
rn=1;
for(i=1;i<zn;i++)
{
for(j=0;j<rn;j++)if(z==z)break;
if(j==rn){z=z;rn++;}
}
return rn;
}
int nu(unsigned z)
{
int i,r;
r=0;
for(i=0;i<20;i++)if(ddy&z)r++;
return r;
}
int doz()
{
int i,j,zn;
unsigned x,z;
zn=0;
for(j=0;j<z_zn;j++)
{
x=z_z;
for(i=0;i<z_xsn;i++)if(nu(x&z_xs)>=2)break;
if(i<z_xsn)continue;
for(i=0;i<z_ansn;i++)if(nu(x&z_ans)==2)break;
if(i<z_ansn)continue;
z=x;zn++;
}
z_zn=ztoz(z,z_z,zn);
return 0;
}
int dozf()
{
int i,j,zn;
unsigned x,z;
zn=0;
for(j=0;j<z_zn;j++)
{
x=z_z;
for(i=0;i<z_xsn;i++)if(nu(x&z_xs)>=2)break;
if(i<z_xsn)continue;
z=x;zn++;
}
z_zn=ztoz(z,z_z,zn);
return 0;
}
int doz1()
{
int i,rn;
rn=0;
for(i=0;i<z_zn;i++)
if(z_x!=z_z){z_z=z_z;rn++;continue;}
z_zn=rn;
return rn;
}
int conf()
{
unsigned room,ans,imp;
int roomn,ansn,impn,i,j;
Begin:
roomn=ztoz(z_xs,room,z_xsn);
roomn+=ztoz(z_ans,room+roomn,z_ansn);
// printf("the input of ssn is(roomn=%d):\n",roomn);
// shows(room,roomn);
ansn=ssn(room,roomn,ans);
if(ansn>0)
{
// printf("Add z_zans to ansn.\n");
ansn+=ztoz(z_ans,ans+ansn,z_ansn);
// printf("\nThere is %d(ansn) ans, and they are:\n",ansn);
// shows(ans,ansn);
ansn=sdcd(ans,ansn);
// printf("Get rid of the same ans, there is %d(ansn) ans lest, and they are:\n",ansn);shows(ans,ansn);
// printf("Cal imp of ans..\n");
impn=0;
for(i=0;i<ansn;i++)
for(j=i+1;j<ansn;j++)
if(nu(ans&ans)==2){imp=ans|ans;
// printf("There is 2 ans to 1 imp: [");show(ans);show(ans);show(imp);printf("]]].\n");
impn++;}
if(impn>0)
{
// printf("There is %d imp. check imp if or not conf with z_xs?\n",impn);
for(i=0;i<impn;i++)
{
for(j=0;j<z_xsn;j++)
if(nu(imp&z_xs)>=2){
// printf("Conf...with ");show(imp);show(z_xs);
return -1;}
z_xs=imp;z_xsn++;
}
// printf("No, there is no conf in imp. and new z_xsn is %d.\n",z_xsn);
// printf("Get rid of ans in the imp, and put to z_ans.\n");
z_ansn=0;
for(i=0;i<ansn;i++)
{
for(j=0;j<impn;j++)if(ans==(ans&imp))break;
if(j!=impn){
// printf("GEtridof ans>>>");show(ans);
continue;}
z_ans=ans;z_ansn++;
}
}
else
{
// printf("There is no imp.\n");
z_ansn=ztoz(ans,z_ans,ansn);
}
// printf("Check conf with z_ans and all z_xs...\n");
for(i=0;i<z_ansn;i++)
for(j=0;j<z_xsn;j++)
if(nu(z_ans&z_xs)==2){
// printf("Conf...with");show(z_ans);show(z_xs);
return -1;}
// printf("No, there is no conf in z_ans and z_xs.\n");
// printf("Now z_ans (number is %d):",z_ansn);shows(z_ans,z_ansn);
// printf("$$$$$$$$$$Recal ssn...$$$$$$$$$\n");
// _getch();
goto Begin;
}
return 0;
}
int _tmain(int argc, _TCHAR* argv[])
{
unsigned xs,ans,z;//,aa;
int kkk;
// int key,zn,sn,xsl,ansl,aal,n,aan;
int loop,xsn,ansn,k,i,zn;//,j;
int r,tn;
FILE *fp;
printf("The program is running...\n");
fopen_s(&fp,"d:\\xt.txt","w");
for(i=0;i<30;i++)kkk=0;
// aan=0;
srand((unsigned)time(NULL));
init();
zn=ztoz(z_z,z,z_zn);
for(i=0;i<500000;i++)
{
// n=0;
z_xsn=z_ansn=0;
xsn=ansn=0;
z_zn=ztoz(z,z_z,zn);
for(loop=0;loop<500;loop++)
{
// printf("\n\n\nLoop %d:\n",loop);
if(z_xsn<10)
{
k=((unsigned)rand())%z_zn;z_x=z_z;
z_xs=z_x;z_xsn++;
dozf();
continue;
}
if(z_xsn==10)tn=z_zn;
xsn=ztoz(z_xs,xs,z_xsn);
ansn=ztoz(z_ans,ans,z_ansn);
// aan=0;
// for(j=0;j<ansn;j++)
// for(k=0;k<z_zn;k++)if(ans==(ans&z_z)){aa=z_z;aan++;}
// if(aan>0){k=((unsigned)rand())%aan;z_x=aa;}
// else {k=((unsigned)rand())%z_zn;z_x=z_z;}
k=((unsigned)rand())%z_zn;z_x=z_z;
// printf("Get a x:\n");show(z_x);
z_xs=z_x;z_xsn++;
// printf("====Input=================================\n");
// printf("Now z_xs (number is %d):",z_xsn);
// shows(z_xs,z_xsn);
// printf("Now z_ans (number is %d):",z_ansn);
// shows(z_ans,z_ansn);
// printf("-------------------------------------------\n");
r=conf();
// printf("\nr=%d.\n",r);
// if(r==0){
// printf("====Output=================================\n");
// printf("Now z_xs (number is %d):",z_xsn);
// shows(z_xs,z_xsn);
// printf("Now z_ans (number is %d):",z_ansn);
// shows(z_ans,z_ansn);
// printf("-------------------------------------------\n");
// }else printf("-1\n");
if(r==0)
{
// printf("@@@@@@@ r=0, and doz() it....\n");
doz();
}
else
{
// printf("&&&&&&& r=-1, recover z_xsn x_ans and doz1() it...\n");
z_xsn=ztoz(xs,z_xs,xsn);
z_ansn=ztoz(ans,z_ans,ansn);
doz1();
}
// printf("z_zn[%d]=%d.\n",n,z_zn);
// key=k;sn=z_xsn;zn=z_zn;xsl=z_xsn;ansl=z_ansn;aal=aan;n++;
if(z_zn==0)break;
// printf("-------------------------------------------\n");
}
kkk++;
if(z_xsn>22)
{
printf("\n\nFinish(@%d)[%d]... %d\n**********************************************\n",loop,tn,z_xsn);
printf("Now z_xs's number is %d):\n",z_xsn);
shows(z_xs,z_xsn);
printf("**********************************************\n");
// if(z_xsn>0)printf("%d,",z_xsn);
// for(j=0;j<n;j++)
// {
// printf("key[%d]=%d(%d),sn[%d]=%d,zn[%d]=%d,xsl[%d]=%d,ansl[%d]=%d\n",j,key,aal,j,sn,j,zn,j,xsl,j,ansl);
// }
printf("=================================================================================\n\n");
// _getch();
fprintf(fp,"\n\nFinish(@%d)... %d\n**********************************************\n",loop,z_xsn);
fprintf(fp,"Now z_xs's number is %d):\n",z_xsn);
fshows(fp,z_xs,z_xsn);
fprintf(fp,"**********************************************\n");
// if(z_xsn>0)printf("%d,",z_xsn);
// for(j=0;j<n;j++)
// {
// printf("key[%d]=%d(%d),sn[%d]=%d,zn[%d]=%d,xsl[%d]=%d,ansl[%d]=%d\n",j,key,aal,j,sn,j,zn,j,xsl,j,ansl);
// }
fprintf(fp,"=================================================================================\n\n");
// _getch();
}
}
printf("\nEnd\n");
for(i=0;i<30;i++)printf("%d,",kkk);;
for(i=0;i<30;i++)fprintf(fp," %d,",kkk);;
_getch();
return 0;
}
代码挺难看懂的，还是大概介绍一下思路吧。
我的方法是不能完全运行时判断的，只能运行时淘汰部分解。