毒酒问题(加强版)

mathe

K6N37.zip (10.16 KB, 下载次数: 4)

2009-6-9 15:10 上传

点击文件名下载附件

得到一个N=37的解.现在的结果是37人解决2111桶酒问题. 附件中每行数字左边18比特,右边19比特. 本来以为还可以得到更好的结果,不过好像是由于我的概率估计公式不够准确,K更大时现在的我的概率公式就完全不准了,所以结果不对.

mathe

wine.zip (16.84 KB, 下载次数: 10)

2009-6-9 15:30 上传

点击文件名下载附件

现在找到了33个囚犯的方案. 附件中分别给出了33~35个囚犯的解决方案. 其中文件中每一行两个整数,前面整数18比特,后面的15~17比特.合起来是33~35比特的数

shshsh_0510

呵呵，想不到这概率的方法效果这么好！居然能低于35！ 沾程序验证的事就只有看你们这帮快手干了。

shshsh_0510

48#说的产生14个24位的随机数，这些数是你结果中的第二列吗？你结果中的数看起来都不相同啊

mathe

对的,第一列是构造值,第二列是随机的(所以看起来都不相同).唯一控制的是0,1产生的概率

shshsh_0510

那上边你说的那个“14个”体现在哪了？

mathe

每个第一个数字相同的数会产生14个第二个数(当然后面的程序会淘汰掉部分数据),所以实际上最终结果是对每个第一个数字,对应第二个数字小于14. 这个说的14仅仅对于39个囚徒的情况,而对于其它情况,这个数字可能不同.(这里这个数字对应程序中参数m)

shshsh_0510

明白了，多谢

mathe

发现前面的程序有个BUG.其中函数check3没有检查完所有情况,需要修改一下. 修改以后,通过K=7还是找到了33个囚犯的解. 附件中是修改以后的程序和33,34个囚犯的解 wine.zip (12.2 KB, 下载次数: 9)

2009-6-10 08:32 上传

点击文件名下载附件

shshsh_0510

程序好像有些问题，check4中的 if(sa[a]|sa[b]) !=(sa[c]|sa[d]) continue; 是不是应该为： if(((sa[a]|sa[b]) !=(sa[c]|sa[d])) && ((sa[a]|sa[c]) !=(sa[b]|sa[d])) && ((sa[a]|sa[d]) !=(sa[b]|sa[c])) ) continue; 如果那样的话，34的就不太容易得了。不过我运行了二十几次，最多得到了一个995的，看来还是很有希望