这是一个创建于 1322 天前的主题，其中的信息可能已经有所发展或是发生改变。
这题应该怎么算？
第 1 条附言 · 2021-04-20 19:45:16 +08:00
这道题不一定有解，这个只是别人问我的，但是我自己又不会……
 |
101
cslive 2021-04-21 16:29:46 +08:00
8 瓶水 6 个老鼠，2 瓶有毒，还要算法？？？？，直接试简单粗暴，试到老鼠死
|
 |
102
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 的对应列 |
 |
103
Jealee 2021-04-21 16:36:58 +08:00  1
123 234 345 456 567 678
这样不知道行不行 |
 |
105
j717273419 2021-04-21 16:48:25 +08:00
@touchwithe 不对吧，全死了 a 是有毒的，但是怎么确定另外一个是哪瓶有毒呢？你已经把 a 污染了所有的样本了。
|
 |
106
mxT52CRuqR6o5 2021-04-21 16:50:56 +08:00
信息论的题目，本质就是设计一种编码
|
 |
107
liprais 2021-04-21 16:51:38 +08:00
这个问题一楼就解答完了你们到底在吵啥
|
 |
108
lff0305 2021-04-21 17:00:39 +08:00
#85 正解，写个程序验证下是正确的
|
 |
109
qaz168000 2021-04-21 17:00:48 +08:00
@hm20062006ok 这个单次校验应该是指每只老鼠只能用 1 次吧？要没有这个限制，就直接两只一瓶一瓶来，试到死就有结果了...
|
 |
111
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 然后就可以得出哪杯水有毒了！ |
|
112
NEVERCODE 2021-04-21 17:19:16 +08:00
@NEVERCODE 上面第 2 写错了一点：
2. 但实际上，是两瓶未知的水，用同样的方法，可以得出红框外的结论，A 小鼠喝 12 水，B 小鼠喝 13 水，C 小鼠喝 45 水，D 小鼠喝 46 水，剩下的两杯水 EF 小鼠各一杯，用 1 的方法可以推断 |
 |
113
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); 试了下应该是可以的 |
|
116
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 |
 |
117
lafree317 2021-04-21 17:53:58 +08:00 1
循环一次....死了就有毒 两只耗子就够了 把剩下的放了吧
|
 |
118
jiorix 2021-04-21 18:17:55 +08:00
想问一下为什么一只老鼠怼一瓶水不行？每瓶水和每只老鼠都是只参与一次啊～～
|
 |
120
err1y 2021-04-21 20:35:21 +08:00 via iPhone
感觉跟汉明码有点像，水按数字编号，12345678，老鼠用 abcdef 编号
a 喝 12 混合水，b 喝 34 混合，c 喝 56，d 喝 78 。 如果 abcd 中只有一个死，则死的那个喝的两个水就都是毒。 如果 abcd 中有两个死了，用 ef 两只老鼠分别去喝死的那两只老鼠喝的其中一杯，如果中了，则喝的是毒，否则没喝的那瓶是毒 |
 |
121
hahaayaoyaoyao 2021-04-21 21:01:41 +08:00
|
|
122
hahaayaoyaoyao 2021-04-21 21:03:46 +08:00
@hahaayaoyaoyao 两两组合, 组成 6 瓶水
|
 |
123
evilStart 2021-04-21 21:16:19 +08:00 via Android
一楼就解答完了为什么能够这么多层楼？
|
 |
124
Godykc 2021-04-21 21:23:14 +08:00 via iPhone
谁能解释下题干强调的单次是啥意思？
按照一楼思路，总共 64 种水的组合，6 只鼠怎么实现“单次”喝完？ |
 |
125
looooooong 2021-04-21 21:29:10 +08:00
@Godykc 可以理解为 1 小时毒发死亡，你也只有 1 小时时间
|
 |
128
snw 2021-04-21 22:16:38 +08:00 via Android
|
 |
130
GTim 2021-04-21 22:36:40 +08:00
@touchwithe lihai
|
 |
