某视频厂的面试题

[fffflyfish]

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

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

可能是我描述有误，结合各位的意见我重述一下：
一个袋子，有 m 个红球，n 个黑球，每次取出两个球，如果球的颜色相同则将取出的球遗弃，并且从其他地方再找一个红球，扔进袋子里，如果取出的球的颜色不同，扔掉红球，黑球放回，问最后剩下的那个球的颜色是什么？

谢谢诸位，没想到会收到这么多关注，非常感谢！

[yagokoro]

答案：m,n 是否均大于等于 1，n 是否为奇数

[fffflyfish]

@yagokoro 怎么说？

[sensui7]

网游武器锻造, 开箱子的算法吗

[yagokoro]

@fffflyfish

n % 2 ？黑 ：红
直说，递归写过没；委婉的说，您可能不太适合创造性工作

[fffflyfish]

@sensui7 额，啥意思？我当时被问蒙了，还是这种看起来很数学的题目，脑子一片空白

[takanasi]

什么鬼题，如果里面只有一个红和一个黑岂不是无限循环了？

[fffflyfish]

@yagokoro 你一说递归我就明白了，非常感谢，您教训的是，我脑子确实不灵光

[am241]

红黑的操作方式有三种[ -1, 0], [1, -2], [1, 0]

[codexu]

为什么我之前一家小公司也是这个题，只不过是确定的数字

[yagokoro]

@fffflyfish 抱歉我这刚才……态度太差言过了，大概就是看到这类问题先想临界情况就是 OTZ

[fffflyfish]

@yagokoro 没关系，您能告知思路已经很感激了，非常感谢

[binux]

我不理解这里拿球做例子，红球还能+-1 的，无中生有吗

[czheo]

感觉不是确定的啊。
以 2 红 2 黑为例：

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

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

所以，最后可红可黑。

[Thexz]

@sensui7 头像不错😂

[xupefei]

出题的人数学功底不足啊。红球的数量是一个真值，没有什么概率问题。
类似的概念错误经常出现在置信区间的计算里：真值永远是一个固定值，并不是什么“真值有 95%可能性在这个区间里”。

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

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

答案是：
i) m 和 n 都为偶数：没有球剩下。
ii) m 和 n 都为奇数：红黑各剩下一个。
iii) 一奇一偶：剩下奇数个的那种。

[czheo]

@xupefei 题目里红球数量+-1 怎么没了？

[fffflyfish]

@binux 你这个关注点哈哈

[xupefei]

@czheo #16 红球的数量是个真值，有多少就是多少。还能人为设定的？

[fffflyfish]

@xupefei 这个题意的目的就是不管你怎么取，每次整体的数量都会减少一个，也就是说不管按照哪种方式取最后都会只剩下一个吧，m，n 值没有定，就是想让人确定出最后什么情况下会剩下哪个球

[xhystc]

题目的意思是要抓到袋子里就剩下一个球，而不是一种颜色，这样的话当袋子里黑球剩 2 个的话，无论红球有多少个，剩下的都会是红球，如果袋子里剩 1 或 3 个黑球，无论袋子里有几个红球，剩下的都是黑球，而黑球总是两个两个丢，所以黑球个数为奇数时剩黑球，反之剩红球

[xupefei]

@czheo #16 换种说法：
> 如果取出的球的颜色不同，那么红球数量-1，取出的球放回
这里的问题是，如果取出了红黑各一个，然后又放了回去，那么盒子里的红球数量没有变化。为什么红球数量会-1 ？
出题人改变了宇宙真理。

[chairuosen]

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]

@xupefei #21 我的错，描述有误，如果取出的球颜色不同，那么只放回黑色的球，红色的球扔掉。

[l00t]

这题我都没看懂。红球怎么+1-1 ？

[acros]

这题目好迷啊。
看流程，只有抓到两个黑的时候，才出现黑色减少红色增加，其他情况下都是红色减少黑色恒定。
总体趋势不是在红黑平衡<->红少黑多之间变化？
结果不应该是算概率吗，恒定的?!

[czheo]

审题有误，最后剩下一个球，我还以为最后剩下一种颜色就停止了。。。

[fffflyfish]

@l00t 重新组织了下语言，在 append，sorry 哈

[binux]

@fffflyfish 那取出两个黑球，红球怎么+1 ？无中生有吗

[fffflyfish]

@acros 我当时也是用概率做的，然后一直往概率的方向想，如果能往递归的原理想想，比如#4，#22，就不至于答不出来了。。。

[fffflyfish]

@binux 算是吧，你就当从别的地方拿来一个红球，然后扔进去嘛，只要满足颜色相同就可以这么干

[Andiry]

红球用 0 代替，黑球用 1 代替，最后剩下的值就是所有球的易或，所以只取决于黑球数量是奇数还是偶数

[l00t]

看了补充描述，那么看 n 是不是奇数。是奇数的话剩下的就是黑的。是偶数的话，那早晚黑的会全部取出，剩下的是红的

[nigelvon]

22 楼没毛病

[acros]

根据 append 重新列了下，22 对了~

[ZxBing0066]

红球数量+1-1 是指放一个或拿出一个红球？题目看的我蒙蔽

[introom]

这种题，到底是证明个什么

[Tink]

22 楼厉害

[BlackCat02]

22 楼正解，比我的解法简单明了多了

[yuang]

22 楼牛逼。我居然还写了段代码 才做出来。

[xml123]

22 楼说的很清楚了，不过其实还可以简化成一句话：
黑球数量的奇偶性不会改变，所有剩下的颜色是 n%2==0?R:B

[kdplus]

这... 题目条件要分析分析撒，这关键黑球只有-2 的选项啊，n 是奇数的时候，必剩下黑球撒

[chengchuan1009]

31 楼简单明了

[sensui7]

@chairuosen 仰望, 我只能这样

[scnace]

异或解法 666666

[66beta]

受教了，希望多来点这种分享帖

[xiaojunjor]

厉害厉害，学习了

[void1208]

《编程珠玑》第四章出现过这道题，正好刚看的。。

[LeoNG]

受教了。

[justicelove]

自己瞎想的。

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

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

如果 M < 1/2 N， 则剩下 N 也就是黑球的几率大
M = 1/2N 红黑都有可能
M > 1/2N 则红球几率大。

[justicelove]

#22 楼牛逼，N 的奇偶性不会变。66666

[xiaoyao9933]

#31 楼比 #22 楼还屌。。这题就是考 XOR 的。发现了问题的本质啊。

[lengyihan]

@Thexz 头像是 pronhub 的色彩吧

[Thexz]

@lengyihan 老司机哟