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

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

  •  2
     
  •   mathzhaoliang · 2018-11-06 09:42:02 +08:00 · 11102 次点击
    这是一个创建于 2202 天前的主题,其中的信息可能已经有所发展或是发生改变。

    问题之一:有 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 码岂不更是不在话下?
    第 4 条附言  ·  2018-11-07 11:51:02 +08:00
    博客文章已经写完,增加了对 leetcode 上的一道类似题目的解释。请移步 https://neozhaoliang.github.io/post/coin-and-coding-theory/
    121 条回复    2018-11-08 16:51:01 +08:00
    1  2  
    lookforsex
        1
    lookforsex  
       2018-11-06 09:46:19 +08:00
    问题一用二分法?
    mathzhaoliang
        2
    mathzhaoliang  
    OP
       2018-11-06 09:49:03 +08:00
    @lookforsex 什么是二分法?
    murmur
        3
    murmur  
       2018-11-06 09:50:40 +08:00
    我记得第二个题的漏洞不是小白鼠喂水会被撑死么
    Rizio
        4
    Rizio  
       2018-11-06 09:50:49 +08:00
    第二题,一只?让它一直喝到死。
    SuperNovaSonic
        5
    SuperNovaSonic  
       2018-11-06 09:52:44 +08:00
    转换成二进制去看这个问题就简单了
    mathzhaoliang
        6
    mathzhaoliang  
    OP
       2018-11-06 09:53:36 +08:00
    @Rizio 应该加上限制,喝药 24 小时以后毒药就会发作。要求 24 小时内找出毒药。
    binxin
        7
    binxin  
       2018-11-06 09:55:10 +08:00
    @lookforsex
    至少第一轮不能两等分,需要三等分。
    meefly
        8
    meefly  
       2018-11-06 09:56:46 +08:00 via Android
    第一题四次,不知道能不能更少
    binux
        9
    binux  
       2018-11-06 09:58:48 +08:00   ❤️ 1
    @mathzhaoliang #5 24 小时以后才发作,24 小时内无论如何都找不出来。。
    chwhsen
        10
    chwhsen  
       2018-11-06 09:59:48 +08:00
    一般说到背后的数学时,第一步就是把具体的数量抽象成`n`个
    feiyuanqiu
        11
    feiyuanqiu  
       2018-11-06 10:00:19 +08:00 via Android
    把 12 枚硬币按四个一组分成三组,找到重量与其他两组不一致的一组,同时能知道假币相对真币轻还是重( 2 次);将包含假币那组四个硬币按两个分成两组,找到假币那组( 1 次);比较假币组两枚硬币重量,找到假币( 1 次)。需要称 4 次
    mathzhaoliang
        12
    mathzhaoliang  
    OP
       2018-11-06 10:03:39 +08:00
    @chwhsen "一般说到背后的数学时,第一步就是把具体的数量抽象成 n 个"。有时候一上来就讨论一般的情形会把问题复杂化。很多数学定理是先对特殊情形加以证明,然后推广到一般的。

    @Rizio
    @mathzhaoliang
    @binux
    我也觉得这个原表述不好,应该直接告诉读者无歧义的规则,我觉得应该表述为 "规则允许每次可以将若干瓶药水搭配起来给某一只小白鼠喝下,且每只小白鼠只能被使用一次"。
    Myprincess
        13
    Myprincess  
       2018-11-06 10:04:59 +08:00
    我出一个:
    例子:615+X^2=2^Y 求 X 与 Y 的值
    Z+X^2=2^Y
    Z 在什么情况下本题无解.
    rabbbit
        14
    rabbbit  
       2018-11-06 10:05:21 +08:00
    第二题不考虑撑死 1 个,考虑撑死 7 个,貌似在哪看过...
    chwhsen
        15
    chwhsen  
       2018-11-06 10:05:38 +08:00
    @mathzhaoliang 的确是这样的
    dnhzm
        16
    dnhzm  
       2018-11-06 10:05:45 +08:00 via iPhone
    第一个 4 次,先分成 3 份,比较两次,得到重量有差别的那份,然后再拿基准的硬币与那份比较。
    第二个是 7 只老鼠,因为是 2 的 7 次方> 100,每个药按二进制编码,然后按位数等于 1 的投喂药。看死了几只就知道落在哪位为 1,然后就求出来了。
    很久之前看过
    zhzer
        17
    zhzer  
       2018-11-06 10:07:01 +08:00 via Android   ❤️ 1
    第一题二分,三次
    第二题二进制分桶,七次

    此贴完结
    Voichesapete
        18
    Voichesapete  
       2018-11-06 10:07:13 +08:00
    @murmur 没说剂量。如果有毒的那瓶喝一滴也会死呢 2333
    Nimrod
        19
    Nimrod  
       2018-11-06 10:07:37 +08:00 via Android
    第一个三次 之前貌似做过这个题
    第二个 DP
    stevenbipt
        20
    stevenbipt  
       2018-11-06 10:08:22 +08:00 via Android
    第一个先四个一组分三个看哪一组和另外两组有差异,然后在把有差异的一组取三个对比,如果有一个与另外两个有差异则那个是假币,如果没有差距则没有对比的那一张是假币,一共需要两次称重。
    wohenyingyu02
        21
    wohenyingyu02  
       2018-11-06 10:12:28 +08:00 via iPhone
    1. 最少称 2 次。首先拿两个比较,正好有一个是假币,再随便拿一个和其他比,就是最少的情况。
    2. 一只。
    mathzhaoliang
        22
    mathzhaoliang  
    OP
       2018-11-06 10:14:58 +08:00
    @zhzer 你说的大体意思我懂,但是不是我要的解答。
    Exin
        23
    Exin  
       2018-11-06 10:16:12 +08:00
    第一题的最佳解是 三次 ,不是四次。有比二分法更好的解法。
    第二题大家都会。
    Exin
        24
    Exin  
       2018-11-06 10:16:53 +08:00
    @zhzer 二分如何解出三次的?
    murmur
        25
    murmur  
       2018-11-06 10:18:58 +08:00   ❤️ 1
    第一个题不是一次都不需要么
    既然假币和真币的差别只有重量区别 而且是只有天平才能发现的问题
    那就是说把这 12 个硬币都花掉不就解决了
    denano
        26
    denano  
       2018-11-06 10:21:29 +08:00
    第一题一开始 3 等分找出重量不一致的那一堆再 2 等分,4 次
    第二题就是一开始把 50 瓶药混在一起喂,就是 2 分查找。。
    LadyChunsKite
        27
    LadyChunsKite  
       2018-11-06 10:21:45 +08:00
    dingyaguang117
        28
    dingyaguang117  
       2018-11-06 10:28:36 +08:00
    第一题是 google 埃里克·施密特 面试别人的题,最多 3 次,过程比较复杂
    yukiww233
        29
    yukiww233  
       2018-11-06 10:29:22 +08:00
    2.每瓶药水等分并编号 1-100,用二进制表示占 7 位,7 只老鼠喝对应二进制位为 1 的的药水,死了该位为 1,拼起来就完事
    yukiww233
        30
    yukiww233  
       2018-11-06 10:34:02 +08:00
    1 在面试时候被问过,半天没答上来
    mathzhaoliang
        31
    mathzhaoliang  
    OP
       2018-11-06 10:47:07 +08:00
    @SuperNovaSonic
    @yukiww233
    @Exin
    @zhzer

    如果是其中两瓶有毒呢?
    ch365
        32
    ch365  
       2018-11-06 10:49:36 +08:00   ❤️ 3
    只要找到假币的话总共称三次,如果还要知道假币轻还是重则要称四次
    首先分成三组每组四个,第一次称其中两组。
    如果,第一次两组一样重,假币则在第三组的四个中;
    这种情况下,第三组的四个中,天平两边各放一个,一样重假币在没称的两个中,不一样重假币在天平上的两个中;
    第三次拿一个真币和一个未知币称可以找到假币。
    如果,第一次两组不一样重,假设轻的那组标为 0,重的那组标为 1,剩下的真币组标为 2 ;
    第二次,天平左右这样放: 001 vs 012 ;
    如果一样重,假币在组 0 和组 1 中没放上天平的三个硬币中;
    第三次拿组 1 中剩下的两个放上天平;如果一样重,假币是租 0 中剩下的那个,否则假币就是重的那个
    如果第二次称,001 的一边较重;那么假币在 001 的 1 或者 012 的 0 之中;两个币第三次称下确定假币。
    如果第二次称,012 的一边较重;那么假币在 001 的两个 0 或者 012 的 1 之中;三个币第三次可以确定假币
    mathzhaoliang
        33
    mathzhaoliang  
    OP
       2018-11-06 10:53:53 +08:00
    @ch365 如果知道背后的数学的话,就可以设计出正确的方案来。并不很难,三次就知道轻重。光靠自己试的话累死不说还找不到正确的方案。
    SuperNovaSonic
        34
    SuperNovaSonic  
       2018-11-06 10:56:33 +08:00
    @denano 第一题是求最好情况,如果一开始三堆上称的那两堆重量一致,直接确认假币在剩下一堆里,所以一共三次就好了,4 次是最差情况下的
    binux
        35
    binux  
       2018-11-06 10:57:13 +08:00
    @mathzhaoliang #29 13 只
    ch365
        36
    ch365  
       2018-11-06 10:59:07 +08:00
    @mathzhaoliang 恩,三次就可以知道轻重,假币则在第三组的四个中的情况,后面称重设计有误。
    A3m0n
        37
    A3m0n  
       2018-11-06 11:03:55 +08:00
    我也来补两个,第一题是小白鼠的简单版本:

    有一批玻璃杯(产品的优劣程度完全相同),和一幢高 100 层的楼( 1 层到 100 层,不存在 0 层)。现在要测试这批玻璃杯的耐摔程度,即玻璃杯如果在 n 层下落没碎,在 n+1 层下落碎了,那耐摔程度就是 n。请问:

    1:最少牺牲多少个玻璃杯?
    2:最少测试几次?
    (两个问题相互独立)

    还有一题题目比较恶俗,但是解起来还是比较有趣的。我想想有什么不怎么恶俗的表达方式,如果想不到的话,待会上题目。
    MisakaTang
        38
    MisakaTang  
       2018-11-06 11:28:49 +08:00
    数学之美番外篇:快排为什么那样快 : http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/
    这篇博客我感觉是讲到了背后的数学原理了 可以看一下
    loryyang
        39
    loryyang  
       2018-11-06 11:33:16 +08:00
    第一题答案是三次,https://gist.github.com/zjucloud/eee320c016e670ddfef111c386ad9b26
    直接写的,不确定一定正确:
    1:平均分三组,A B C
    A vs B
    A < B or A > B 看 2.1, A == B 看 2.2

    2.1
    说明在 A,B 里面,由于 A 和 B 相对等价,我们可以假设 A < B (反过来就把 AB 互换即可):这样只可能是 A 有一个硬币轻,或者 B 有一个硬币重
    A 和 B 都分成 2+1+1,表示为 A1,A3,A4 和 B1,B3,B4
    我们从 C 里面取正常的硬币 X,然后 A3 + B1 VS A4 + B4 + X,把 A1 和 B3 留下
    三种情况:
    <:2.1.3
    >:2.1.4
    =:2.1.5

    2.1.3
    A3 + B1 < A4 + B4 + X
    说明 A3, B4 有问题,因为之前是 A < B,所以要不是 A 的只可能轻,B 的只可能重, B1, A4 如果有问题,应该是>而不是<
    A3 和 B4 都是一个,所以用 3.1.2 解法即可

    2.1.4
    A3 + B1 > A4 + B4 + X
    反转了,说明 B1,A4 可能有问题,B1 是两个,A4 是一个
    我们把 B1 拆成 B11 和 B12,然后 B11 + A4 VS X + X:
    <:说明 res = A4
    >:res=B11
    ==:res=B12

    2.1.5
    A3 + B1 == A4 + B4 + X
    说明剩下的 A1 和 B3 有问题,和 2.4 类似,拆分 A1 为 A11, A12
    然后 A11 + B3 VS X + X
    <: res=A11
    >: res=B3
    ==: res=A12

    3.1
    说明 C 有问题
    C 分为 2 + 2:M, N
    M 再分 M1, M2,然后 M1 VS M2
    如果 M1 != M2 看 3.1.2,否则看 3.1.3

    3.1.2 M1 != M2 说明 M1, M2 有一个有问题
    取一个正常的 X vs M1,如果不平衡,res=M1 否则 res=M2

    3.1.3
    说明 N 里面有问题,和 2.3 一样,取一个正常的 X vs N1,如果不平衡,说明 res=N1,否则 res=N2
    mathzhaoliang
        40
    mathzhaoliang  
    OP
       2018-11-06 11:35:35 +08:00
    @MisakaTang 那些写数学之美的人 (包括吴军),都不是数学科班出身的,所以遇到一个好玩的题目和一个好玩一点的解释就大惊小怪一番。其实那篇文章也没写到点子上。
    loryyang
        41
    loryyang  
       2018-11-06 11:58:50 +08:00   ❤️ 6
    说实话我很难理解 lz 发这个帖子为了什么,如果你想分享,那么就直接把背后的数学知识贴出来,没必要卖关子。知识这东西,都是建立在前人的基础上的,没看过的人,你要让他从低基础开始直接赶上前人那么多年的积累,那根本不可能。而如果想引导别人思考一遍,你给出原理,大家学习一下也就都受益了
    如果你只是想看看大家对你已掌握的知识如何的无知,给自己增加点快感,那就当我没说
    jkeylu
        42
    jkeylu  
       2018-11-06 12:41:32 +08:00
    楼主题目用词不严谨,不是“最少”而是“至多”
    ballshapesdsd
        43
    ballshapesdsd  
       2018-11-06 12:43:36 +08:00
    @mathzhaoliang #40 大佬可以公布答案了,这都发帖三个小时了
    mathzhaoliang
        44
    mathzhaoliang  
    OP
       2018-11-06 13:01:07 +08:00
    @ballshapesdsd 正在写 ing,说清楚的话比较长,所以麻烦等一会。

    @loryyang
    ”如果你想分享,那么就直接把背后的数学知识贴出来“。就是想分享,很快就会贴的,只是我还没看到那个中文网页上有现成的,所以正在写 ing。
    jaleo
        45
    jaleo  
       2018-11-06 13:01:30 +08:00
    只要求答案的话 第一题是小学五年级数学题 最少 3 次 至少 4 次 大纲里要求掌握的
    mathzhaoliang
        46
    mathzhaoliang  
    OP
       2018-11-06 13:02:10 +08:00
    @jaleo 现在小学生都这么厉害了?我有点担心我家娃将来跟不上啊 ..
    iceheart
        47
    iceheart  
       2018-11-06 13:07:58 +08:00 via Android
    第一题有通解,大概 01 年或者 02 年在水木清华上看到过,有个叫袁哥的用信息论分析,给出的解法。
    zjxlim
        48
    zjxlim  
       2018-11-06 13:36:23 +08:00
    第一题可以看成二叉树叶结点的最大深度,有不同的构造方法,(最少 2 次最多 5 次的和最少 3 次最多 4 次的)
    第二题同理有不同构造方法
    mathzhaoliang
        49
    mathzhaoliang  
    OP
       2018-11-06 14:18:46 +08:00
    我先大致说一下吧。这两个题都有一个共同点 "恰好有一个 xxx 和其它不同",也就是说,在一个码子中有一个位置发生了错误,要纠正这个错误。

    这就是纠错码理论可以应用的地方,而且纠正一个错误的当然就是 Hamming 码 ~。
    maswang
        50
    maswang  
       2018-11-06 14:28:28 +08:00
    题 1 想到还有一个方法:
    分成 4 组,每组 3 个。
    第一次称其中 2 组。
    如果一样重,则假币在另外两组中
    如果不一样重,假币正在在称的两组中
    即第一次称之后确定 1/6

    第二次:
    在确定假币的 6 个中,分成 3 组,每组 2 个
    称其中两组:
    如果一样重,则假币在剩下的 1/2 中
    如果不一样重,则假币在 1/4 中

    如果第二次一样重,1/2 确定假币,只需要再称 1 次了,拿 10 个正常币中的 1 个来比较一下就行了,即 3 次确定假币
    如果第二次不一样重,因为最后 4 个已经 2 个 2 个称过一次了,所以也有 50%概率一次确定到假币,具体就不详细说了
    loryyang
        51
    loryyang  
       2018-11-06 14:38:37 +08:00
    @mathzhaoliang 期待大作,真的,你完全可以写完再发这个帖子,一样很多人来看的
    talen666
        52
    talen666  
       2018-11-06 14:59:39 +08:00
    “最少”称几次才能找出假币,最少 emmm
    swordmaster
        53
    swordmaster  
       2018-11-06 15:26:01 +08:00
    第二题李永乐讲二进制的时候用过这个例子
    MisakaTian
        54
    MisakaTian  
       2018-11-06 16:08:29 +08:00
    请把烧脑两个字去掉?
    mario85
        55
    mario85  
       2018-11-06 16:15:09 +08:00 via iPhone
    第一题我居然想歪到分解质因数上去了,最多 4 次,不知道能不能更少。
    前面楼的 3 次好像都是剩两枚算最后一次,个人觉得只有两枚硬币的情况下无法知道哪个是假,只剩两枚的情况下还需要用已知的真币再测一次
    sun1719
        56
    sun1719  
       2018-11-06 16:17:16 +08:00 via Android
    问题一: 之前思考过,也看过些文章。
    具体数学考虑是用信息熵的理论(香农);
    结论: n 个硬币(不知道假币是轻还是重),至多需要次数 log3(2n)确定真假。
    mathzhaoliang
        57
    mathzhaoliang  
    OP
       2018-11-06 16:19:35 +08:00
    @sun1719 不是的,信息论只能给出一个直观的解释,并不是严格的论证。用到的是纠错码的理论。
    ballshapesdsd
        58
    ballshapesdsd  
       2018-11-06 16:25:54 +08:00
    @mathzhaoliang #57 大哥,我等了一下午了
    jin5354
        59
    jin5354  
       2018-11-06 16:26:11 +08:00
    你一个数学科班的人,来满是工业界程序员的论坛问题解,我们用标准 leetcode 刷题解题思路给你回,你表示 nonono 都不是我要的,这不是鸡同鸭谈
    murmur
        60
    murmur  
       2018-11-06 16:26:59 +08:00
    @A3m0n 杯子没碎但是出现裂纹怎么办?
    jin5354
        61
    jin5354  
       2018-11-06 16:27:07 +08:00
    思维方式都不一样,你就直接分享呗,虽然我预料对于绝大多数码农都是屠龙术了。。
    wayne1027
        62
    wayne1027  
       2018-11-06 16:28:50 +08:00
    最少的话。。。不就是纯看脸了吗。
    1.随机取一枚 A,与另一枚 B 对比,一样重,则两枚都是真币;
    2.取一枚真币 A 或 B,另随机取一枚 C,这时候不一样重了,则刚好 C 就是假币。
    所以,运气爆炸的话,最少只用两次……轻喷…

    楼上的三分法,就是完全不看运气了。
    Wincer
        63
    Wincer  
       2018-11-06 16:32:40 +08:00 via Android
    第二题是 7 只,2 的 7 次幂大于 100
    summerluqman
        64
    summerluqman  
       2018-11-06 16:37:28 +08:00 via iPhone
    等待李老师视频
    keylor
        65
    keylor  
       2018-11-06 16:50:18 +08:00
    第一题有比三分法更优的解--四分法。下面论证。
    三分法:也就是分成 3 等分,第一次分成 4,4,4,取两份称重,根据重量相等还是不同来确定假币所在的堆,最终要称三次。
    优化的四分法:分成:3,3,3, 3 四份。称重两份,那么,如果两份不相等,则再需要一次三分法就可确定假币,两次就找出假币。如果相等,则称重剩余两份,再三分法,需要三次。
    总结:优化的四分法有二分之一的概率只要两次即可确定假币,二分之一概率三次确定假币。期望值是 2.5 次。

    还有谁能给出比我次数期望更低的解不?
    Rizio
        66
    Rizio  
       2018-11-06 16:51:09 +08:00
    @wayne1027 其实看脸的话一次就行了,直接拿一枚说这是假的,比真的轻 /重,蒙对了就行 doge。
    keylor
        67
    keylor  
       2018-11-06 16:51:11 +08:00
    @loryyang 看我四分法
    keylor
        68
    keylor  
       2018-11-06 16:52:10 +08:00
    @Exin 有比三分法更好的
    Kirscheis
        69
    Kirscheis  
       2018-11-06 16:56:59 +08:00   ❤️ 1
    你的问题太简单了,谈不上烧脑,给大家来个难的

    有 1000 瓶药水和若干只小白鼠,其中 2 瓶药水是有毒的。正常的药水对小白鼠是无害的,但是有毒的药水则会杀死小白鼠。问最少需要几只小白鼠才能找出有毒的是哪一瓶?允许每次可以将若干瓶药水搭配起来给某一只小白鼠喝下,且每只小白鼠只能被使用一次

    我可以给一个信息论的估计,总信息熵是 S = lg C_{1000}^2 = lg 495000,每用一只白鼠,最少可以得到的信息是白鼠死了或者白鼠活着,则得到的信息熵至少为 S = lg 2,故可以估计出最多需要的数量是 ceil( lg 495000 / lg 2 ) = ceil( 18.9 ) = 19。

    请只用 19 只白鼠给出一个构造性的办法
    mathzhaoliang
        70
    mathzhaoliang  
    OP
       2018-11-06 17:08:44 +08:00
    @keylor
    @Rizio

    题目是要求一定能确保找出假币最少需要称几次
    hundan
        71
    hundan  
       2018-11-06 17:51:41 +08:00 via Android
    第一题的问题 就是问在最差情况下的最优解 同学们不要抠字眼拿运气说事啊
    SNOOPY963
        72
    SNOOPY963  
       2018-11-06 18:44:13 +08:00
    各位,这个上限是用信息论解决的,至于怎么构造是剩下的事情。第一题很小时候就接触过,今年才突然醒明白这是信息量处理的问题。再一看信息论早已有定论了。
    Exin
        73
    Exin  
       2018-11-06 18:49:52 +08:00 via iPhone
    @keylor 要不你再想想...
    SNOOPY963
        74
    SNOOPY963  
       2018-11-06 18:51:38 +08:00
    有 12 个硬币,只有一个重量不同(轻重未知),利用一个无刻度天平,通过 3 次平衡,找出那枚硬币。求解法? - Jun LI 的回答 - 知乎
    https://www.zhihu.com/question/21677131/answer/323179768

    人家已经有回答了,我就不多说了。
    frienmo
        75
    frienmo  
       2018-11-06 20:40:16 +08:00
    第一题背后的数学是信息熵,学熵的时候做题都证明过。
    mathzhaoliang
        76
    mathzhaoliang  
    OP
       2018-11-06 21:19:14 +08:00
    @SNOOPY963 不不不,他的表述漏洞太多,似搭不搭边。
    murmur
        77
    murmur  
       2018-11-06 22:29:40 +08:00
    @Kirscheis 让小白鼠互相繁殖可以么
    linKnowEasy
        78
    linKnowEasy  
       2018-11-06 23:24:27 +08:00
    对楼主即将完成的文章很感兴趣.
    有博客啥的么?
    mathzhaoliang
        79
    mathzhaoliang  
    OP
       2018-11-06 23:25:24 +08:00
    Xs0ul
        80
    Xs0ul  
       2018-11-07 00:04:18 +08:00
    @mathzhaoliang #78 现在更新了吗?目录只能看到一个旧的 “称硬币问题与编码理论”
    aheadlead
        81
    aheadlead  
       2018-11-07 00:18:14 +08:00
    @mathzhaoliang 膜拜大佬
    l00t
        82
    l00t  
       2018-11-07 08:49:00 +08:00
    @Kirscheis #69 给瓶子编号,然后取 998 瓶混合成一瓶,这样混出 C(1000,998) 瓶,其中一瓶是恰好排除了有毒那两瓶的最终混合物无毒的。然后就回到 C(1000,998)瓶中找一瓶无毒的问题了。
    mathzhaoliang
        83
    mathzhaoliang  
    OP
       2018-11-07 09:11:06 +08:00
    @Xs0ul
    @aheadlead

    已经更新啦,地址在 https://neozhaoliang.github.io/post/coin-and-coding-theory/

    欢迎提出批评和改进意见~~
    mathzhaoliang
        84
    mathzhaoliang  
    OP
       2018-11-07 09:14:35 +08:00
    @SNOOPY963
    @aheadlead
    @Xs0ul
    @linKnowEasy
    @frienmo

    目前只完成了第一题的部分,第二题还在写作中。见 83 楼链接。
    lueffy
        85
    lueffy  
       2018-11-07 09:26:50 +08:00
    @loryyang 也不一定啊 因为如果说这个帖子 楼主直接把答案放出来,我肯定不会细看的;相反,如果只给了问题,没有答案,你才会
    lueffy
        86
    lueffy  
       2018-11-07 09:27:23 +08:00
    @loryyang 也不一定啊 因为如果说这个帖子 楼主直接把答案放出来,我肯定不会细看的;相反,如果只给了问题,没有答案,你才会有兴趣去思考一下
    mathzhaoliang
        88
    mathzhaoliang  
    OP
       2018-11-07 09:46:07 +08:00
    @linhua 第一个链接里的文章最接近我的叙述,不过我觉得没有我的写的好~
    第二个链接表示看不懂。
    ballshapesdsd
        89
    ballshapesdsd  
       2018-11-07 09:53:13 +08:00
    @mathzhaoliang #88 大佬,012 和 021 为啥共线啊?看不懂
    linhua
        90
    linhua  
       2018-11-07 09:54:02 +08:00
    @mathzhaoliang
    https://en.wikipedia.org/wiki/Balance_puzzle
    “ Note that with 3 weighs and 13 coins, it is not always possible to determine the identity of the last coin (whether it is heavier or lighter than the rest), but merely that the coin is different. ”
    mathzhaoliang
        91
    mathzhaoliang  
    OP
       2018-11-07 09:55:10 +08:00
    @ballshapesdsd 在有限域 F_3 里面,运算都是模 3 意义下的,1x2=2, 2x2=1。向量 (0, 1, 2) 乘以 2 以后是 (0, 2, 1),它俩只差一个倍数,当然共线啊。
    mathzhaoliang
        92
    mathzhaoliang  
    OP
       2018-11-07 09:58:50 +08:00
    @linhua 这个我在文章中写了原因了。13 枚硬币里面任取 12 枚,在这 12 枚里面要么找出假币且确定出轻重,要么什么也找不到,当然剩下的那个是假币 (但不知道轻重)。
    ballshapesdsd
        93
    ballshapesdsd  
       2018-11-07 10:03:17 +08:00
    @mathzhaoliang #91 学到了
    KellenChou
        94
    KellenChou  
       2018-11-07 10:08:25 +08:00
    @mathzhaoliang 文章中 “如果天平是平衡的,由于两边硬币数目相同,那么两边一定都是真币,假币不出现,即 xi=0,从而 s1=0。”
    应该是 yi=0 吧。
    mathzhaoliang
        95
    mathzhaoliang  
    OP
       2018-11-07 10:09:28 +08:00
    @KellenChou 是的,笔误了。
    mathzhaoliang
        96
    mathzhaoliang  
    OP
       2018-11-07 10:47:59 +08:00
    @KellenChou
    @ballshapesdsd
    第二个问题也写完啦。
    mathzhaoliang
        97
    mathzhaoliang  
    OP
       2018-11-07 11:49:45 +08:00
    @LadyChunsKite 已经增加了对这个问题的解释。
    loryyang
        98
    loryyang  
       2018-11-07 11:57:17 +08:00
    @lueffy 这个就和做 leetcode 一样啊,你知道你可以去评论区看到各种解法,你提交之后可以看到错误的 test case。但是你依然会选择先自己解决问题

    我并不觉得楼主把答案扔出来就会妨碍你去探索问题了
    MisakaTang
        99
    MisakaTang  
       2018-11-07 12:34:27 +08:00
    看完了楼主的博客个人感觉用纠错码和三分来解这个问题只是两种不同的方法而已,三分的方法是把问题转换到了程序员熟悉的搜索领域然后用三分来解决,楼主的解法是把问题转换到了数学工具上然后来解决,我感觉这也只是解决一个问题数学和计算机思维的两种不同的表现而已,至于说搜索的解法没有接触到问题的本质这一点我想问本质是什么,楼主的解法我也可以看成是纠错码这个工具正好能套中这类问题罢了
    loryyang
        100
    loryyang  
       2018-11-07 12:34:37 +08:00
    看了文章,写的很清楚,不过感觉对纠错码的基础可以再展开多说点
    1  2  
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2726 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 10:11 · PVG 18:11 · LAX 02:11 · JFK 05:11
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.