知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 03 - 小白鼠试毒 ## 题目 有 1000 瓶酒,其中 1 瓶有毒。小白鼠喝到毒酒后会在 T 时间后死亡。现在有 10 只小白鼠,只有一个 T 时间段。如何找出哪一瓶有毒? ## 大白话理解 你是一个国王,有人进贡了 1000 瓶酒,但情报说其中恰好 1 瓶被下了毒。毒药发作需要整整 1 天时间。你只有 10 个死囚(小白鼠)可以试毒,而且必须在 1 天内找到毒酒——因为第二天就要开宴会了。 ``` 暴力做法:一瓶一瓶试 → 最多需要 1000 只老鼠,但我们只有 10 只 聪明做法:让每只老鼠喝多瓶酒,用死亡组合反推毒酒编号 ``` --- ### 核心思想:二进制编码 ``` 关键洞察:10 只老鼠的"死/活"状态可以表示 2^10 = 1024 种结果 而我们要从 1000 瓶酒中找出 1 瓶 → 1000 种可能 1024 > 1000,够用! 每只老鼠对应一个二进制位: 老鼠 1 → 第 1 位(最低位,2^0 = 1) 老鼠 2 → 第 2 位(2^1 = 2) 老鼠 3 → 第 3 位(2^2 = 4) ... 老鼠 10 → 第 10 位(2^9 = 512) ``` ### 操作步骤 ``` 第 1 步:给 1000 瓶酒编号 0~999(用二进制表示 0000000000 ~ 1111100111) 第 2 步:每只老鼠喝对应二进制位为 1 的那些瓶酒 老鼠 1(bit 0):喝编号第 0 位(最低位)为 1 的酒 → 0,2,4,6,8,... 老鼠 2(bit 1):喝编号第 1 位为 1 的酒 → 1,3,5,7,... 老鼠 3(bit 2):喝编号第 2 位为 1 的酒 → 4,5,6,7,12,13,14,15,... ... 第 3 步:T 时间后,观察哪些老鼠死了 死亡老鼠的位组合起来 = 毒酒编号! ``` ### 具体例子 ``` 假设第 666 瓶酒有毒。 666 的二进制 = 1010011010 位号:9 8 7 6 5 4 3 2 1 0 二进制值:1 0 1 0 0 1 1 0 1 0 对应老鼠:⑩ ⑧ ⑤④③ ① 老鼠 10(bit9)、8(bit7)、5(bit4)、4(bit3)、3(bit2)、1(bit0) 喝了第 666 瓶 T 时间后,这 6 只老鼠死了。 死亡组合 → 1010011010 → 十进制 666 → 毒酒找到了! ``` ``` ASCII 图解: 1000 瓶酒编号 0~999: ┌─────┬─────┬─────┬─────┬─────┬─────┬──────────┬─────┐ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ ... │ 999 │ └──┬──┴──┬──┴──┬──┴──┬──┴──┬──┴──┬──┴──────────┴──┬──┘ │ │ │ │ │ │ │ ▼ ▼ ▼ ▼ ▼ ▼ ▼ 每只老鼠喝对应二进制位为 1 的那些酒 老鼠 1 (2^0=1) 喝:0, 2, 4, 6, 8, 10, ...(末位为1的) 老鼠 2 (2^1=2) 喝:2, 3, 6, 7, 10, 11, ...(第2位为1的) 老鼠 3 (2^2=4) 喝:4,5,6,7, 12,13,14,15, ...(第3位为1的) ... T 时间后: 死 = 1,活 = 0 如果老鼠 1、3、5、7、9 死了: 二进制:1010101010 十进制 = 682 → 第 682 瓶有毒! ``` --- ### 为什么 10 只老鼠刚好够? ``` 1000(十进制)= 1111101000(二进制)= 10 位 所以 10 只老鼠的死亡/存活状态 → 2^10 = 1024 种组合 1024 > 1000,编码空间充足。 如果只有 9 只老鼠: 2^9 = 512 < 1000,不够! ``` --- ### 延伸思考 ``` Q1:如果有 2 瓶有毒,需要多少只老鼠? 2 瓶的组合数 = C(1000, 2) ≈ 499500 需要 ⌈log₂(499500)⌉ ≈ 19 只老鼠 实际上更复杂——因为一只老鼠可能同时喝了两瓶毒酒, 二进制编码的方式不再直接适用,需要用组合编码。 Q2:如果有 N 瓶酒 M 只老鼠,关系是什么? 每只老鼠死/活 = 1 bit 信息 M 只老鼠 → 最多 2^M 种结果 因此:N ≤ 2^M → M ≥ log₂(N) 1000 瓶 → M ≥ log₂(1000) ≈ 9.97 → 至少 10 只 Q3:如果有 2 个 T 时间段(可以做两轮实验),能测多少瓶? 第一轮:10 只老鼠,死/活 = 10 bit 信息 第一轮死掉的老鼠无法参与第二轮 第二轮:剩余老鼠,再测一轮 → 最多 (2+1)^10 = 3^10 = 59049 瓶! 这就是更高级的"三进制编码"思想。 ``` --- ## 一句话总结 把 1000 瓶酒用 10 位二进制编号,每只老鼠负责一个二进制位,喝下该位为 1 的所有酒。死亡老鼠的二进制组合直接等于毒酒编号——这是信息论中"用最少 bit 编码最多信息"的经典应用。 --- 下一篇:[04 - 赛马问题](./04-horse-racing.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入