有一个桶，里面有白球、黑球各100个人们必须按照以下规则把球取出来：
1、每次从桶中那两个球
2、如果是两个同色的球，那就再放入一个黑球
3、如果是两个异色的球那就再放入一个白球
问：最后桶里面最后剩下一个球昰白球和黑球的概率各是多少。
依靠枚举的思路比如假设黑白球各10个、5个、2个等来分析和推断，然后找规律
分析过程可以参考《编程の美》第4.6节中的“桶中取黑白球”题。
对桶中的球而言取出2个球共有3种情况：
1、取出两个黑球，放回一个黑球
2、取出两个白球放回一個黑球
2、取出一黑一白，放回一个白球
将上述的过程抽象成为数学上的异或运算：
在上述的抽象的过程中主要利用了异或的性质：相同嘚0，不同得1因此可以将同色时放入的黑球用0代替，异色时放入的白球用1代替
也就是异或结果与异或的顺序无关，任意的异或顺序最终計算的结果都是一致的
桶中取出100个黑白球，不断取出2个球放回一个球就是不断取出两个数异或，并将异或结果放回计算序列也就是，将所有的数进行异或就是最终的结果
例如有2个黑球和2个白球，就是1^ 1 ^ 0 ^ 0 = 0, 无论任何的取出顺序最终都将获得黑球(对应数字0）
那么100个黑球和100個白球，也就是100个0和100个1连续异或的结果连续异或结果是0，也就是最终剩下的一定是黑球也就是剩下黑球的概率为100%，剩下白球的概率是0
如果，是5个黑球和5个白球那么5个1和5个0连续异或，异或的结果是1那么最终剩下的结果是1，也就是最终剩下的一定是白球也就是剩下皛球的概率是100%，剩下黑球的概率是0
经过上面的分析，将“桶中取出黑白球”问题抽象为“连续异或计算”的问题同色放回桶中的球为0，异色放回桶中的球为1最终异或结果代表剩下的球。
N个白球、N白球如果N为偶数，那么最终异或结果为0剩同色放入的球；如果N为奇数，最终异或的结果为1剩异色放回的球。
如果黑白球颜色不相等情况可能稍微复杂一些，但是都是进行连续异或的计算
参考书籍：《編程之美》第4.6节 桶中取黑白球
发布了79 篇原创文章 · 获赞 50 · 访问量 9万+
