这是一个创建于 1311 天前的主题，其中的信息可能已经有所发展或是发生改变。
这题应该怎么算？
第 1 条附言 · 2021-04-20 19:45:16 +08:00
这道题不一定有解，这个只是别人问我的，但是我自己又不会……
 |
1
noe132 2021-04-20 19:12:13 +08:00  26
将 2 瓶水两两组合混合一共 8x8=64 种状态，编码为 0-63，每种状态代表任意 2 瓶水的 combo，6 只耗子=6bit，每只耗子毒死 /存货代表 1bit，6bit 一共 2^6 = 64 种状态，将上面组合的 64 种状态再根据每一种状态对应二进制位混合出 6 瓶水，给 6 只耗子喝，根据最后结果就可以推算出来 8 瓶水哪 2 瓶有毒了。
|
 |
2
Samuelcc 2021-04-20 19:13:23 +08:00 via Android
详细说下单次检验是什么意思？是不能看任何前置的检验结果吗？
感觉思路应该和混合水缩小范围相关 |
 |
3
touchwithe 2021-04-20 19:16:05 +08:00 via iPhone 5
1. 拿出一瓶水，记为 A，向剩余 7 瓶中都倒入一点。
2. 7 中拿出 6 瓶，剩余一瓶记为 B 。 3. 6 瓶水分别喂 6 只耗子。 可能的结果： 死一只，对应喝的水有毒，B 有毒。 死两只，对应喝的水有毒。 全死了，A 有毒。 |
 |
4
l00t 2021-04-20 19:18:17 +08:00 3
一次就检验出来，那就不能等待之前的喝药结果了。
没仔细验算过，你试试这个思路可行否： 将 8 按 2 进制拆出来，得到 8 个三位二进制数。看每个位上，是 0 的派一只老鼠，是 1 的派一只老鼠，这样三位三个 01，正好 6 只。喝完后看结果，根据死的老鼠找出毒药。 |
 |
5
LZSZ 2021-04-20 19:22:10 +08:00
几瓶混在一起试错
|
|
6
touchwithe 2021-04-20 19:22:20 +08:00 via iPhone
@touchwithe #3 想错了，不对。还是一楼的方法好！
|
 |
8
zxCoder 2021-04-20 19:36:05 +08:00 1
@noe132 能再详细解释一下吗大佬
将上面组合的 64 种状态再根据每一种状态对应二进制位混合出 6 瓶水，给 6 只耗子喝，根据最后结果就可以推算出来 8 瓶水哪 2 瓶有毒了。 这段读得有点费劲。。。 |
 |
9
xdeng 2021-04-20 19:36:09 +08:00 1
@eroko 单次检验就是喂一次就能得到结果 那不就是 6+2=8 吗。。。拿六瓶喂六只 都没死 那就是剩下的 2 瓶有毒吗？死了对应的那瓶就有毒？是我理解错了吗？
|
 |
10
fisherman0459 2021-04-20 19:37:42 +08:00 1
@xdeng 如果六只里面只死了一只呢？
|
 |
11
qsmd42 2021-04-20 19:38:34 +08:00 8
1 2 3 4 5 6 7 8
V V V V V V A B C D E F 这样? |
 |
12
xinh 2021-04-20 19:42:32 +08:00 via iPhone
2 楼的那种二进制解法，在李永乐的视频里学的，有一期讲这个数学
|
|
13
xdeng 2021-04-20 19:53:29 +08:00
@fisherman0459 啊这。。。一楼字多一楼肯定对 哈哈哈
|
 |
17
AngryPanda 2021-04-20 20:22:07 +08:00 via iPhone
2 只耗子🐭就检验出来了
|
 |
18
hm20062006ok 2021-04-20 20:24:02 +08:00
@noe132 "将 2 瓶水两两组合混合一共 8x8=64 种状态" 不是只有 28 瓶(两两混合后的)+ 8 瓶(原始的) = 36 种状态吗？
|
 |
19
AndyVerne 2021-04-20 20:34:26 +08:00
8 瓶水，分四组（一组两瓶），一只老鼠喝一组如果
|
|
20
AndyVerne 2021-04-20 20:37:45 +08:00
@AndyVerne 8 瓶水，分四组（一组两瓶），一只老鼠喝一组，还有 2 只老鼠多出来，
如果 3 组没事，没事，那么有毒的一组就包括那两瓶有毒的水 如果 2 组出事，拿出两组的其中各一瓶，用多出的两只老鼠，根据情况对应排除，就能得到结果 |
 |
