毒酒问题(加强版)

mathe · 发表于 2009-6-10 09:42:53

这样判断过多了. 程序里面已经枚举了所有的a<=b,a<=c,c<=d的情况,而A,B,C,D枚举了所有的组合也就是对于任何的(aA,bB),(cC,dD)组合已经穷举完了. 而如你那样修改,会在sa[a]|sa[b]) !=(sa[c]|sa[d])的情况下还要额外要求对应的la不等

shshsh_0510 · 发表于 2009-6-10 10:18:00

sorry 没注意前面是 for(c=a;c

数学星空 · 发表于 2009-6-10 16:30:33

数学上的构造方法更需要天才的想法和可靠的理论

mathe · 发表于 2009-6-10 17:40:52

现在将这个模型的期望数目重新推导了一下,得出一个比较准确的公式,然后用计算机计算的确在N=32时无法超过1000了(只有824),而N=33时期望数目可以达到1262. 所以这个方法33已经是最好的结果了.

#define N 32
#define MAXR 800
double maxr;
double f(double r[4],double x,int n)
{
double rt=0.0;
int i;
for(i=0;i<n;i++){
rt*=x;
rt+=r[n-1-i];
}
return rt;
}
double round(double x)
{
return (double)(int)(x+0.5);
}
#define ERROR 0.0001
void solve3(double r[4],int m[])
{
double dr[3];
double r0=100.0;
double err;
int c;
int gc=0;
dr[0]=r[1];dr[1]=2*r[2];dr[2]=3*r[3];
start:
c=0;
do{
double t=f(r,r0,4);
err=t/f(dr,r0,3);
r0-=err;
c++;
}while(fabs(err)>ERROR&&c<100);
if(c>=100){
r0=(double)rand();
gc++;
if(gc>=100){
m[0]=m[1]=m[2]=-1;
return;
}
goto start;
}
m[0]=(int)round(r0);
dr[2]=r[3];
dr[1]=r[2]-r0*dr[2];
dr[0]=r[1]-r0*dr[1];
double dd=dr[1]*dr[1]-4*dr[0]*dr[2];
if(dd<0.0){
m[1]=m[2]=-1;
}else{
dd=sqrt(dd);
m[1]=(int)round((-dr[1]+dd)/(2*dr[2]));
m[2]=(int)round((-dr[1]-dd)/(2*dr[2]));
}
}
void get_m(int k,double q, int m[3])
{
int L=N-3*k;
double r[4];
double K=k*pow(3.0,(double)(k-2));
double H=1-2*q*q+2*q*q*q;
double Q=1-2*q*q+2*q*q*q*q;
double HL=pow(H,L);
double QL=pow(Q,L);
double S=pow(6.0,k-2);
double R=k*6*S+k*(k-1)/2.0*S*9.0;
r[0]=-K;
r[0]+=HL*K;
r[1]=-3*HL*K;
r[2]=3.0/2.0*HL*K;
r[0]-=3.0/2.0*QL*K;
r[1]+=11.0/2.0*QL*K;
r[2]-=9.0/2.0*QL*K;
r[3]=QL*K;
r[1]+=0.5*QL*K*(K-1);
r[2]-=3.0/2.0*QL*K*(K-1);
r[3]+=QL*K*(K-1);
r[3]+=QL*R*4.0;
solve3(r,m);
}
void test(int k,double q, int m)
{
int L=N-3*k;
double K=k*pow(3.0,(double)(k-2));
double H=1-2*q*q+2*q*q*q;
double Q=1-2*q*q+2*q*q*q*q;
double HL=pow(H,L);
double QL=pow(Q,L);
double dm=m;
double S=pow(6.0,k-2);
double R=k*6*S+k*(k-1)/2.0*S*9.0;
double r=K*dm-K*dm*(dm-1)*(dm-2)/2.0*HL-dm*(dm-1)*(dm-2)*(dm-3)/4.0*K*QL
-K*(K-1)*dm*dm*(dm-1)*(dm-1)/4.0*QL-R*dm*dm*dm*dm*QL;
if(r>=MAXR){
printf("k=%d,q=%f,m=%d,r=%f\n",k,q,m,r);
if(r>maxr)maxr=r;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int k,s;
double q;
for(k=3;k<=8;k++){
for(q=0.6667;q<0.707;q+=0.0001){
int m[3];
get_m(k,q,m);
for(s=0;s<3;s++){
if(m[s]>0&&m[s]<100000){
test(k,q,m[s]);
}
}
}
}
printf("maxr=%f\n",maxr);
return 0;
}

复制代码

mathe · 发表于 2009-6-11 08:37:25

现在写了一个穷举的程序. 对于囚犯数目n不超过5,仅可以识别n+1坛酒(2坛毒酒) 对于n=6,可以识别8坛酒 00 03 0C 15 1A 26 29 30 对于n=7,可以识别10坛酒: 00 03 05 09 12 24 38 48 54 62 对于n=8,至少可以识别13坛酒: 00 03 0C 15 26 38 49 52 60 8A 90 A1 C4 对于n=9,至少可以识别16坛酒: 000 003 024 038 048 062 00D 016 051 081 098 0C4 10A 110 121 144 n=10,至少20坛酒 000 003 024 038 048 062 00D 016 051 098 0C4 10A 110 181 231 254 28A 2C1 30C 322 n=11,至少可以26坛酒 016 051 098 0C4 10A 110 181 231 254 28A 2C1 30C 322 000 003 00D 024 038 048 062 428 485 4C2 521 540 600 n=12,可以32坛 0C4 10A 110 081 144 221 288 301 431 494 505 602 628 740 000 00D 024 038 048 051 062 092 252 4C2 832 886 909 A04 A41 B02 C18 C80 n=13,可以39坛 010A 0110 0081 0121 0144 0205 0494 0612 0640 0720 0904 0A11 0A20 0B02 0C06 0C08 0C21 0E80 0000 0003 000D 0016 0024 0048 0051 02B0 03C0 08A8 101C 1022 10E0 1188 1242 1280 1401 1428 1444 1812 1901 n=14,至少47坛 0110 0081 0121 0144 0205 0494 0222 0460 0630 0704 0809 0842 0A11 0B02 0C10 0E80 10C0 1212 1301 1408 1421 1890 1940 1A00 0000 0003 000D 0016 0024 0038 0048 0051 0098 010A 1406 2046 2084 2214 22C0 2320 2402 2488 2908 2C20 3009 3010 3060

mathe · 发表于 2009-6-11 08:45:04

这下在Sloane网站中找到位置了: https://oeis.org/A054961 根据A054961,有 a(9) >= 17. Here is a candidate solution: {011010001 001001010 101000110 100000001 000010110 110010100 010000011 000110000 001001101 010000100 110001000 000101100 100100010 001000000 010100101 111100000 000011001}. - Dmitry Kamenetsky, Jul 17 2017 a(10) >= 22. Here is a candidate solution: {1010110000 1110000000 0010011000 0110100001 1000010101 0011000101 1001000000 0000000010 0001110100 0001001000 0010101010 1100010010 0000010001 0000101101 0100010100 0000011110 0100101000 0001100011 0000100100 0101000001 0101000110 1010000011}. - Dmitry Kamenetsky, Jul 17 2017 a(11) >= 31. Here is a candidate solution: {00101010010 01100101000 00001101100 00001010101 00100110100 00101001001 01000100101 00010101001 10001100001 11010000010 01001001010 00000001111 01111000000 00110010001 10000111000 11100000001 10010000101 00011110000 01000011001 00100100011 01010010100 01000110010 10110100000 10101000100 11001010000 00011000110 10000010011 10000100110 10100001010 00010011010 00000000100}. - Dmitry Kamenetsky, Jul 21 2017 a(12) >= 46. Here is a candidate solution: {011000011000 000000001000 000110100001 111000000010 110100000100 000010110100 010100010010 000011000011 010001001010 000111001000 010000101100 001001100010 100010000110 000001010110 001010101000 010010100010 001001001001 101000100100 000001100101 100011100000 000100011100 001000010011 010100001001 101100001000 100110010000 001110000010 100001001100 010101100000 110001000001 110010001000 011000100001 001100110000 001000001110 000010001101 110000110000 000100100110 000010011010 101001010000 000101010001 001100000101 100000010101 000001111000 101010000001 100101000010 010000000111 010010010001}. - Dmitry Kamenetsky, Jul 21 2017

数学星空 · 发表于 2009-6-14 17:26:04

请教mathe一个问题对于n=6,可以识别8坛酒 00 03 0C 15 1A 26 29 30 列表中的00,13,...表示什么意思?? 即6个人怎么喝这8坛酒?/

mathe · 发表于 2009-6-14 21:38:21

上面每一行数都是一个16进制数,其中A,B,C,D,E,F表示16进制中的10~15. 而我们可以将每位16进制数转化为4位二进制数,比如 0 -> 0000 1 -> 0001 2 -> 0010 3 -> 0011 4 -> 0100 ... F -> 1111 于是替换以后,每一行可以表示成一个n位二进制数.其中每一位分别对应那个人是否要喝对应的那坛酒(所在行表示酒) 如上面n=6的情况,那么第一行00,表示第一坛酒6个人都不喝.第二行0C转化为6位二进制数是001100,表示第3和第4个人喝第二坛酒.第三行15即二进制010101,所以第三坛酒是第2,4,6个人喝,等等.

mathe · 发表于 2009-6-15 08:34:16

百度贴巴中的tannis_jin关于这个题目找到了一种挺好的构造方法(虽然这个方法对于大规模数据的结果还是不够好),这里我来整理一下他的思路: 假设h(m)表示m坛酒中如果有1坛或2坛毒酒的情况下,需要囚犯的最少数目. 那么对于一个m*m方阵坛酒, 首先,我们可以将每一行的酒混合,得到m坛混合酒,其中有1坛或2坛有毒,所以需要h(m)个囚犯可以确定在哪一航. 同样在使用h(m)个囚犯可以确定在哪一列. 在确定行和列以外,在任意一条对角线方向,除了对角线顶点,以及紧挨着顶点的酒坛,余下的酒按桶对角线垂直方向的直线分类可以分成2m-5类,我们最多使用h(2m-5)个囚犯可以确定在那条对角线上. 于是采用这个方案有 $h(m*m)<=2h(m)+h(2m-5)$ 而对于1000坛酒,我们可以取m=32,于是$h(1024)<=2h(32)+h(59)$ 我们看65#的结果,其中每个结果中都包含一个全0的结果,去掉那个全0的方案就正好对应h(.)的方案也就是说包含1到2坛毒酒的38坛只需要13个人识别,所以h(32)<=13.而看上面序列的趋势,h(59)应该不会超过16,也就是用这个方法需要2*13+16=42个人就可以了. 而如果我们继续结合7#的方案,那么一个边长为19的六边形里面包含1027桶酒.其中三组对边方向,每个方向有37条直线,所以我们只需要3h(37)=3*13=39个人酒可以确定了. 而将方法推广到m非常大的情况, tannis_jin的方法相当于使用递推式 $h(m*m)<=2h(m)+h(2m-5)$ 于是这个方法得到的h(m)的复杂度也为$h(m)=O(log^2(m))$ 而结合7#的方案当中,其递推式为 $h(3*m*(m-1)+1)=3h(m)$, 这个方案的复杂度为$h(m)=O(log^{log_2 3}(m))$,比上面的方法要好一些. 但是无论比起24#的集合方法(其中1000坛酒可以得到41人的结果),47#4n个人解决$2^n$坛酒的$F_{2^n}$上的构造方法(1000坛酒40人的结果),还是39#半随机方法(1000坛酒33人的结果59#)(它们的复杂度都是$O(log(n))$)都还是要差一些.可能这是构造方法本身的缺陷了

数学星空 · 发表于 2009-6-15 11:33:59

mathe有相当的数学专业精神,佩服至极.....

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 毒酒问题(加强版)