- 注册时间
- 2007-12-27
- 最后登录
- 1970-1-1
- 威望
- 星
- 金币
- 枚
- 贡献
- 分
- 经验
- 点
- 鲜花
- 朵
- 魅力
- 点
- 上传
- 次
- 下载
- 次
- 积分
- 2608
- 在线时间
- 小时
|
发表于 2008-11-13 11:50:12
|
显示全部楼层
我把代码贴上来吧。编写的比较乱。上面发的可执行文件去掉了写盘的部分。
其中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[20]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288};
- unsigned z_xs[1000],z_ans[1000],z_z[M],z_x;
- int z_xsn,z_ansn,z_zn;
- int show(unsigned d)
- {
- unsigned i;
- for(i=0;i<20;i++)if(d&ddy[i])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[i]);printf("-");}
- show(d[i]);
- }
- printf("]\n");
- return 0;
- }
- int fshow(FILE *fp,unsigned d)
- {
- unsigned i;
- for(i=0;i<20;i++)if(d&ddy[i])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[i]);fprintf(fp,"-");}
- fshow(fp,d[i]);
- }
- 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[z_zn]=ddy[i1]|ddy[i2]|ddy[i3]|ddy[i4];
- z_zn++;
- }
- return 0;
- }
- int ssn(unsigned *qtx,int qtxn,unsigned *ans)
- {
- unsigned lxz[1000],sxz1,sxz2,sxz3,sjx[3000],sjd1,sjd2,sjxl1[3000],sjxl2[3000],sjxl3[3000];
- 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[i]){lxz[lxzn]=qtx[i]^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[i1];sxz2=lxz[i2];sxz3=lxz[i3];
- 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[i]))break;if(i<qtxn)continue;
- for(i=0;i<qtxn;i++)if(((z2&qtx[i])!=0)&&((z3&qtx[i])!=0)){sjxl1[sjxn]=qtx[i]&(~z2)&(~z3);break;}if(i==qtxn)continue;
- for(i=0;i<qtxn;i++)if(((z1&qtx[i])!=0)&&((z3&qtx[i])!=0)){sjxl2[sjxn]=qtx[i]&(~z1)&(~z3);break;}if(i==qtxn)continue;
- for(i=0;i<qtxn;i++)if(((z1&qtx[i])!=0)&&((z2&qtx[i])!=0)){sjxl3[sjxn]=qtx[i]&(~z1)&(~z2);break;}if(i==qtxn)continue;
- sjx[sjxn]=zz;sjxn++;
- }}}
- for(k1=0;k1<sjxn-1;k1++)
- for(k2=k1+1;k2<sjxn;k2++)
- {
- sjd1=sjx[k1];sjd2=sjx[k2];
- if(sjd1&sjd2)continue;
- sa1=sjxl1[k1];sa2=sjxl2[k1];sa3=sjxl3[k1];
- sb1=sjxl1[k2];sb2=sjxl2[k2];sb3=sjxl3[k2];
- 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[i]))break;if(i==qtxn){ans[ansn]=zz;ansn++;}}
- }
- }
- }
- return ansn;
- }
- int ztoz(unsigned *z0,unsigned *z,int zn)
- {
- int i;
- for(i=0;i<zn;i++)z[i]=z0[i];
- 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[i]==z[j])break;
- if(j==rn){z[rn]=z[i];rn++;}
- }
- return rn;
- }
- int nu(unsigned z)
- {
- int i,r;
- r=0;
- for(i=0;i<20;i++)if(ddy[i]&z)r++;
- return r;
- }
- int doz()
- {
- int i,j,zn;
- unsigned x,z[M];
- zn=0;
- for(j=0;j<z_zn;j++)
- {
- x=z_z[j];
- for(i=0;i<z_xsn;i++)if(nu(x&z_xs[i])>=2)break;
- if(i<z_xsn)continue;
- for(i=0;i<z_ansn;i++)if(nu(x&z_ans[i])==2)break;
- if(i<z_ansn)continue;
- z[zn]=x;zn++;
- }
- z_zn=ztoz(z,z_z,zn);
- return 0;
- }
- int dozf()
- {
- int i,j,zn;
- unsigned x,z[M];
- zn=0;
- for(j=0;j<z_zn;j++)
- {
- x=z_z[j];
- for(i=0;i<z_xsn;i++)if(nu(x&z_xs[i])>=2)break;
- if(i<z_xsn)continue;
- z[zn]=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[i]){z_z[rn]=z_z[i];rn++;continue;}
- z_zn=rn;
- return rn;
- }
- int conf()
- {
- unsigned room[1000],ans[1000],imp[1000];
- 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[i]&ans[j])==2){imp[impn]=ans[i]|ans[j];
- // printf("There is 2 ans to 1 imp: [");show(ans[i]);show(ans[j]);show(imp[impn]);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[i]&z_xs[j])>=2){
- // printf("Conf...with ");show(imp[i]);show(z_xs[j]);
- return -1;}
- z_xs[z_xsn]=imp[i];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[i]==(ans[i]&imp[j]))break;
- if(j!=impn){
- // printf("GEtridof ans>>>");show(ans[i]);
- continue;}
- z_ans[z_ansn]=ans[i];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[i]&z_xs[j])==2){
- // printf("Conf...with");show(z_ans[i]);show(z_xs[j]);
- 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[1000],ans[1000],z[M];//,aa[1000];
- int kkk[30];
- // int key[1000],zn[1000],sn[1000],xsl[1000],ansl[1000],aal[1000],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[i]=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[k];
- z_xs[z_xsn]=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[j]==(ans[j]&z_z[k])){aa[aan]=z_z[k];aan++;}
-
- // if(aan>0){k=((unsigned)rand())%aan;z_x=aa[k];}
- // else {k=((unsigned)rand())%z_zn;z_x=z_z[k];}
- k=((unsigned)rand())%z_zn;z_x=z_z[k];
- // printf("Get a x:\n");show(z_x);
- z_xs[z_xsn]=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[n]=k;sn[n]=z_xsn;zn[n]=z_zn;xsl[n]=z_xsn;ansl[n]=z_ansn;aal[n]=aan;n++;
- if(z_zn==0)break;
- // printf("-------------------------------------------\n");
- }
- kkk[z_xsn]++;
- 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[j],aal[j],j,sn[j],j,zn[j],j,xsl[j],j,ansl[j]);
- // }
- 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[j],aal[j],j,sn[j],j,zn[j],j,xsl[j],j,ansl[j]);
- // }
- fprintf(fp,"=================================================================================\n\n");
- // _getch();
- }
- }
- printf("\nEnd\n");
- for(i=0;i<30;i++)printf("%d,",kkk[i]);;
- for(i=0;i<30;i++)fprintf(fp," %d,",kkk[i]);;
- _getch();
- return 0;
- }
|
|
楼主: 0→∞
IP卡
狗仔卡
发表于 2008-11-12 16:44:29
显身卡
不过这个文件可能比较大了