21
dethan 2021-04-20 20:56:41 +08:00 via Android
好残忍，鼠鼠那么可爱。。
|
 |
24
suisetai 2021-04-20 21:07:18 +08:00 via iPhone 10
拿一只老鼠一瓶瓶喂 死了就换下一只... 顶多用两只 当然 撑死不算
|
 |
25
ro2020 2021-04-20 21:33:39 +08:00
4 楼方法是正确的
|
 |
27
akira 2021-04-20 21:50:48 +08:00
遇到这种问题 一律用 2 进制的思路去考虑 肯定对的
|
 |
28
looooooong 2021-04-20 22:06:21 +08:00 via iPhone
|
|
29
ro2020 2021-04-20 22:20:58 +08:00
@looooooong 是的，我刚才在算的时候也发现了问题，这个方法不对
|
 |
31
chrisouta 2021-04-20 23:42:21 +08:00
可以把所有毒药可能的组合写到一个二进制矩阵 S 中，每行代表一种组合，一共有 C(8,2)行，8 列。相应的老鼠编码二进制矩阵记为 M(8,k), 每一列代表一只老鼠的喝药方案, 六只老鼠 k=6 。有 Binary(SM) = X，这里 X 也是二进制矩阵(大于零的元素视为 1)，可以为一个二进制 BCD 矩阵(类似上面李永乐老师的 100 瓶毒药编码矩阵)。只要解出来 M 矩阵就可以找出编码方式。上面李永乐老师的例子里 S 为单位矩阵，所以老鼠编码矩阵就等于 BCD 矩阵，不需要解，这个可能要稍微麻烦点了。
|
|
33
hm20062006ok 2021-04-21 00:25:05 +08:00
8 瓶毒药两两混合一次得到:1+2,1+3...1+8,2+3,2+4,...2+8,3+4,3+5...3+8......7+8. 一共 28 瓶混合物，编号为 1-28， 转换为 5 位数的二进制（ 00001.....11100),按照上面回答种视频说的，小鼠 1 喝所有二进制第一位为 1 的混合物，小鼠 2 喝所有二进制第二位为 1 的混合物..... 需要 5 只小鼠可以检验出结果。
|
|
34
noe132 2021-04-21 00:38:11 +08:00
@hm20062006ok 一开始我也是这么想的。但是毒药是或运算，2 瓶只要有 1 瓶是毒药，混合出来就都是毒药了。实际上按照这个逻辑，应该检验 8 瓶里面哪 6 瓶不是毒药
|
|
35
hm20062006ok 2021-04-21 00:50:45 +08:00
@noe132 是的， 想错了
|
 |
36
Elethom 2021-04-21 01:00:07 +08:00 via iPhone
其实五只就够了，这个问题一分钟答不上来的建议转行，这智商不适合做技术。
送一个拓展问题：四维空间的一个西瓜切五刀可以分成多少块？切六刀呢？ 再进阶一步：m 维空间的一个西瓜切 n 刀可以分成多少块？（ m > 3，n > m ）求通解。 |
 |
38
snw 2021-04-21 02:49:15 +08:00 via Android 1
|
|
39
snw 2021-04-21 03:49:33 +08:00 via Android
顺带一提，这个链接提出的解法也是不对的。
blog.csdn.net/kingoverthecloud/article/details/4068[去掉此方括号]6129 反例：无法区分(000, 110)为毒药与(010, 100)为毒药这两种情况。 |
|
41
Elethom 2021-04-21 06:43:37 +08:00 via iPhone
@snw
两瓶毒的情况，应该是对半分的。ABCD 、EFGH 、ABEF 、CDGH 、ACEG 、BDFH 这样子，可以理解为一个西瓜切三刀（就是我上面那个比喻），扩展到无限维度就可以解决更多瓶子的问题。上面我说五瓶确实是草率了，我道歉。 写了一段代码验证： （ Swift 的编译检查不怎么待见 bitwise calculation 的样子，所以写成 Int 了，见谅） https://gist.github.com/Elethom/e31af1a9f576d150aa691c5468bed379 |
 |
