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 单次检验
|