数学研发论坛

 找回密码
 欢迎注册
楼主: mathe

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

  [复制链接]
发表于 2009-6-8 08:53:24 | 显示全部楼层
不好意思,原来没注意15#已经讲解过原理了,感谢mathe的再次解说
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-8 09:46:31 | 显示全部楼层
现在写了个程序来简单搜索1000桶酒的解,看看能否找到41个囚徒的解:
不过程序运行挺慢的.

  1. #include <vector>
  2. #define TARGET_COUNT 1000
  3. #define N 41
  4. #define WEIGHT 7
  5. #define MIN_DISTANCE 8
  6. #define MAX_OVERLAP (WEIGHT-(MIN_DISTANCE+1)/2)
  7. #define DISP_SIZE ((N+3)/4)
  8. using namespace std;
  9. //#define SHOW_COUNT
  10. vector<long long> data;
  11. void init()
  12. {
  13.     long long u=(1LL<<MAX_OVERLAP)-1;
  14.     int j=(N-MAX_OVERLAP)/(WEIGHT-MAX_OVERLAP);
  15.     long long s=(1LL<<(WEIGHT-MAX_OVERLAP))-1;
  16.     int i;
  17.     for(i=0;i<j;i++){
  18.         int k=i*(WEIGHT-MAX_OVERLAP)+MAX_OVERLAP;
  19.         long long r=u|(s<<k);
  20.         data.push_back(r);
  21.         printf("%0*llX",DISP_SIZE,r);
  22. #ifdef SHOW_COUNT
  23.         printf("::%d",data.size());
  24. #endif
  25.         printf("\n");
  26.     }
  27.     fflush(stdout);
  28. }

  29. int bitcount(long long x)
  30. {
  31.     int bc=0;
  32.     int i;
  33.     for(i=0;i<64;i++){
  34.         if(x&(1LL<<i))bc++;
  35.     }
  36.     return bc;
  37. }

  38. bool try_next_bit(long long r, int nb, int bc)
  39. {
  40.     int i,j;
  41.     if(bc>=WEIGHT){
  42.         data.push_back(r);
  43.         printf("%0*llX",DISP_SIZE,r);
  44. #ifdef SHOW_COUNT
  45.         printf("::%d",data.size());
  46. #endif
  47.         printf("\n");
  48.         fflush(stdout);
  49.         return true;
  50.     }
  51.     for(i=nb;i<N;i++){
  52.         r|=(1LL<<i);
  53.         for(j=0;j<data.size();j++){
  54.             if(bitcount(r&data[j])>MAX_OVERLAP)
  55.                 break;
  56.         }
  57.         if(j<data.size()){
  58.             r&=~(1LL<<i);
  59.             continue;
  60.         }
  61.         if(try_next_bit(r,i+1,bc+1))
  62.             return true;
  63.         r&=~(1LL<<i);
  64.     }
  65.     return false;
  66. }


  67. int _tmain(int argc, _TCHAR* argv[])
  68. {
  69.     init();
  70.     while(try_next_bit(0LL,0,0));
  71.     printf("Total %d\n",data.size());
  72.         return 0;
  73. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-8 10:04:25 | 显示全部楼层
29#给出的是一个上界,这个问题需要下界,对于A(n,d,w)的上下界可参照
下界:http://www.research.att.com/~njas/codes/Andw/index.html
上界:http://webfiles.portal.chalmers.se/s2/research/kit/bounds/cw.html
没仔细看,不知mathe的上界对其是否有改善
另外对于1000瓶酒,感觉用Constant-weight code的方法,41就是极限了,用A(n,10,9)已经不如A(n,8,7)了,所以知道更多的A(n,d,w)也没有用了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-8 10:10:42 | 显示全部楼层
我的bound肯定很不好.我主要是希望能够有一个用公式表示的下界,这样就可以比较可信的估计出k和n的关系是不是对数关系了.现在的结果还是不够可信
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-8 13:20:29 | 显示全部楼层
上面的程序挺慢的,所以我修改了一下main函数,让程序运行的快一些:


  1. int _tmain(int argc, _TCHAR* argv[])
  2. {
  3.     int nb=0;
  4.     int newnb;
  5.     init();
  6.     while(try_next_bit(0LL,nb,0)){
  7.         nb=firstone(data[data.size()-1]);
  8.     }
  9.     printf("Total %d\n",data.size());
  10.         return 0;
  11. }
复制代码
其中函数firstone返回输入数据的最低为1的比特位(0~63)
现在程序对于41个囚犯,已经搜索出超过1000桶酒的方案了,不过还没有算完.
等算完了我再将数据贴出来(不知道能够搜索出多少桶酒的方案)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-8 13:29:18 | 显示全部楼层
呵呵,结果出来了,结果也是1095,就是说同上面表格给出的结果相同,基本上花了一个小时.
附件中给出了源代码和数据
cs.tar.gz (6.08 KB, 下载次数: 8)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-8 17:32:16 | 显示全部楼层
想了一下,shshsh_0510的拆分方法还是挺有用的.不过得到的结果应该是
$f(2x)
mathe 发表于 2009-6-7 19:06

现在感觉shshsh_0510的那个结果:
$f(2x)<=f(x)+2+g(x)$还是对的.
不过复杂度还是$O(log^2(x))$而不是$O(log(x))$.
其道理在于每次对2x桶酒中找两桶毒酒时,我们可以直接让两个人分别喝掉左边和右边的x桶酒.
那么如果只有一个人毒死,那么就转化为f(x)的问题.而且左边和右边死掉的情况不会同时出现.所以f(x)部分对于左边和右边的情况可以用相同的人来测试.
而这种测试会就相当于将2x写成2进制数,这些囚犯都正好喝掉某个比特位为1对应的所有的酒或某个比特位为0对应的所有的酒.
而余下比较复杂的情况是在某一层开始,左边和右边的人同时死去(对应上面的方法,相当于出现比特位为1和0对应的囚徒都死去的最高比特位h).而由这一层开始,我们只需要左边分支,对这个分支采用$g(2^h)$的方案可以得出这个分支中毒酒的位置.而对于右边的分支,在左边分支的结果确定以后,对于所有低比特位就可以直接确定了(如果对某个比特位,只有1或0对应的囚徒死去,两个分支在这个比特位相同;如果同时1和0对应的囚徒死去,两个分支在这个比特位取值相反).
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-8 19:43:41 | 显示全部楼层
然后对于每个数字,在表格中找到不小于这个数字的行号最小的格子.那么行号就是这个方法可以提供的最少的囚徒数.不过可惜我没有找到A(n,d,w)的近似公式,不然我们可以对它有更好的了解.
可以看到在同的数目k
mathe 发表于 2009-6-7 18:11

发现我的这个方案中,我们总可以再加一桶酒,所有的人都不喝.
这个对比较小规模问题影响比较明显.比如9个人可以解决13桶问题
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-8 22:15:24 | 显示全部楼层
google到一篇很强的文章,对于1000,应该可以消减到31一下:
v5i1r39.pdf (140.75 KB, 下载次数: 96)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-8 22:48:31 | 显示全部楼层
39# mathe


呵呵,还是你快。
我找到erdos那个但没能超过41
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-12-11 05:57 , Processed in 0.060357 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表