42
tianxia 2021-04-21 06:44:30 +08:00 via Android 10
不需要什么算法，直接给 6 只耗子分别喂 6 瓶水，就保证单次检验出结果，不信可以尝试
|
 |
43
Mutoo 2021-04-21 06:54:43 +08:00
|
|
48
chrisouta 2021-04-21 07:05:06 +08:00 3
https://en.wikipedia.org/wiki/Group_testing
果然深似海，学到了很多，感谢楼主的问题。 现有的理论还没有保证最优的算法，问题确实需要对矩阵进行搜索，wiki 里提到了几种搜索方法可以参考。 甚至还有老鼠有概率死有概率不死的扩展，更复杂了🐶 |
|
49
Elethom 2021-04-21 07:17:46 +08:00
#41 是我傻逼了。下界是 5 没错但是重新算了下上界还要再高一点。
|
|
51
chrisouta 2021-04-21 07:33:40 +08:00
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. |
 |
53
elfive 2021-04-21 07:38:17 +08:00 via iPhone 5
8 瓶水放到 9 宫格里，每行每列取样混在一起，正好 3 行 3 列，6 只耗子一次性喝混出来的一瓶，就可以了。
这就是二维的奇偶校验。 |
|
54
chrisouta 2021-04-21 07:55:48 +08:00
#53 两瓶毒在对角上无法区分在主对角还是次对角吧。这里的加法运算毕竟不是模二加，是直接或运算，跟奇偶校验应该不同。
|
 |
55
popil1987 2021-04-21 08:40:48 +08:00
按照一楼的解法：8 瓶里 2 瓶有毒共 28 种组合（状态），那么 5 只老鼠可以表示 32 种状态就可以了吧，是不是能让一只老鼠去做电击实验？
|
 |
56
SlipStupig 2021-04-21 10:48:36 +08:00
@suisetai 万一老鼠都变异了毒不死怎么办呢。。
|
 |
57
palfortime 2021-04-21 11:18:28 +08:00 via Android
@noe132 #1 这种二进制编码的方案只能找 64 瓶里只有 1 瓶有毒的情况吧，混合出来的 64 瓶远远不只 1 瓶有毒。多瓶叠加在一起，无法用 6 只老鼠来找出吧。
没有想到单次校验的。 我的想法是 8 瓶分成 2 批，再用这种位编码的方式来找出每组里有毒的。具体会产生两种情况： 2 批都有死或者都没有死，这样用位编码方式来算，用 4 只来试就可以。 另外一种情况就是只有 1 批有死。这种情况有分为两种子情况：1. 没死的那批，00 是有毒的。2. 2 瓶有毒都在 1 批。 针对子情况 1，找没有死的去喝 00，挂了就出结果。没有挂的话，那么现在还活着的还有 4 只，4 只对应有毒的那批的 4 瓶。那么结果也可以出来。 |
 |
59
nieyujiang 2021-04-21 11:27:52 +08:00 3
六个老鼠一只一瓶,面试官再喝一瓶.最后一瓶自己的.
|
 |
61
tinytoadd 2021-04-21 11:37:59 +08:00 via Android
@tianxia #42 这个有点问题，6 瓶里有一瓶有毒，那么无法 判断剩下的两瓶里哪一瓶有毒
|
 |
62
sujin190 2021-04-21 11:42:49 +08:00
这不就是二分法查找么，不很简单么，也需要讨论的这么复杂么。。。
|
 |
63
bk201 2021-04-21 11:50:23 +08:00
@nieyujiang 你自己不用喝，结果就出来了呀
|
 |
64
cking 2021-04-21 11:52:37 +08:00
随便拿一瓶 给老鼠喝 然后把老鼠弄死 告知实验结果 这瓶有毒 然后这题结束 因为还有一瓶有毒的 肯定不会尝试 所以这题一次就结果了
|
 |
