这是一个创建于 2211 天前的主题，其中的信息可能已经有所发展或是发生改变。
问题之一：有 12 枚外表一模一样的硬币，其中一枚是假币，其余都是真币。假币的重量与真币不同，但是更重还是更轻不知道。给你一个没有砝码和刻度的天平，最少称几次才能找出假币?
问题之二：有 100 瓶药水和若干只小白鼠，其中一瓶药水是有毒的。正常的药水对小白鼠是无害的，但是有毒的药水则会杀死小白鼠。问最少需要几只小白鼠才能找出有毒的是哪一瓶？
欢迎 v 友们讨论。
第 1 条附言 · 2018-11-06 10:18:05 +08:00
第二个问题原表述有歧义：有的读者理解为取一只小白鼠，让它挨个喝下去不就行了？
现在重新表述为：规则允许每次可以将若干瓶药水搭配起来给某一只小白鼠喝下，且每只小白鼠只能被使用一次。问最少需要几只小白鼠。
现在重新表述为：规则允许每次可以将若干瓶药水搭配起来给某一只小白鼠喝下，且每只小白鼠只能被使用一次。问最少需要几只小白鼠。
第 2 条附言 · 2018-11-06 10:27:51 +08:00
我知道很多人做过这个题目，"称三次"，"二进制"。但是注意题目："背后的数学"。如果不说清背后的数学，那么它对你来说只是一道智力题而已，它的真正价值没有被发掘。举个例子：
如果把第二个问题改成有其中有两瓶是毒药呢？或者改成 "已知在你使用的小白鼠中，有一只小白鼠发生了变异，它对毒酒是免疫的，喝下去不会死，但是你不知道是哪一只“。
这两种情况下分别最少需要几只小白鼠？
如果把第二个问题改成有其中有两瓶是毒药呢？或者改成 "已知在你使用的小白鼠中，有一只小白鼠发生了变异，它对毒酒是免疫的，喝下去不会死，但是你不知道是哪一只“。
这两种情况下分别最少需要几只小白鼠？
第 3 条附言 · 2018-11-06 11:44:41 +08:00
我正在写一篇文章，打算详细聊聊这些问题背后的数学，其实如果你学过纠错码的知识的话，它们是很好理解的，而且对那些推广型的问题，你也能举一反三找到解答。
这里就显出数学在编程中的作用了。
此外如果有写过二维码编码器的同学，里面不就是一个 RS 码吗？如果你会懂 RS 码是怎么回事的话，小小 Hamming 码岂不更是不在话下？
这里就显出数学在编程中的作用了。
此外如果有写过二维码编码器的同学，里面不就是一个 RS 码吗？如果你会懂 RS 码是怎么回事的话，小小 Hamming 码岂不更是不在话下？
第 4 条附言 · 2018-11-07 11:51:02 +08:00
博客文章已经写完，增加了对 leetcode 上的一道类似题目的解释。请移步 https://neozhaoliang.github.io/post/coin-and-coding-theory/
 |
101
mathzhaoliang OP @loryyang 是的，仓促成文，肯定很多不足。
@MisakaTang 我想你的问题可以从几个角度回答：1。程序复杂性上。如果是 39 枚硬币呢？或者更多呢？代码量增加多少？写起来快不快？至少纠错码的角度看只要遍历一次不共线的向量就行了。2. 程序可推广性如何？如果问题难度增加，程序怎么写？ 3. 我不用记忆具体步骤，理解了这个原理，随时可以写出一种正确的称法来。这算不算由技入道了呢？ |
 |
102
ballshapesdsd 2018-11-07 13:31:34 +08:00
@mathzhaoliang #101 有一点不理解 2*2=1 是可以任意定义的吗？如果可以任意定义，那为什么 s1 可以用累加呢？还是说 s1 中的累加项只能有一个非零值？
|
 |
