V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Yokin
V2EX  ›  职场话题

一道笔试题求答案

  •  
  •   Yokin · 2021-02-01 21:52:53 +08:00 · 4684 次点击
    这是一个创建于 1375 天前的主题,其中的信息可能已经有所发展或是发生改变。
    昨天的一道面试题,想了好久都没有答案,听说 V2EX 大佬多
    大佬勿喷,初级开发,能力有限,没想到合适答案。
    8 个外表一样的小球,其中 7 个球重量相同,1 个球为[异常球],可能重量更轻也可能更重,利用天平称重至少多少次可以确保找出这个[异常球],并且知道到底是轻了还是重了。
    (1)请先说明思路。
    (2)使用 js 实现此思路。
    (3)如何从性能的角度优化第(2)步的 js 代码?
    62 条回复    2021-02-02 20:47:02 +08:00
    JerryY
        1
    JerryY  
       2021-02-01 21:56:59 +08:00
    看过类似的题目,好像是位运算符做的? 2^3 = 8 ?如果不对,证明我记错了。
    Jooooooooo
        2
    Jooooooooo  
       2021-02-01 21:57:54 +08:00
    称球的题目本身一搜都是答案

    n 个球称几次能找出异常重量的球是有公式的
    LadyChunsKite
        3
    LadyChunsKite  
       2021-02-01 22:04:14 +08:00
    称球的题目我记得好像是三等分来做。
    但是你这个重量更轻也可能更重好像把问题复杂化了。
    lance6716
        4
    lance6716  
       2021-02-01 22:11:36 +08:00 via Android
    概率空间{1 轻、1 重、2 轻、2 重…}共 16 种,理想情况下每次操作砍一半,所以最少要操作 4 次

    具体咋操作,就慢慢想吧
    yeqizhang
        5
    yeqizhang  
       2021-02-01 22:15:13 +08:00 via Android
    先各放 3,
    如果在这 6 个球里,再各放 2,
    如果在这 4 个球里,再各放 1,可以找到剩下的最后的 2 个中有一个异常球,
    两球中再拿一球和六正常球中的一个对比就可以知道了。
    最坏的情况 4 次,最快是 3 次。

    暂时没抽象出公式出来……
    Caballarii
        6
    Caballarii  
       2021-02-01 22:24:01 +08:00
    @yeqizhang 最快不在这 6 个球里,两次
    yeqizhang
        7
    yeqizhang  
       2021-02-01 22:24:38 +08:00 via Android
    上面漏了最坏的一次,应该是 5 次了。
    比二等分还复杂,二等分称好像也是这个结果……是我想复杂了……
    yeqizhang
        8
    yeqizhang  
       2021-02-01 22:29:56 +08:00 via Android
    @Caballarii 不知道轻重,所以还得称两次。其实理想情况下,一次各放 1 个,运气好是两次能找到轻重的那个。不过题目是确保找出来咯……
    lemon6
        9
    lemon6  
       2021-02-02 00:22:26 +08:00   ❤️ 1
    3 次啊,2 分法!!
    lxy42
        10
    lxy42  
       2021-02-02 00:28:34 +08:00
    有 v 友发过一篇文章解释这个问题: https://www.v2ex.com/t/504875?p=1
    bushenx
        11
    bushenx  
       2021-02-02 01:10:35 +08:00 via Android
    二分,最好 3 最坏 4 吧
    szxczyc
        12
    szxczyc  
       2021-02-02 02:35:19 +08:00 via iPhone
    最快不是两次嘛,332,两两测。最少两次。
    hawhaw
        13
    hawhaw  
       2021-02-02 06:37:33 +08:00 via Android
    三次
    kunkunzhang
        14
    kunkunzhang  
       2021-02-02 08:50:42 +08:00
    三次,2 的 3 次为 8,建议搜索同款题,关键词:8 只小鼠 毒药
    k3Sv1
        15
    k3Sv1  
       2021-02-02 08:55:35 +08:00 via iPhone
    只要两次。因为天平结果有三种。3^2=9 。
    IvanLi127
        16
    IvanLi127  
       2021-02-02 09:04:12 +08:00 via Android
    三个和三个比,如果等重,那么剩下两个比,得出结论;否则轻的那三个中拿两个比。如果等重,剩下的一个轻;否则答案也出来了。
    Biwood
        17
    Biwood  
       2021-02-02 09:04:42 +08:00 via Android
    单纯用二分法也不行,因为不知道异常球的轻重,第一次二分的时候你取哪边?
    Biwood
        18
    Biwood  
       2021-02-02 09:09:13 +08:00 via Android
    二分法还不如枚举法,至少能达到目的,最坏 n 的平方,在此基础上再优化
    JKeita
        19
    JKeita  
       2021-02-02 09:15:13 +08:00
    3 次
    1 。两个与两个比较,相同说明在另外 4 个里,反之这在当前比较的 4 个里。
    2 。拿出未比较的两个球,与上一步比较过的一组进行比较,相同说明在另一组(这一步就能看出到底是大还是小)
    3 。同上再拿一颗球与上一步中其中一颗球比较,相同则说明另一颗为异。
    DonaldY
        20
    DonaldY  
       2021-02-02 09:24:52 +08:00
    两次
    stukiller
        21
    stukiller  
       2021-02-02 10:02:37 +08:00
    第一秤:拿出 4 个球 2:2 秤,得出正常组 AAAA 异常组 BBBB
    第二秤:分四组 AAA BBB A1 B1
    情况 1 AAA=BBB 第三秤:正常 A1 和异常 B1
    情况 2 AAA > BBB 或 AAA < BBB BBB 异常组,且得知异常球轻还是重。 第三秤:再 BBB 拿 2 个称下就好
    toan
        22
    toan  
       2021-02-02 10:13:00 +08:00
    还要弄清楚异常的那个是重了还是轻了,所以楼上各位回答的好像都不准确。
    huang119412
        23
    huang119412  
       2021-02-02 10:16:00 +08:00
    @Biwood 大致框架是这,但是每题都有变动,分 4 组,最好一次就能确定异常组,再一次就能确定重量,最坏 4+1,分 2 组,最好 2 次确定异常组,一次就能确定重量,最坏 3+1
    Lumuy
        24
    Lumuy  
       2021-02-02 11:20:06 +08:00
    4, 4 -> 4 一次二分
    2, 2 -> 2 二次二分
    1, 1 -> 1 三次二分
    1, 1 替换一球,确定轻重
    Lumuy
        25
    Lumuy  
       2021-02-02 11:24:47 +08:00
    上面写错了,天平状态
    2, 2 判断四分组
    1, 1 判断二分组,平保持,不平换分组
    1, 1 替换一球判断轻重

    最少三次,最多四次
    Alixlucky
        26
    Alixlucky  
       2021-02-02 11:36:54 +08:00
    16 楼正解,2 次就能找出来。
    mxT52CRuqR6o5
        27
    mxT52CRuqR6o5  
       2021-02-02 11:40:33 +08:00   ❤️ 1
    @lance6716
    称一次结果有三种,理想情况下每次操作可以砍到 1/3
    我这边已经想到稳定称 3 次得出轻重的方案了
    mxT52CRuqR6o5
        28
    mxT52CRuqR6o5  
       2021-02-02 11:49:25 +08:00
    @lance6716
    当我没说,想的方案有点问题
    如果按照上面的思路能得出有可能存在最差称 3 次的方案,就是不知道存不存在
    doushiyinweini
        29
    doushiyinweini  
       2021-02-02 11:52:09 +08:00
    分治法, 2 次
    mxT52CRuqR6o5
        30
    mxT52CRuqR6o5  
       2021-02-02 12:45:58 +08:00
    @lance6716
    第一次 124 356
    第二次 123 457
    第三次 158 234
    算的我头大,大家帮我验算看看这个固定方案能不能解决这个问题
    lance6716
        31
    lance6716  
       2021-02-02 13:22:15 +08:00 via Android
    @mxT52CRuqR6o5 30 楼这个不能识别 2 轻 5 重吧

    另外天平能减少的信息量确实不是一半,是多少有空我再想想
    CareiOS
        32
    CareiOS  
       2021-02-02 13:25:41 +08:00
    line 面试的时候 CTO 出了这道题。
    superrichman
        33
    superrichman  
       2021-02-02 13:34:14 +08:00 via iPhone
    找出异常球只要 2 次,找出异常球轻了还是重了要 3 次
    superrichman
        34
    superrichman  
       2021-02-02 13:40:59 +08:00 via iPhone
    @superrichman 知道异常球更轻或更重只要 2 次,不知道要 3 次
    yaphets666
        35
    yaphets666  
       2021-02-02 13:44:43 +08:00
    我想知道 有没有人是 从来没看过类似这种题的方法 然后自己想出答案的?
    CareiOS
        36
    CareiOS  
       2021-02-02 13:47:15 +08:00
    如果要找出那个球是轻还是中就需要三次。
    如果只是找出差异球就需要两次。
    leaveeel
        37
    leaveeel  
       2021-02-02 13:56:59 +08:00
    1 2 3 4 5 6 7 8

    取 123456 六个球三三对比(123, 456)
    情况 1:
    ①123 == 456, 7||8 异常
    ②17 == 23 ? 8 : 7, 异常球中取一个和三个正常球两两对比,找出异常球
    ③7<8||7>8, 异常球和正常球对比,得出轻重
    3 次

    情况 2:
    ①123 != 456, 1||2||3||4||5||6 异常,78 正常
    ②12 == 45 ? 3||6 : 1||2||4||5, 1245 相等 3||6 异常,否则 1||2||4||5 异常

    ③(3||6) 13 == 45 ? 6 : 3;
    ④(3||6) 3<6||3>6;
    4 次,同情况 1

    ③(1||2||4||5) 12>45 ? (14>25 ? 1||5 : 2||4) : (14<25 ? 1||5 : 2||4), 两两对比(12, 45)然后交换一个球(24),结果相同则是没交换的球异常,否则交换的球异常,这里假设 1||5 异常
    ④(1||2||4||5) 16 == 78 ? 5 : 1;
    ⑤(1||2||4||5) 1<5||1>5, 同情况 1
    5 次
    mxT52CRuqR6o5
        38
    mxT52CRuqR6o5  
       2021-02-02 13:57:48 +08:00
    @lance6716
    找到一种方案可以 7/8 找到异常球确定轻重,1/8 找到异常球但确定不了情重
    三次找出异常并确定轻重的方法可能不存在
    mxT52CRuqR6o5
        39
    mxT52CRuqR6o5  
       2021-02-02 14:00:03 +08:00
    我信息论水平有限,没法用科学的方法,足够完善的证出来 3 次找出异常并确定轻重的方案存不存在
    yzbythesea
        40
    yzbythesea  
       2021-02-02 14:01:11 +08:00
    这是道脑筋急转弯(很早之前面 Intel 考的,当时给我说是 brain teaser )。。。面试问这道写代码,我觉得只能写 `print 2`
    mxT52CRuqR6o5
        41
    mxT52CRuqR6o5  
       2021-02-02 14:04:19 +08:00
    第一次 123 456
    第二次 124 357
    第三次 134 267
    可以三次称量确定 1-7 轻重或 8 缺陷(再称一次就能确定 8 轻重)
    kifile
        42
    kifile  
       2021-02-02 14:07:37 +08:00
    来一份伪代码吧

    def find_different_ball(balls: list):
    if len(balls) == 1:
    return balls[0]
    balls_1, balls2, balls_3, balls_other = split(balls) // 将球等个数分为三份,如果不能等分,剩余球放入 ball_other
    if sum(balls) == sum(balls):
    target_balls = balls_3 + balls_other
    if len(target_balls) == 2:
    # 至少保留三个球方便比对
    (target_balls) += balls_1[0]
    return find_different_ball(target_balls )
    else:
    target_balls = balls_1 + balls_2
    if len(target_balls) == 2:
    # 至少保留三个球方便比对
    (target_balls) += balls_3[0]

    return find_different_ball(target_balls )
    mxT52CRuqR6o5
        43
    mxT52CRuqR6o5  
       2021-02-02 14:09:46 +08:00
    @lance6716
    哦哦,想到 3 次的方案了,要动态策略不能固定策略
    第一次 123 456
    如果不平衡则
    第二次 124 357
    第三次 134 267
    如果第一次平衡
    第二次 1 7
    第三次 1 8
    kifile
        44
    kifile  
       2021-02-02 14:10:41 +08:00
    来一份伪代码吧

    ```
    def find_different_ball(balls: list):
    if len(balls) == 1:
    return balls[0]
    balls_1, balls2, balls_3, balls_other = split(balls) // 将球等个数分为三份,如果不能等分,剩余球放入 ball_other
    if sum(balls) == sum(balls):
    target_balls = balls_3 + balls_other
    if len(target_balls) == 2:
    # 至少保留三个球方便比对
    (target_balls) += balls_1[0]
    return find_different_ball(target_balls )
    else:
    target_balls = balls_1 + balls_2
    if len(target_balls) == 2:
    # 至少保留三个球方便比对
    (target_balls) += balls_3[0]

    return find_different_ball(target_balls )
    ```
    kifile
        45
    kifile  
       2021-02-02 14:11:00 +08:00
    不支持 code?
    verzqli
        46
    verzqli  
       2021-02-02 16:59:09 +08:00
    3 次,12 个球也是三次,知乎有篇文章讲过这个
    Exin
        47
    Exin  
       2021-02-02 17:04:41 +08:00
    因为 12 个球是 3 次,所以 8 个球我猜是 2 次
    lwlizhe
        48
    lwlizhe  
       2021-02-02 17:32:22 +08:00
    记得知乎看过一个最少几头猪检测哪桶水有毒的问题;好像差不多;
    https://www.zhihu.com/question/60227816

    根据高赞的回答,试着整活一下哈:

    因为一个小球最多提供三个信息:
    重、轻、普通重量

    所以按三进制来分配小球编号;

    又因为 3^2=9,大于 8 ;

    所以最小 2 次?

    不知道思路对不对
    lwlizhe
        49
    lwlizhe  
       2021-02-02 17:34:44 +08:00
    @lwlizhe 发现问题漏洞了~

    猪那个直接靠本身就可以判断结果……而小球这个,还要弄两组做对比,所以情况不一样
    zzh7982
        50
    zzh7982  
       2021-02-02 17:38:59 +08:00
    至少两次 ,随机选两个球正好重量不想等 1 次,第二次换掉一个球再称就能称出来
    ila
        51
    ila  
       2021-02-02 17:40:00 +08:00
    1,8 个球平均分 ab 两份(每份 4 个),
    2,把 a 份平均分成 a1 和 a2 两份(每份 2 个),
    3,a1 和 a2 称重不相同,
    4,把 a1 平均分成两份 a11 和 a12,
    5,如果 a11 和 a12 称重不一样,则异常球在 a1 里
    6,把 a2 平均分成 a21 和 a22 两份(相同重),
    7,如果 a11 和 a21 称重不一样重,
    8,那 a11 就是异常球.
    至此,至少称重 3 次.
    shyrock
        52
    shyrock  
       2021-02-02 18:27:32 +08:00
    如果给 8 个球的可能状态编码,因为 8 个里面有一个不正常,并且可能轻或者重,所以可能的状态编码共有 8x2=16 个。我们用于探寻问题空间的手段是天平,每次使用天平最多可以把球分成三组,左托盘、右托盘和不上天平,所以实际上可用一个三进制编码来记录称量结果,而要覆盖全部 16 种情况,3^2<16<3^3,所以至少需要三次称量。
    称量操作的要点是:
    1.尽量平均分组;
    2.根据前面称量的结果动态剪掉可能性分支
    newInstance
        53
    newInstance  
       2021-02-02 18:43:25 +08:00
    @Alixlucky 第二次为什么要拿轻的呢 (否则轻的那三个中拿两个比。)为什么说异常球不可能在重的那边呢?
    @Alixlucky
    lwlizhe
        54
    lwlizhe  
       2021-02-02 18:44:27 +08:00
    @lwlizhe 不过做法思路好像差不多,可能还有优化空间吧

    三进制给小球编号:

    000 001 002
    010 011 012
    020 021

    因为只有 8 个球,所以结尾和第二位为 2 的天然少一个,所以不对其进行对比;

    (一)第一步对比结尾为 0 的球和结尾为 1 的球;
    因此是:
    000 010 020 和 001 011 021

    ( 1.1 )如果平衡,那么异常球是结尾是 2 的那俩,随便找个球分别对比下,就知道异常球是哪个,是轻是重;所以三次;

    ( 1.2 )如果不平衡,那么异常球的结尾是 0 或 1 ;记录一下;

    (二)然后对比第二位为 0 的球和结尾为 1 的球;
    因此是:
    000 001 002 和 010 011 012

    ( 2.1 )如果平衡,那么异常球第二位是 2,结合第一步中所述的,异常球结尾是 0 或 1 ;范围确定为 020 和 021,再随便找个球分别对比下,就知道异常球是哪个,是轻是重;所以四次;

    ( 2.2 )如果不平衡,那么异常球第二位是 0 或 1,因此范围确定为 000,010,011,001 这四个;

    (三)尴尬的是,这次没有第三位可供再次对比了,都是 0 ;
    但是因为 000 跟 010 、001 都组队过,唯一没组队的是 011,所以这次对比的是
    000,011 和 010 001

    这次肯定是不平衡的,但是可以根据上次结果判断一下:

    上次结果是 000 001 这边重,这次是 000,011 这边重的话,这说明异常球是这两次中相同的部分;所以是 000 或 010 ;
    那么随便拿个球对比下 000,如果相等,那就是 010 轻;如果不等,那就是 000 重;四次;

    上次结果是 000 001 这边重,这次是 000,011 这边轻的话,那说明异常球是两次中不同的部分,所以是 001 和 011 ;跟上面同理,可验证是异常球及其轻重

    同理可验证 000 001 这边轻的情况; 共计四次
    lwlizhe
        55
    lwlizhe  
       2021-02-02 18:46:37 +08:00
    顺便提一下,各位看清题哦,不仅要知道哪个球是异常球,还要知道是轻还是重~~
    lwlizhe
        56
    lwlizhe  
       2021-02-02 18:53:23 +08:00
    @lwlizhe 更正:

    (二)中应该是这样:
    然后对比第二位为 0 的球和第二位为 1 的球
    lambdAlan
        57
    lambdAlan  
       2021-02-02 19:04:37 +08:00
    最好 3 次最坏 4 次吧。不妨设更轻
    第一次:左右各 4 个,分为 A,B 两队堆。拿出较轻的那一堆 A
    第二次:将较轻的那一堆 4 个分为 2 份
    2.1 如果平衡,,说明 A 中的 4 个是正常的,进一步说明球是较重的且存在 B 堆中,此时将 B 拿去称,进入第三次
    2.2 如果不平衡,拿出较轻的一边,还剩 2 个,此时再进行一次即可,也就是三次。
    第三次:将 B 中的 4 个分为 2 份,因为球较重,这次选出较重的一头(还剩 2 个)再称一次即可
    pkookp8
        58
    pkookp8  
       2021-02-02 19:33:28 +08:00 via Android
    第一次 12 比 34,相等则
    第二次 12 比 78,相等则
    第三次 1 比 5,相等则
    第四次 1 比 6
    mxT52CRuqR6o5
        59
    mxT52CRuqR6o5  
       2021-02-02 20:06:10 +08:00   ❤️ 2
    第一次称 123,456
    如果不平衡则
    第二次称 124,357
    第三次称 134,267
    左重 左重 左重 ->1 重
    左轻 左轻 左轻 ->1 轻
    左重 左重 左轻 ->2 重
    左轻 左轻 左重 ->2 轻
    左重 左轻 左重 ->3 重
    左轻 左重 左轻 ->3 轻
    左轻 左重 左重 ->4 重
    左重 左轻 左轻 ->4 轻
    左轻 左轻 平衡 ->5 重
    左重 左重 平衡 ->5 轻
    左轻 平衡 左轻 ->6 重
    左重 平衡 左重 ->6 轻
    如果第一次平衡
    第二次称 1,7 -> 7 轻或 7 重
    第三次称 1,8 -> 8 轻或 8 重
    只要称 3 次就能找出缺陷球并确定轻重
    ila
        60
    ila  
       2021-02-02 20:08:50 +08:00
    @szxczyc 是的,最理想两次,
    3 个和 3 个称重相同,
    剩下 2 个里其中 1 个和 3 个里的其中 1 个称重,
    找到异常
    pkookp8
        61
    pkookp8  
       2021-02-02 20:35:10 +08:00 via Android
    @pkookp8 知道为什么可以 3 次了
    第一次,123 对 456,不相等(左重)则
    第二次,14 对 25

    球有三种状态,3*8 有 24 种状态
    天平有轻重相等,3^3 等于 27>24
    JeffGe
        62
    JeffGe  
       2021-02-02 20:47:02 +08:00 via Android
    单从信息论的角度讲,所有不同可能性是“1 重、1 轻、2 重、2 轻、……”共 16 种,天平最多提供“左<右、左=右、左>右”3 种不同信息,确定异常球**且**确定异常球是轻是重至少需要 ceil(log3(16))=3 次,上面说 2 次的不用看绝对是错的。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1005 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 21:35 · PVG 05:35 · LAX 13:35 · JFK 16:35
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.