66
iwasthere 2021-04-21 12:30:18 +08:00 via iPhone
数学渣，评论看的懵逼
|
|
67
sujin190 2021-04-21 12:42:04 +08:00
@snw #65 8 瓶水分成 4 瓶两堆，给两只老鼠喝
如果都死，那就是两个 4 瓶里各 1 瓶有毒，然后每个 4 瓶再分成 2 瓶每堆，然后没边再各取 2 瓶一堆给两只老鼠喝，就能确定有毒的在哪 2 瓶里，最后两只老鼠在试剩下分成两堆的 4 瓶就能确定哪瓶有毒了啊 如果只有一边死，那就确定两瓶有毒的都在一边的四瓶里，另外 4 瓶就可以扔了，然后再把有毒的 4 瓶分成 2 瓶两堆，给两只老鼠喝，重复刚才的流程就是了啊 这不简单么，有啥好讨论的 |
 |
68
Dvel 2021-04-21 12:42:58 +08:00
这题目出错了，8-2=6，这题不用算法，直接怼就行，应该是更多的瓶子或更少的老鼠。
|
 |
72
cyrbuzz 2021-04-21 13:28:09 +08:00
分成两组 1-4 。
每组 4 瓶编号 1-4 。 用三只， 一只喝 1,3，一只喝 2,3，一只喝 1,2 。 另外一组分别喝，1,3 2,3 和 4 。 A: 13 和 23 死掉的情况，看另一只喝 1,2，死了，1 和 2 都有毒。没死，3 确定有毒，4 可能有毒看下一组情况。 B: 13 死了，23 没死，1 有毒，4 可能有毒看下一组情况。 C: 13 没死，23 死了，2 有毒，4 可能有毒看下一组情况。 D: 13 和 23 都没死，4 可能有毒看下一组情况。 此时看另一组： A1: 13 和 23 死掉的情况，4 死了，3 和 4 有毒，4 没死，3 和上一组 4 有毒。 B1: 13 死掉了，23 没死，4 死了，14 有毒，4 没死，1 和上一组 4 有毒。 C1: 13 没死，23 死了，24 或者 2 和上一组 4 。 D1: 13 和 23 都没死，4 死了，4 和上组死掉的那个没死就是上组 4，4 没死，把上组的`可能`换成`肯定`。 |
|
73
Samuelcc 2021-04-21 13:33:33 +08:00 1
搜了一下，感觉应该是找到正解了。这道题目是 group testing 问题中的 non-adaptive 情况，应该是这类型题目最难的一种变体。解法是构建 t-separable 的矩阵进行测试，测试后将结果还原。
这篇文章有比较详细的论述，有兴趣的可以看看 https://people.cs.umass.edu/~arya/courses/690T/lecture14.pdf |
 |
74
rationa1cuzz 2021-04-21 13:41:43 +08:00
@cyrbuzz 两组 X 、Y 假设都在 X 组 A 鼠(13) B 鼠(23) C 鼠(12) 假设 12 都是毒药 ABC 都死 假设 13 都是毒药 ABC 都死
|
 |
76
ElmerZhang 2021-04-21 14:12:56 +08:00
假设 8 瓶水为 1-8，第一轮先给一只老鼠喝 1+2+3，另一只老鼠喝 4+5+6 。
假如某一只老鼠死掉，最多再用两只老鼠即可找出其中有毒的水。剩下的 7 、8 再用一只就可以找出有毒的水。 假如第一轮都没死，就是 7 、8 有毒。 |
|
77
ElmerZhang 2021-04-21 14:13:49 +08:00
看错题目，要求单次，我再想想
|
|
78
cyrbuzz 2021-04-21 14:17:35 +08:00
@rationa1cuzz 额，说的是= =，少一组验证。
|
|
79
ElmerZhang 2021-04-21 14:21:59 +08:00
仍然编号 1-8，6 只老鼠分别喝 1+2 2+3 3+4 5+6 6+7 7+8 。
想了一些用例，应该是可解的。 |
 |
80
wuxinling 2021-04-21 14:32:25 +08:00
如果水多一些还需要好好考虑，
|
 |
81
Xs0ul 2021-04-21 14:44:23 +08:00
@ElmerZhang #79 13 和 23 是一样的，都是前三只都死
|
 |
82
Otho 2021-04-21 14:52:52 +08:00
@ElmerZhang #79 1+2 2+3 3+4 喝完都死了 5+6 6+7 7+8 没事 ，确定不了吧
|
 |
83
igwen6w 2021-04-21 14:55:58 +08:00
@ElmerZhang 看 11 楼
|
 |
