V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
fffflyfish
V2EX  ›  问与答

某视频厂的面试题

  •  2
     
  •   fffflyfish · 2017-11-22 16:28:41 +08:00 · 6716 次点击
    这是一个创建于 2537 天前的主题,其中的信息可能已经有所发展或是发生改变。

    一个袋子,有 m 个红球,n 个黑球,每次取出两个球,如果球的颜色相同则将取出的球遗弃,并且红球数量+1,如果取出的球的颜色不同,那么红球数量-1,取出的球放回,问最后剩下的那个球的颜色是什么?计算方式是怎么样的?

    各位有思路吗?说是会有一个公式可以确定结果,咋做呀

    第 1 条附言  ·  2017-11-22 17:52:40 +08:00
    可能是我描述有误,结合各位的意见我重述一下:
    一个袋子,有 m 个红球,n 个黑球,每次取出两个球,如果球的颜色相同则将取出的球遗弃,并且从其他地方再找一个红球,扔进袋子里,如果取出的球的颜色不同,扔掉红球,黑球放回,问最后剩下的那个球的颜色是什么?
    第 2 条附言  ·  2017-11-23 11:26:50 +08:00
    谢谢诸位,没想到会收到这么多关注,非常感谢!
    53 条回复    2017-11-23 21:25:39 +08:00
    yagokoro
        1
    yagokoro  
       2017-11-22 16:36:39 +08:00 via Android   ❤️ 1
    答案:m,n 是否均大于等于 1,n 是否为奇数
    fffflyfish
        2
    fffflyfish  
    OP
       2017-11-22 16:38:09 +08:00
    @yagokoro 怎么说?
    sensui7
        3
    sensui7  
       2017-11-22 16:40:55 +08:00
    网游武器锻造, 开箱子的算法吗
    yagokoro
        4
    yagokoro  
       2017-11-22 16:44:40 +08:00 via Android
    @fffflyfish

    n % 2 ?黑 :红
    直说,递归写过没;委婉的说,您可能不太适合创造性工作
    fffflyfish
        5
    fffflyfish  
    OP
       2017-11-22 16:45:42 +08:00
    @sensui7 额,啥意思?我当时被问蒙了,还是这种看起来很数学的题目,脑子一片空白
    takanasi
        6
    takanasi  
       2017-11-22 16:50:07 +08:00
    什么鬼题,如果里面只有一个红和一个黑岂不是无限循环了?
    fffflyfish
        7
    fffflyfish  
    OP
       2017-11-22 16:51:46 +08:00   ❤️ 1
    @yagokoro 你一说递归我就明白了,非常感谢,您教训的是,我脑子确实不灵光
    am241
        8
    am241  
       2017-11-22 16:51:57 +08:00 via Android
    红黑的操作方式有三种[ -1, 0], [1, -2], [1, 0]
    codexu
        9
    codexu  
       2017-11-22 16:53:49 +08:00
    为什么我之前一家小公司也是这个题,只不过是确定的数字
    yagokoro
        10
    yagokoro  
       2017-11-22 16:57:23 +08:00 via Android
    @fffflyfish 抱歉我这刚才……态度太差言过了,大概就是看到这类问题先想临界情况就是 OTZ
    fffflyfish
        11
    fffflyfish  
    OP
       2017-11-22 17:09:14 +08:00
    @yagokoro 没关系,您能告知思路已经很感激了,非常感谢
    binux
        12
    binux  
       2017-11-22 17:18:09 +08:00 via Android
    我不理解这里拿球做例子,红球还能+-1 的,无中生有吗
    czheo
        13
    czheo  
       2017-11-22 17:25:58 +08:00
    感觉不是确定的啊。
    以 2 红 2 黑为例:

    如果取出 2 黑, [剩下 3 红] 。
    如果取出 1 红 1 黑或 2 红,都剩下 1 红 2 黑。

    继续 1 红 2 黑的情况:
    如果取出 1 红 1 黑, [剩下 2 黑] 。
    如果取出 2 黑, [剩下 2 红] 。

    所以,最后可红可黑。
    Thexz
        14
    Thexz  
       2017-11-22 17:27:41 +08:00 via iPhone
    @sensui7 头像不错😂
    xupefei
        15
    xupefei  
       2017-11-22 17:37:29 +08:00   ❤️ 1
    出题的人数学功底不足啊。红球的数量是一个真值,没有什么概率问题。
    类似的概念错误经常出现在置信区间的计算里:真值永远是一个固定值,并不是什么“真值有 95%可能性在这个区间里”。

    把谬误删除后剩下的问题应该是:

    一个袋子,有 m 个红球,n 个黑球,每次取出两个球,如果球的颜色相同则将取出的球遗弃;如果取出的球的颜色不同,取出的球放回。最后剩下的那个球的颜色是什么?

    答案是:
    i) m 和 n 都为偶数:没有球剩下。
    ii) m 和 n 都为奇数:红黑各剩下一个。
    iii) 一奇一偶:剩下奇数个的那种。
    czheo
        16
    czheo  
       2017-11-22 17:40:57 +08:00
    @xupefei 题目里红球数量+-1 怎么没了?
    fffflyfish
        17
    fffflyfish  
    OP
       2017-11-22 17:42:26 +08:00
    @binux 你这个关注点哈哈
    xupefei
        18
    xupefei  
       2017-11-22 17:42:33 +08:00
    @czheo #16 红球的数量是个真值,有多少就是多少。还能人为设定的?
    fffflyfish
        19
    fffflyfish  
    OP
       2017-11-22 17:45:14 +08:00
    @xupefei 这个题意的目的就是不管你怎么取,每次整体的数量都会减少一个,也就是说不管按照哪种方式取最后都会只剩下一个吧,m,n 值没有定,就是想让人确定出最后什么情况下会剩下哪个球
    xhystc
        20
    xhystc  
       2017-11-22 17:45:47 +08:00 via Android   ❤️ 1
    题目的意思是要抓到袋子里就剩下一个球,而不是一种颜色,这样的话当袋子里黑球剩 2 个的话,无论红球有多少个,剩下的都会是红球,如果袋子里剩 1 或 3 个黑球,无论袋子里有几个红球,剩下的都是黑球,而黑球总是两个两个丢,所以黑球个数为奇数时剩黑球,反之剩红球
    xupefei
        21
    xupefei  
       2017-11-22 17:46:45 +08:00
    @czheo #16 换种说法:
    > 如果取出的球的颜色不同,那么红球数量-1,取出的球放回
    这里的问题是,如果取出了红黑各一个,然后又放了回去,那么盒子里的红球数量没有变化。为什么红球数量会-1 ?
    出题人改变了宇宙真理。
    chairuosen
        22
    chairuosen  
       2017-11-22 17:47:56 +08:00   ❤️ 26
    BB: R+1 B-2
    RR:R+1 R-2 = R-1
    RB: R-1
    可见每次操作总数-1
    所以最后一个球之前的状态是最后有两个球。
    最后两个球的三种状态 BB BR RR
    BR=B
    BB= R
    RR = R
    什么时候是 BR 呢?因为每次操作 B 都是两个减,则最开始 B 的数量 n 为奇数最后两个球一定是 BR。
    所以 n%2==0?R:B
    fffflyfish
        23
    fffflyfish  
    OP
       2017-11-22 17:49:11 +08:00
    @xupefei #21 我的错,描述有误,如果取出的球颜色不同,那么只放回黑色的球,红色的球扔掉。
    l00t
        24
    l00t  
       2017-11-22 17:49:33 +08:00
    这题我都没看懂。红球怎么+1-1 ?
    acros
        25
    acros  
       2017-11-22 17:56:12 +08:00
    这题目好迷啊。
    看流程,只有抓到两个黑的时候,才出现黑色减少红色增加,其他情况下都是红色减少黑色恒定。
    总体趋势不是在红黑平衡<->红少黑多之间变化?
    结果不应该是算概率吗,恒定的?!
    czheo
        26
    czheo  
       2017-11-22 17:56:38 +08:00
    审题有误,最后剩下一个球,我还以为最后剩下一种颜色就停止了。。。
    fffflyfish
        27
    fffflyfish  
    OP
       2017-11-22 17:56:48 +08:00
    @l00t 重新组织了下语言,在 append,sorry 哈
    binux
        28
    binux  
       2017-11-22 17:57:40 +08:00 via Android
    @fffflyfish 那取出两个黑球,红球怎么+1 ?无中生有吗
    fffflyfish
        29
    fffflyfish  
    OP
       2017-11-22 17:58:57 +08:00
    @acros 我当时也是用概率做的,然后一直往概率的方向想,如果能往递归的原理想想,比如#4,#22,就不至于答不出来了。。。
    fffflyfish
        30
    fffflyfish  
    OP
       2017-11-22 18:00:06 +08:00
    @binux 算是吧,你就当从别的地方拿来一个红球,然后扔进去嘛,只要满足颜色相同就可以这么干
    Andiry
        31
    Andiry  
       2017-11-22 18:01:44 +08:00   ❤️ 3
    红球用 0 代替,黑球用 1 代替,最后剩下的值就是所有球的易或,所以只取决于黑球数量是奇数还是偶数
    l00t
        32
    l00t  
       2017-11-22 18:02:32 +08:00
    看了补充描述,那么看 n 是不是奇数。是奇数的话剩下的就是黑的。是偶数的话,那早晚黑的会全部取出,剩下的是红的
    nigelvon
        33
    nigelvon  
       2017-11-22 18:04:14 +08:00
    22 楼没毛病
    acros
        34
    acros  
       2017-11-22 18:10:20 +08:00
    根据 append 重新列了下,22 对了~
    ZxBing0066
        35
    ZxBing0066  
       2017-11-22 18:14:05 +08:00
    红球数量+1-1 是指放一个或拿出一个红球?题目看的我蒙蔽
    introom
        36
    introom  
       2017-11-22 18:49:20 +08:00 via Android
    这种题,到底是证明个什么
    Tink
        37
    Tink  
       2017-11-22 18:57:10 +08:00 via iPhone
    22 楼厉害
    BlackCat02
        38
    BlackCat02  
       2017-11-22 19:57:09 +08:00
    22 楼正解,比我的解法简单明了多了
    yuang
        39
    yuang  
       2017-11-22 20:17:17 +08:00
    22 楼牛逼。我居然还写了段代码 才做出来。
    xml123
        40
    xml123  
       2017-11-22 20:37:47 +08:00   ❤️ 1
    22 楼说的很清楚了,不过其实还可以简化成一句话:
    黑球数量的奇偶性不会改变,所有剩下的颜色是 n%2==0?R:B
    kdplus
        41
    kdplus  
       2017-11-22 20:41:57 +08:00
    这... 题目条件要分析分析撒,这关键黑球只有-2 的选项啊,n 是奇数的时候,必剩下黑球撒
    chengchuan1009
        42
    chengchuan1009  
       2017-11-22 21:53:26 +08:00
    31 楼简单明了
    sensui7
        43
    sensui7  
       2017-11-23 00:21:08 +08:00
    @chairuosen 仰望, 我只能这样
    scnace
        44
    scnace  
       2017-11-23 01:27:55 +08:00 via Android
    异或解法 666666
    66beta
        45
    66beta  
       2017-11-23 08:48:15 +08:00
    受教了,希望多来点这种分享帖
    xiaojunjor
        46
    xiaojunjor  
       2017-11-23 09:26:33 +08:00
    厉害厉害,学习了
    void1208
        47
    void1208  
       2017-11-23 09:26:38 +08:00
    《编程珠玑》第四章出现过这道题,正好刚看的。。
    LeoNG
        48
    LeoNG  
       2017-11-23 10:04:48 +08:00
    受教了。
    justicelove
        49
    justicelove  
       2017-11-23 13:59:30 +08:00
    自己瞎想的。

    有三种情况:
    红 黑
    -1 0
    +1 -2
    -1 0

    假设 mn 都很大,以上三种情况出现的比例则趋向于 1:1:1, 则总的趋势也就是平均红黑减少比例 红: 黑 = 1:2

    如果 M < 1/2 N, 则剩下 N 也就是黑球的几率大
    M = 1/2N 红黑都有可能
    M > 1/2N 则红球几率大。
    justicelove
        50
    justicelove  
       2017-11-23 14:05:07 +08:00
    #22 楼牛逼,N 的奇偶性不会变。66666
    xiaoyao9933
        51
    xiaoyao9933  
       2017-11-23 15:28:59 +08:00
    #31 楼比 #22 楼还屌。。这题就是考 XOR 的。发现了问题的本质啊。
    lengyihan
        52
    lengyihan  
       2017-11-23 19:12:15 +08:00 via Android
    @Thexz 头像是 pronhub 的色彩吧
    Thexz
        53
    Thexz  
       2017-11-23 21:25:39 +08:00 via iPhone
    @lengyihan 老司机哟
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   990 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 20:17 · PVG 04:17 · LAX 13:17 · JFK 16:17
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.