首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  算法

出几个烧脑的智力/算法题,顺便聊聊它们背后的数学

  •  2
     
  •   mathzhaoliang · 106 天前 · 4650 次点击
    这是一个创建于 106 天前的主题,其中的信息可能已经有所发展或是发生改变。

    问题之一:有 12 枚外表一模一样的硬币,其中一枚是假币,其余都是真币。假币的重量与真币不同,但是更重还是更轻不知道。给你一个没有砝码和刻度的天平,最少称几次才能找出假币?

    问题之二:有 100 瓶药水和若干只小白鼠,其中一瓶药水是有毒的。正常的药水对小白鼠是无害的,但是有毒的药水则会杀死小白鼠。问最少需要几只小白鼠才能找出有毒的是哪一瓶?

    欢迎 v 友们讨论。

    第 1 条附言  ·  106 天前
    第二个问题原表述有歧义:有的读者理解为取一只小白鼠,让它挨个喝下去不就行了?
    现在重新表述为:规则允许每次可以将若干瓶药水搭配起来给某一只小白鼠喝下,且每只小白鼠只能被使用一次。问最少需要几只小白鼠。
    第 2 条附言  ·  106 天前
    我知道很多人做过这个题目,"称三次","二进制"。但是注意题目:"背后的数学"。如果不说清背后的数学,那么它对你来说只是一道智力题而已,它的真正价值没有被发掘。举个例子:

    如果把第二个问题改成有其中有两瓶是毒药呢?或者改成 "已知在你使用的小白鼠中,有一只小白鼠发生了变异,它对毒酒是免疫的,喝下去不会死,但是你不知道是哪一只“。
    这两种情况下分别最少需要几只小白鼠?
    第 3 条附言  ·  106 天前
    我正在写一篇文章,打算详细聊聊这些问题背后的数学,其实如果你学过纠错码的知识的话,它们是很好理解的,而且对那些推广型的问题,你也能举一反三找到解答。

    这里就显出数学在编程中的作用了。

    此外如果有写过二维码编码器的同学,里面不就是一个 RS 码吗?如果你会懂 RS 码是怎么回事的话,小小 Hamming 码岂不更是不在话下?
    第 4 条附言  ·  105 天前
    博客文章已经写完,增加了对 leetcode 上的一道类似题目的解释。请移步 https://neozhaoliang.github.io/post/coin-and-coding-theory/
    121 回复  |  直到 2018-11-08 16:51:01 +08:00
    1  2  
        101
    mathzhaoliang   105 天前
    @loryyang 是的,仓促成文,肯定很多不足。
    @MisakaTang 我想你的问题可以从几个角度回答:1。程序复杂性上。如果是 39 枚硬币呢?或者更多呢?代码量增加多少?写起来快不快?至少纠错码的角度看只要遍历一次不共线的向量就行了。2. 程序可推广性如何?如果问题难度增加,程序怎么写? 3. 我不用记忆具体步骤,理解了这个原理,随时可以写出一种正确的称法来。这算不算由技入道了呢?
        102
    ballshapesdsd   105 天前
    @mathzhaoliang #101 有一点不理解 2*2=1 是可以任意定义的吗?如果可以任意定义,那为什么 s1 可以用累加呢?还是说 s1 中的累加项只能有一个非零值?
        103
    MisakaTang   105 天前
    @mathzhaoliang 1. 程序复杂性 确实纠错码的构造更巧妙 2. 程序推广性 这得看问题的难度从哪个角度增加,如果现在给第一个问题加一个限制:每次把一个硬币放到天平上都记为使用硬币一次,给出在最少称重次数下使用硬币次数最少的解法.请给出纠错码角度的解法 3. 不用记忆具体步骤 搜索的方法也是推导出来的理解了之后也不用记忆步骤,这难道就不是由技入道了吗?
        104
    ballshapesdsd   105 天前
    @keylor #65 四分法:如果两份不相等,则再需要一次三分法就可确定假币,两次就找出假币。这时候你只确定在 6 个硬币中间,怎么一次就找出来了?又不知道假币更重还是更轻。另外你说的三分法,重量不同,也只确定了在 8 个硬币之中。还有 2 次怎么确定哪个是假币?
        105
    mathzhaoliang   105 天前
    @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   105 天前
    @mathzhaoliang #105 有意思。。
        107
    ballshapesdsd   105 天前
    @mathzhaoliang #105 leetcode 那道题答案好像有问题,猪死了就不能进行下一次实验了
        108
    mathzhaoliang   105 天前
    @ballshapesdsd 你说得对,我也在想这个事儿。
        109
    ballshapesdsd   105 天前
    @mathzhaoliang #108 想了想,死一次好像没什么问题。。唯一的问题就是这个和有限域好像没什么关系了,5=60/15+1 ( 4 个死亡时间和 1 个不死亡的可能),然后 5 的 r 次方大于 1000 就行了
        110
    keylor   105 天前
    @ballshapesdsd 也有道理哈
        111
    dhsss   105 天前 via Android
    @wohenyingyu02 …震惊了 还有这么理解的
        112
    l00t   105 天前
    @Kirscheis #69 再想了想,我之前的方案还是不对。因为最后要从有毒的里面找无毒的,和无毒里面找有毒的,难度完全不对等。
        113
    l00t   105 天前
    @mathzhaoliang 文章看完了,所以两瓶有毒怎么解?
        114
    mathzhaoliang   105 天前
    @l00t 在有限域上,按照本原元素的幂排列,加一组校验方程,这就得用程序算了。
        115
    l00t   105 天前
    @mathzhaoliang #114 能否再详细点, 你一句话里我有一半没看懂…… 本原元素是什么?幂排列是什么…… 假如 10 瓶里面有两瓶,这个有限域要怎么构建,里面几个值?可否给个例子演示下。
        116
    mathzhaoliang   105 天前
    @l00t 几句话说不清楚,需要你懂 Galois 域的知识。可以见[这本书]( http://vdisk.weibo.com/s/AcSJGKVz_Xdzf?category_id=0&parents_ref=AcSJGKVz_X6Sx,AcSJGKVz_Xe4e)的第 9 章。
        117
    Xs0ul   105 天前
    @mathzhaoliang 起手就是一个有限域,建议加一段介绍有限域上的加法和乘法
        118
    l00t   105 天前
    @mathzhaoliang #116 大致看了下,不是很能看懂。主要就是一个问题,我看到的 Galois 域里面的运算好像有用到异或?但是毒药的情况里,有毒的和有毒的在一起并不能变成无毒的。

    不说 2 瓶的事,就说一瓶吧。假设题目改成 3 瓶药里面 2 瓶是毒药,一瓶没毒的。几次能找出没毒的那瓶?
        119
    mathzhaoliang   104 天前
    @ballshapesdsd 我想明白了,这个方法没有问题,猪死了它给出的校验子就是它死时对应的实验次数。
        120
    mathzhaoliang   104 天前
    @l00t Galois 域的知识对没学过的人不好解释。你写过二维码的编码器或者解码器吗?里面的 RS 码用的就是 Galois 域。
        121
    mathzhaoliang   104 天前
    @l00t 我知道两瓶毒药的时候怎么做了,我现在可以证明至少需要 9 只老鼠,大致方案也有,今晚想想。
    1  2  
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   864 人在线   最高记录 4385   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 18ms · UTC 22:25 · PVG 06:25 · LAX 14:25 · JFK 17:25
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1