威廉姆斯为什么拿白球黑球每次拿两个

桶中有n个黑球n个白球黑球每次拿两个,取球规则如下:每次从桶中取两个球如果两球同色,则放回一个黑球否则放回一个白球黑球每次拿两个。

问:最后桶中剩下┅个黑球的概率是多大

分析取球的规则,每次取完球之后黑球的数量要么增1,要么减1白球黑球每次拿两个的数量要么不变,要么减2

如果说桶中只剩下一个球,鉴于白球黑球每次拿两个的递减是以2为倍数所以,当n为奇数时桶中剩下的一定是白球黑球每次拿两个,當n为偶数时桶中剩下的一定是黑球。

编程之美中作者提出了用异或的数学逻辑来模拟取球的过程,黑球看作是0白球黑球每次拿两个看作是1,这样的话取球规则就相当于把取出的数字异或之后再把结果丢回去。

这样以来每次取完数字之后,所有数字的异或的结果是鈈变的要么是0,要么是1当1的个数为奇数时,奇数个1的异或结果是1偶数个1的异或结果为0,0的个数不影响异或结果

所以,把1和白球黑浗每次拿两个对应起来得出的结论是当有奇数个白球黑球每次拿两个时,桶中剩下的一个一定是白球黑球每次拿两个当白球黑球每次拿两个的个数为偶数时,桶中剩下的一个一定是黑球

note:编程之美中的问题中给出的n为100,我们很容易就从100个黑白球黑球每次拿两个从头开始分析想着怎么样模拟取球的过程,能够递归到桶中只剩一个黑球的情形然后陷入到复杂的穷举当中去,

我刚开始就是这么干的搞叻一个下午,还写了个程序去跑结果是程序没跑出结果来,原因是穷举的规模太大了当n为100的时候,穷举的规模大概为3199

so,一开始就应該有个正确的思路考虑穷举是不可行的,应该从取球的规则中挖掘规律原来,就这么简单吼啊x。

我要回帖

更多关于 五个黑球五个白球一次拿两个 的文章

 

随机推荐