mathe
发表于 2009-6-9 15:10:18
得到一个N=37的解.现在的结果是37人解决2111桶酒问题.
附件中每行数字左边18比特,右边19比特.
本来以为还可以得到更好的结果,不过好像是由于我的概率估计公式不够准确,K更大时现在的我的概率公式就完全不准了,所以结果不对.
mathe
发表于 2009-6-9 15:30:05
现在找到了33个囚犯的方案.
附件中分别给出了33~35个囚犯的解决方案.
其中文件中每一行两个整数,前面整数18比特,后面的15~17比特.合起来是33~35比特的数
shshsh_0510
发表于 2009-6-9 16:47:34
呵呵，想不到这概率的方法效果这么好！居然能低于35！
沾程序验证的事就只有看你们这帮快手干了。
shshsh_0510
发表于 2009-6-9 17:06:35
48#说的产生14个24位的随机数，这些数是你结果中的第二列吗？你结果中的数看起来都不相同啊
mathe
发表于 2009-6-9 17:17:36
对的,第一列是构造值,第二列是随机的(所以看起来都不相同).唯一控制的是0,1产生的概率
shshsh_0510
发表于 2009-6-9 17:19:59
那上边你说的那个“14个”体现在哪了？
mathe
发表于 2009-6-9 17:40:50
每个第一个数字相同的数会产生14个第二个数(当然后面的程序会淘汰掉部分数据),所以实际上最终结果是对每个第一个数字,对应第二个数字小于14.
这个说的14仅仅对于39个囚徒的情况,而对于其它情况,这个数字可能不同.(这里这个数字对应程序中参数m)
shshsh_0510
发表于 2009-6-9 19:44:43
明白了，多谢
mathe
发表于 2009-6-10 08:00:06
发现前面的程序有个BUG.其中函数check3没有检查完所有情况,需要修改一下.
修改以后,通过K=7还是找到了33个囚犯的解.
附件中是修改以后的程序和33,34个囚犯的解
shshsh_0510
发表于 2009-6-10 09:13:30
程序好像有些问题，check4中的
if(sa|sa) !=(sa|sa) continue;
是不是应该为：
if(((sa|sa) !=(sa|sa)) &&((sa|sa) !=(sa|sa))
&& ((sa|sa) !=(sa|sa)) ) continue;
如果那样的话，34的就不太容易得了。不过我运行了二十几次，最多得到了一个995的，看来还是很有希望
页:
1
2
3
4
5
[6]
7
8
9
10
11
12
13
14
15