某视频厂的面试题

[fffflyfish]

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

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

[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