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

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

  [复制链接]
 楼主| 发表于 2009-6-9 15:10:18 | 显示全部楼层
K6N37.zip (10.16 KB, 下载次数: 4)
得到一个N=37的解.现在的结果是37人解决2111桶酒问题.
附件中每行数字左边18比特,右边19比特.
本来以为还可以得到更好的结果,不过好像是由于我的概率估计公式不够准确,K更大时现在的我的概率公式就完全不准了,所以结果不对.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-9 15:30:05 | 显示全部楼层
wine.zip (16.84 KB, 下载次数: 10)
现在找到了33个囚犯的方案.
附件中分别给出了33~35个囚犯的解决方案.
其中文件中每一行两个整数,前面整数18比特,后面的15~17比特.合起来是33~35比特的数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-9 16:47:34 | 显示全部楼层
呵呵,想不到这概率的方法效果这么好!居然能低于35!
沾程序验证的事就只有看你们这帮快手干了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-9 17:06:35 | 显示全部楼层
48#说的产生14个24位的随机数,这些数是你结果中的第二列吗?你结果中的数看起来都不相同啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-9 17:17:36 | 显示全部楼层
对的,第一列是构造值,第二列是随机的(所以看起来都不相同).唯一控制的是0,1产生的概率
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-9 17:19:59 | 显示全部楼层
那上边你说的那个“14个”体现在哪了?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-9 17:40:50 | 显示全部楼层
每个第一个数字相同的数会产生14个第二个数(当然后面的程序会淘汰掉部分数据),所以实际上最终结果是对每个第一个数字,对应第二个数字小于14.
这个说的14仅仅对于39个囚徒的情况,而对于其它情况,这个数字可能不同.(这里这个数字对应程序中参数m)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-9 19:44:43 | 显示全部楼层
明白了,多谢
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-10 08:00:06 | 显示全部楼层
发现前面的程序有个BUG.其中函数check3没有检查完所有情况,需要修改一下.
修改以后,通过K=7还是找到了33个囚犯的解.
附件中是修改以后的程序和33,34个囚犯的解

wine.zip (12.2 KB, 下载次数: 9)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-10 09:13:30 | 显示全部楼层
程序好像有些问题,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的,看来还是很有希望
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 20:13 , Processed in 0.048780 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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