131
Xs0ul 2021-04-21 22:41:40 +08:00
|
|
133
GTim 2021-04-21 22:48:04 +08:00
@touchwithe 你的答案挺好的呀 ，在于启发
1. 8 瓶中先拿三两瓶 比如 A，B, C 2. 将 C 往剩余的 5 瓶中都倒入，拿给老鼠喝 3. 如果全死，那么说明 C 有毒，A，B 中有一瓶有毒，剩下一只老鼠，嘿嘿，随便喂一瓶就知道结果了 4. 如果死一只，那么，C 没毒，哪瓶对应的老鼠死了就是哪瓶，A，B 中有一瓶有毒，剩下一只老鼠，嘿嘿，随便喂一瓶就知道结果了 5. 死两只，那么就是哪瓶死了是哪瓶 6. 什么，一只都没死，不可能的事。 |
 |
136
dangyuluo 2021-04-22 01:28:43 +08:00
没说多少个杯子
|
|
137
NEVERCODE 2021-04-22 10:20:18 +08:00
@snw 确实，当时没想到。那就组成 12，13，34，35，四杯水，然后 6 7 各一杯，正好六只老鼠，然后根据死亡情况再去排除 8 的水
|
 |
138
JustLookBy 2021-04-22 14:54:57 +08:00 1
1 楼就是说了个理论，结果是行不通的。
@lff0305 #116 @Xs0ul #85 俩楼给出了正确解，至于怎么有逻辑的推出这个解 感觉还没答案。。 我写了个在线验证答案的简单页面，同学们有需要可以来验证下自己答案先。。。一堆给了错误答案的 https://abiudoit.github.io/algorithmTest/checkPoison.html |
|
139
lff0305 2021-04-22 21:46:33 +08:00
@JustLookBy
没那么复杂，穷举+验证就行了 本来最开始用的是 6 个循环每个循环 1~255 发现时间不可接受（ 255^6) 后来看 85 楼的结果行 1 的个数是相同的（也就是老鼠喝相同数目的瓶子） 所以就做了个假设：老鼠喝的瓶子的数目是相同的 这样循环的次数就少多了 每个老鼠喝一瓶 无解 每个老鼠喝两瓶 无解 每个老鼠喝三瓶 很多解 至于每个老鼠喝不同的数目的瓶子，没实验，也无法证明一定不存在解 |
|
140
Xs0ul 2021-04-23 00:24:18 +08:00
@lff0305 #139 有一点，很多解实际是等价的，交换行列实际上相当于交换瓶子或者老鼠的顺序，本质上没有差别。所以我比较好奇除了全是 3 瓶以外的解
|
 |
141
yucongo 2021-04-23 12:59:18 +08:00
@JustLookBy 大佬这个程序 https://abiudoit.github.io/algorithmTest/checkPoison.html 给的反馈啥意思？
例如（第 5 号老鼠不想喝药啦:)）， 10000000 01000000 00100000 00010000 00001000 00000000 反馈说：失败,毒药 0,1 和 0,2 存在相同死亡情况: 000000 毒药是 5,6,7 中的两瓶时，所有老鼠都安全吧 |
|
142
JustLookBy 2021-04-23 15:05:33 +08:00
@yucongo 这个意思是，当毒药是 0 号 1 号 或者毒药是 0 号，2 号的时候，老鼠的死亡都是 000000，既都没有老鼠死亡。
老鼠死亡结果必须和毒药结果 是 [多对一] 或 [一对一] 的关系，否则不能通过老鼠死亡情况推出哪俩瓶有毒 |
|
143
JustLookBy 2021-04-23 15:17:56 +08:00
@yucongo 你说的没错。。对你们来说应该是 5 6 和 5 7， 不是 0 1 和 0 2 。 消息提示的有点问题
|
|
145
snw 2021-04-24 06:00:23 +08:00 via Android
@NEVERCODE
依然不行。现在喝(12)和(13)的两只老鼠死了，你无法判断是(1,8)有毒还是(1,2)有毒。 |
|
146
hahaayaoyaoyao 2021-04-24 22:36:57 +08:00
|
Select Language