不好意思，原来没注意15#已经讲解过原理了，感谢mathe的再次解说:)
现在写了个程序来简单搜索1000桶酒的解,看看能否找到41个囚徒的解:
不过程序运行挺慢的.
#include <vector>
#define TARGET_COUNT 1000
#define N 41
#define WEIGHT 7
#define MIN_DISTANCE 8
#define MAX_OVERLAP (WEIGHT-(MIN_DISTANCE+1)/2)
#define DISP_SIZE ((N+3)/4)
using namespace std;
//#define SHOW_COUNT
vector<long long> data;
void init()
{
long long u=(1LL<<MAX_OVERLAP)-1;
int j=(N-MAX_OVERLAP)/(WEIGHT-MAX_OVERLAP);
long long s=(1LL<<(WEIGHT-MAX_OVERLAP))-1;
int i;
for(i=0;i<j;i++){
int k=i*(WEIGHT-MAX_OVERLAP)+MAX_OVERLAP;
long long r=u|(s<<k);
data.push_back(r);
printf("%0*llX",DISP_SIZE,r);
#ifdef SHOW_COUNT
printf("::%d",data.size());
#endif
printf("\n");
}
fflush(stdout);
}
int bitcount(long long x)
{
int bc=0;
int i;
for(i=0;i<64;i++){
if(x&(1LL<<i))bc++;
}
return bc;
}
bool try_next_bit(long long r, int nb, int bc)
{
int i,j;
if(bc>=WEIGHT){
data.push_back(r);
printf("%0*llX",DISP_SIZE,r);
#ifdef SHOW_COUNT
printf("::%d",data.size());
#endif
printf("\n");
fflush(stdout);
return true;
}
for(i=nb;i<N;i++){
r|=(1LL<<i);
for(j=0;j<data.size();j++){
if(bitcount(r&data)>MAX_OVERLAP)
break;
}
if(j<data.size()){
r&=~(1LL<<i);
continue;
}
if(try_next_bit(r,i+1,bc+1))
return true;
r&=~(1LL<<i);
}
return false;
}
int _tmain(int argc, _TCHAR* argv[])
{
init();
while(try_next_bit(0LL,0,0));
printf("Total %d\n",data.size());
return 0;
}
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)也没有用了
我的bound肯定很不好.我主要是希望能够有一个用公式表示的下界,这样就可以比较可信的估计出k和n的关系是不是对数关系了.现在的结果还是不够可信
上面的程序挺慢的,所以我修改了一下main函数,让程序运行的快一些:
int _tmain(int argc, _TCHAR* argv[])
{
int nb=0;
int newnb;
init();
while(try_next_bit(0LL,nb,0)){
nb=firstone(data);
}
printf("Total %d\n",data.size());
return 0;
}
其中函数firstone返回输入数据的最低为1的比特位(0~63)
现在程序对于41个囚犯,已经搜索出超过1000桶酒的方案了,不过还没有算完.
等算完了我再将数据贴出来(不知道能够搜索出多少桶酒的方案)
呵呵,结果出来了,结果也是1095,就是说同上面表格给出的结果相同,基本上花了一个小时.
附件中给出了源代码和数据
其中每行数据是一个41比特的数,用16进制表示表示.
每一行代表一桶酒,如果对应比特位是1,那么就说明那个囚犯需要喝那同酒.
其中每桶酒正好有7个囚犯来喝.
而最终的结果应该有14个囚犯死去.检测方法类似,只要查看每行比特位为1的囚犯是否全部死去(如果是,则这桶酒有毒,不然无毒)
所以这个方案可以用41个囚犯检测不超过1095桶酒(2桶有毒)
想了一下,shshsh_0510的拆分方法还是挺有用的.不过得到的结果应该是
$f(2x)
mathe 发表于 2009-6-7 19:06 http://bbs.emath.ac.cn/images/common/back.gif
现在感觉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对应的囚徒死去,两个分支在这个比特位取值相反).
然后对于每个数字,在表格中找到不小于这个数字的行号最小的格子.那么行号就是这个方法可以提供的最少的囚徒数.不过可惜我没有找到A(n,d,w)的近似公式,不然我们可以对它有更好的了解.
可以看到在同的数目k
mathe 发表于 2009-6-7 18:11 http://bbs.emath.ac.cn/images/common/back.gif
发现我的这个方案中,我们总可以再加一桶酒,所有的人都不喝.
这个对比较小规模问题影响比较明显.比如9个人可以解决13桶问题
google到一篇很强的文章,对于1000,应该可以消减到31一下:
39# mathe
呵呵，还是你快。
我找到erdos那个但没能超过41