8 瓶水 2 瓶有毒 6 个耗子 要求单次检验出结果

2021-04-20 18:58:15 +08:00
 eroko
这题应该怎么算?
11671 次点击
所在节点    问与答
146 条回复
cslive
2021-04-21 16:29:46 +08:00
8 瓶水 6 个老鼠,2 瓶有毒,还要算法????,直接试简单粗暴,试到老鼠死
chrisouta
2021-04-21 16:32:09 +08:00
输入 pattern
[[1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0]
[0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 0]
[0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 1 0]
[0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1]
[0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1]]
#85 矩阵得到的老鼠死亡 pattern
[[0 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1 1]
[1 1 1 1 1 1 1 1 0 0 1 0 0 1 1 1 1 1 0 1 0 0 1 0 0 1 1 0]
[0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1]
[1 1 1 1 1 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 1 1 0 1 0 1 0 1]
[0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 0]
[1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 0 0 0 1 1 1 0 0 0]]
死亡 pattern 是没有重复列的,需要验证的情况可以查看输入 pattern 的对应列
Jealee
2021-04-21 16:36:58 +08:00
123 234 345 456 567 678
这样不知道行不行
shyrock
2021-04-21 16:38:16 +08:00
@Xs0ul #85 这个测试矩阵怎么构造的?
j717273419
2021-04-21 16:48:25 +08:00
@touchwithe 不对吧,全死了 a 是有毒的,但是怎么确定另外一个是哪瓶有毒呢?你已经把 a 污染了所有的样本了。
mxT52CRuqR6o5
2021-04-21 16:50:56 +08:00
信息论的题目,本质就是设计一种编码
liprais
2021-04-21 16:51:38 +08:00
这个问题一楼就解答完了你们到底在吵啥
lff0305
2021-04-21 17:00:39 +08:00
#85 正解,写个程序验证下是正确的
qaz168000
2021-04-21 17:00:48 +08:00
@hm20062006ok 这个单次校验应该是指每只老鼠只能用 1 次吧?要没有这个限制,就直接两只一瓶一瓶来,试到死就有结果了...
idyu
2021-04-21 17:11:26 +08:00
@Xs0ul 抱歉回错人了,你的是对的
NEVERCODE
2021-04-21 17:18:18 +08:00
很简单:

1. 假设,平均下来,4 瓶水,3 只鼠,那么我们可以用红框里的解法,A 小鼠喝 12 水,B 小鼠和 13 水,C 小鼠喝 4 水,死的是一只 A 小鼠,则 2 号有毒;一只 B 小鼠则 3 号有毒; A 小鼠和 B 小鼠同时死亡,则 1 水有毒; 4 小鼠死亡则 4 号有毒
2. 但实际上,是两瓶未知的水,用同样的方法,可以得出红框外的结论,A 小鼠喝 12 水,B 小鼠喝 13 水,C 小鼠喝 45 水,D 小鼠喝 56 水,剩下的 EF 小鼠各一杯,用上面的方法可以推断

i.loli.net/2021/04/21/AdZLxobNhHjJenB.png

然后就可以得出哪杯水有毒了!
NEVERCODE
2021-04-21 17:19:16 +08:00
@NEVERCODE 上面第 2 写错了一点:

2. 但实际上,是两瓶未知的水,用同样的方法,可以得出红框外的结论,A 小鼠喝 12 水,B 小鼠喝 13 水,C 小鼠喝 45 水,D 小鼠喝 46 水,剩下的两杯水 EF 小鼠各一杯,用 1 的方法可以推断
idyu
2021-04-21 17:22:26 +08:00
只要死亡组的二进制或运算之后的值在所有组或运算里是唯一的就可以了,PHP 代码:

$r = []; //分配方案
$s = []; //所有可能发生的死亡组合数组
for($i=0b00000001;$i<=0b11111111;$i++){
if(in_array($i,$s)) continue;
$isok = true;
$ts = [$i]; //当前组可能发生的死亡组合数组
foreach($r as $n){ //遍历已有分配方案,是否有重复的死亡组合
$t = $n|$i; //死亡或运算
$ts[] = $t; //死亡放到当前数组
if(in_array($t,$s)) { //如果死亡组合已经存在 s 里,无效
$isok = false;
break;
}
}
if($isok){
$s = array_unique(array_merge($s,$ts)); //如果当前组有效,当前组的死亡数组放到总数组
$r[] = $i;
}
}
var_dump($r);
试了下应该是可以的
idyu
2021-04-21 17:25:36 +08:00
@idyu

可行的结果之一:
00100000
00101010
00110100
00111111
10000000
11000001
zhyl
2021-04-21 17:52:08 +08:00
@elfive 这样两瓶有毒的话可能会死 4 只。。
lff0305
2021-04-21 17:53:07 +08:00
受 85 楼启发写了个程序,其实远不止一组解,比如
六只老鼠
m0=00000111
m1=00011001
m2=00101010
m3=00110100
m4=01001100
m5=01010010

毒药在
01 的时候,0125 死
02 的时候 0134 死,等等等,0<=i<j<=7, 每种(i,j)的组合死法都是不同的,就可以知道那两瓶是毒药,

类似的还有

00000111
00011001
00101010
00110100
01001100
10100001

00000111
00011001
00101010
00110100
01010010
10100001
lafree317
2021-04-21 17:53:58 +08:00
循环一次....死了就有毒 两只耗子就够了 把剩下的放了吧
jiorix
2021-04-21 18:17:55 +08:00
想问一下为什么一只老鼠怼一瓶水不行?每瓶水和每只老鼠都是只参与一次啊~~
jiorix
2021-04-21 18:23:06 +08:00
@jiorix 哦哦,死一只老鼠剩下的 2 瓶水就……
err1y
2021-04-21 20:35:21 +08:00
感觉跟汉明码有点像,水按数字编号,12345678,老鼠用 abcdef 编号


a 喝 12 混合水,b 喝 34 混合,c 喝 56,d 喝 78 。
如果 abcd 中只有一个死,则死的那个喝的两个水就都是毒。
如果 abcd 中有两个死了,用 ef 两只老鼠分别去喝死的那两只老鼠喝的其中一杯,如果中了,则喝的是毒,否则没喝的那瓶是毒

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://tanronggui.xyz/t/771969

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX