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

[eroko]

这题应该怎么算？

[Elethom]

@snw
两瓶毒的情况，应该是对半分的。ABCD 、EFGH 、ABEF 、CDGH 、ACEG 、BDFH 这样子，可以理解为一个西瓜切三刀（就是我上面那个比喻），扩展到无限维度就可以解决更多瓶子的问题。上面我说五瓶确实是草率了，我道歉。

写了一段代码验证：
（ Swift 的编译检查不怎么待见 bitwise calculation 的样子，所以写成 Int 了，见谅）
https://gist.github.com/Elethom/e31af1a9f576d150aa691c5468bed379

[tianxia]

不需要什么算法，直接给 6 只耗子分别喂 6 瓶水，就保证单次检验出结果，不信可以尝试

[Mutoo]

@tianxia 是呀
6 只都没事，剩下两瓶有毒
5 只没事，1 只喝的是毒，剩下一瓶有毒
4 只没事，2 只喝的是毒。
根本不需要什么算法。

[tianxia]

@Elethom 会导致毒药剂量不够，毒不死

[Elethom]

@Mutoo
剩下的是两瓶。

[tianxia]

@Elethom 实际给你操作，保证一次出结果

[Mutoo]

@Elethom 对哦，走神了

[chrisouta]

https://en.wikipedia.org/wiki/Group_testing
果然深似海，学到了很多，感谢楼主的问题。
现有的理论还没有保证最优的算法，问题确实需要对矩阵进行搜索，wiki 里提到了几种搜索方法可以参考。
甚至还有老鼠有概率死有概率不死的扩展，更复杂了🐶

[Elethom]

#41 是我傻逼了。下界是 5 没错但是重新算了下上界还要再高一点。

[Elethom]

@Elethom 大概在 log(2, n) * 2 * log(2, n/2)

[chrisouta]

2 瓶毒，上界应该是下界加 1，六只老鼠，所以问题一定有解，看来 6 只老鼠不是随随便便选的。
In scenarios where there are two or more defectives, the generalised binary-splitting algorithm still produces near-optimal results, requiring at most d-1 tests above the information lower bound where d is the number of defectives.

[Elethom]

@chrisouta
的确比看起来更复杂。 😭

[elfive]

8 瓶水放到 9 宫格里，每行每列取样混在一起，正好 3 行 3 列，6 只耗子一次性喝混出来的一瓶，就可以了。

这就是二维的奇偶校验。

[chrisouta]

#53 两瓶毒在对角上无法区分在主对角还是次对角吧。这里的加法运算毕竟不是模二加，是直接或运算，跟奇偶校验应该不同。

[popil1987]

按照一楼的解法：8 瓶里 2 瓶有毒共 28 种组合（状态），那么 5 只老鼠可以表示 32 种状态就可以了吧，是不是能让一只老鼠去做电击实验？

[SlipStupig]

@suisetai 万一老鼠都变异了毒不死怎么办呢。。

[palfortime]

@noe132 #1 这种二进制编码的方案只能找 64 瓶里只有 1 瓶有毒的情况吧，混合出来的 64 瓶远远不只 1 瓶有毒。多瓶叠加在一起，无法用 6 只老鼠来找出吧。
没有想到单次校验的。
我的想法是 8 瓶分成 2 批，再用这种位编码的方式来找出每组里有毒的。具体会产生两种情况：
2 批都有死或者都没有死，这样用位编码方式来算，用 4 只来试就可以。
另外一种情况就是只有 1 批有死。这种情况有分为两种子情况：1. 没死的那批，00 是有毒的。2. 2 瓶有毒都在 1 批。
针对子情况 1，找没有死的去喝 00，挂了就出结果。没有挂的话，那么现在还活着的还有 4 只，4 只对应有毒的那批的 4 瓶。那么结果也可以出来。

[dicc]

@Elethom #45 剩下两瓶，一有一无毒，你再喝一瓶

[nieyujiang]

六个老鼠一只一瓶,面试官再喝一瓶.最后一瓶自己的.

[man9820]

@suisetai 他要一次性，大概意思是同时进行，要不方式太多了