103
MisakaTang 2018-11-07 13:35:00 +08:00
@mathzhaoliang 1. 程序复杂性 确实纠错码的构造更巧妙 2. 程序推广性 这得看问题的难度从哪个角度增加,如果现在给第一个问题加一个限制:每次把一个硬币放到天平上都记为使用硬币一次,给出在最少称重次数下使用硬币次数最少的解法.请给出纠错码角度的解法 3. 不用记忆具体步骤 搜索的方法也是推导出来的理解了之后也不用记忆步骤,这难道就不是由技入道了吗?
|
|
104
ballshapesdsd 2018-11-07 13:44:07 +08:00
@keylor #65 四分法：如果两份不相等，则再需要一次三分法就可确定假币，两次就找出假币。这时候你只确定在 6 个硬币中间，怎么一次就找出来了？又不知道假币更重还是更轻。另外你说的三分法，重量不同，也只确定了在 8 个硬币之中。还有 2 次怎么确定哪个是假币？
|
|
105
mathzhaoliang OP @ballshapesdsd 不是任意定义的，必须满足域的公理。域算法里面有加法和乘法，每个非零元都有 "倒数"，且乘法满足结合律 a(bc) = (ab)c，加法乘法满足交换律 a(b+c) = ab + ac 等等。
如果定义 2x2 = 2, 则 2 = 2 x( 1 + 1) = 2 + 2 = 1 矛盾。若定义 2x2 = 0 则 2 没有倒数。若不然 2 x m = m x 2 = 1，则 2 x 2 x m = 2 x 1 = 2, 即 0 = 2，矛盾。 模一个素数 p 得到的剩余类满足域的公理，这个叫做有限域。密码学和纠错码理论就是建立在有限域上的。 |
|
106
ballshapesdsd 2018-11-07 13:51:38 +08:00
@mathzhaoliang #105 有意思。。
|
|
107
ballshapesdsd 2018-11-07 16:15:43 +08:00
@mathzhaoliang #105 leetcode 那道题答案好像有问题，猪死了就不能进行下一次实验了
|
|
108
mathzhaoliang OP @ballshapesdsd 你说得对，我也在想这个事儿。
|
|
109
ballshapesdsd 2018-11-07 16:38:56 +08:00
@mathzhaoliang #108 想了想，死一次好像没什么问题。。唯一的问题就是这个和有限域好像没什么关系了，5=60/15+1 （ 4 个死亡时间和 1 个不死亡的可能），然后 5 的 r 次方大于 1000 就行了
 |
 |
110
keylor 2018-11-07 17:03:21 +08:00
@ballshapesdsd 也有道理哈
|
 |
111
dhsss 2018-11-07 17:04:02 +08:00 via Android
@wohenyingyu02 …震惊了 还有这么理解的
|
 |
112
l00t 2018-11-07 20:58:01 +08:00
@Kirscheis #69 再想了想，我之前的方案还是不对。因为最后要从有毒的里面找无毒的，和无毒里面找有毒的，难度完全不对等。
|
|
113
l00t 2018-11-07 21:30:02 +08:00
@mathzhaoliang 文章看完了，所以两瓶有毒怎么解？
|
|
114
mathzhaoliang OP @l00t 在有限域上，按照本原元素的幂排列，加一组校验方程，这就得用程序算了。
|
|
115
l00t 2018-11-07 21:45:21 +08:00
@mathzhaoliang #114 能否再详细点， 你一句话里我有一半没看懂…… 本原元素是什么？幂排列是什么…… 假如 10 瓶里面有两瓶，这个有限域要怎么构建，里面几个值？可否给个例子演示下。
|
|
116
mathzhaoliang OP @l00t 几句话说不清楚，需要你懂 Galois 域的知识。可以见[这本书]( http://vdisk.weibo.com/s/AcSJGKVz_Xdzf?category_id=0&parents_ref=AcSJGKVz_X6Sx,AcSJGKVz_Xe4e)的第 9 章。
|
 |
117
Xs0ul 2018-11-07 22:32:24 +08:00
@mathzhaoliang 起手就是一个有限域，建议加一段介绍有限域上的加法和乘法
|
|
118
l00t 2018-11-07 23:26:29 +08:00
@mathzhaoliang #116 大致看了下，不是很能看懂。主要就是一个问题，我看到的 Galois 域里面的运算好像有用到异或？但是毒药的情况里，有毒的和有毒的在一起并不能变成无毒的。
不说 2 瓶的事，就说一瓶吧。假设题目改成 3 瓶药里面 2 瓶是毒药，一瓶没毒的。几次能找出没毒的那瓶？ |
|
119
mathzhaoliang OP @ballshapesdsd 我想明白了，这个方法没有问题，猪死了它给出的校验子就是它死时对应的实验次数。
|
|
120
mathzhaoliang OP @l00t Galois 域的知识对没学过的人不好解释。你写过二维码的编码器或者解码器吗？里面的 RS 码用的就是 Galois 域。
|
|
121
mathzhaoliang OP @l00t 我知道两瓶毒药的时候怎么做了，我现在可以证明至少需要 9 只老鼠，大致方案也有，今晚想想。
|
Select Language