84
tegusi 2021-04-21 15:10:30 +08:00
1 楼的编码没看懂…一个编码矩阵有一行一列共有 15 个元素结果都是死亡，6 个小白鼠怎么能推断出最后的信息？
|
|
85
Xs0ul 2021-04-21 15:15:01 +08:00 4
@Samuelcc #73
按这个介绍，随机出了一个可行的解： [[0, 0, 1, 1, 0, 0, 0, 1], [1, 0, 1, 0, 0, 1, 0, 0], [0, 0, 1, 0, 1, 0, 1, 0], [1, 0, 0, 1, 0, 0, 1, 0], [0, 0, 0, 1, 1, 1, 0, 0], [1, 1, 0, 0, 1, 0, 0, 0]]) |
 |
86
alan7 2021-04-21 15:20:59 +08:00
直接编号 1—6 的老鼠 喝 编号 1-6 的的水
|
 |
88
vermouth1995 2021-04-21 15:25:20 +08:00
@alan7 死一只的时候呢
|
 |
89
MyouiSouth 2021-04-21 15:37:37 +08:00
@vermouth1995 自己再痛饮一杯 （
|
|
90
sujin190 2021-04-21 15:41:43 +08:00
把瓶子编号 1 到 8，8 个瓶子 2 个有毒 2 只老鼠的话，应该每组应该用 6 只瓶子的水，可以用下边这种组合
A 1 2 3 4 5 6 B 3 4 5 6 7 8 C 1 2 3 6 7 8 D 2 3 4 5 6 7 E 1 2 4 5 7 8 F 1 3 4 5 6 8 经过测试，发下只有其中 5 组都死的情况下才能满足两只瓶子有毒的条件，组合方式分别为 A B C D E 组死 {2, 7}有毒 A B C D F 组死 {3, 6}有毒 A B C E F 组死 {8, 1}有毒 A B D E F 组死 {4, 5}有毒 A C D E F 组死 {1, 2}有毒 B C D E F 组死 {8, 7}有毒 不知道有没有覆盖到所有情况了，看条件测试时满足的 |
|
91
MyouiSouth 2021-04-21 15:43:49 +08:00
@chrisouta 但是是 8 瓶水 如果可以确保九宫格的其中一角不放水 应该是可以的吧..?
|
 |
92
foreverstandbyu 2021-04-21 15:49:54 +08:00
10 人一组核酸检测的原理？？
|
|
93
MyouiSouth 2021-04-21 15:52:32 +08:00
@chrisouta 我傻了，如果是小对角好像也不行🧐
|
 |
94
joyhub2140 2021-04-21 15:56:54 +08:00
11 楼最简单了，两两组合，8 个瓶子总共 4 组，花掉 4 只老鼠，可以确定哪两组是有毒的，用剩下 2 只老鼠，可以用排除法（划重点）确定哪两瓶有毒。
这个版本最理想的情况下，可以只花 4 只老鼠，就可以确定有毒的瓶子了。 |
 |
96
aureole999 2021-04-21 16:16:23 +08:00
@joyhub2140 要求单次
|
 |
97
idyu 2021-04-21 16:21:07 +08:00
@Xs0ul #85
不行，很多组合会导致六个全死，6 和 124578，5 和 123678，4 和 123678，3 和 124578 |
|
98
sujin190 2021-04-21 16:21:48 +08:00
@chrisouta #95 似乎 A1 的 4 没死的条件不满足，如果第一组的 13 和 23 都没死，第二组 13 和 23 死掉，4 没死，这种情况下似乎不能确定是第二组的 1 2 有毒，还是第二组的 3 和第一组的 4 有毒
|
 |
99
qaz168000 2021-04-21 16:26:42 +08:00
AB,CD,EF,GH 4 只老鼠
死一只，那结果已经有了，就是对应的 2 瓶水 如果死两只，则拿出对应的两只老鼠的那 4 瓶水，比如 CD GH，还有 2 只老鼠 一只给 C，一只给 G，都死那就是 C 和 G 有毒， C 死，G 活，有毒的是 CH C 活，G 死，有毒的是 DG |
|
100
hm20062006ok 2021-04-21 16:27:47 +08:00
@qaz168000 单次检验
|
Select Language