100个白球100个黑球，取出两个球，同色则补充黑色，异色则补充白色。最后剩什么颜色

柔情只为你懂 2023-06-07 05:50 20阅读 0赞

## 【题目描述】 ##

桶中取黑白球

有一个桶，里面有白球、黑球各100个，人们必须按照以下规则把球取出来：  
1、每次从桶中那两个球  
2、如果是两个同色的球，那就再放入一个黑球  
3、如果是两个异色的球，那就再放入一个白球

问：最后桶里面最后剩下一个球是白球和黑球的概率各是多少。

## 【思路解析】 ##

### 思路一：归纳总结 ###

依靠枚举的思路，比如假设黑白球各10个、5个、2个等来分析和推断，然后找规律。

分析过程可以参考《编程之美》第4.6节中的“桶中取黑白球”题。

### 思路二：连续异或 ###

对桶中的球而言，取出2个球共有3种情况：

1、取出两个黑球，放回一个黑球  
2、取出两个白球，放回一个黑球  
2、取出一黑一白，放回一个白球

将上述的过程抽象成为数学上的异或运算：

1、2个黑球变成1个黑球 ==> `1 ^ 1 = 1`  
2、2个白球变成1个黑球 ==>`0 ^ 0 = 1`  
3、1白1黑变成1个白球 ==> `1 ^ 0 = 1`

在上述的抽象的过程中，主要利用了异或的性质：**相同得0，不同得1**。因此可以将同色时放入的黑球用0代替，异色时放入的白球用1代替。

由于异或运算满足结合律(`a ^ b ^ c = a ^ (b ^ c)`)和交换律(`a ^ b = b ^ c`)，那么就有  
`a ^ b ^ c = a ^ c ^ b = b ^ a ^ c = b ^ c ^ a = c ^ a ^ b = c ^ b ^ a`

也就是异或结果与异或的顺序无关，任意的异或顺序最终计算的结果都是一致的。

桶中取出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节 桶中取黑白球

发表评论取消回复

表情：

评论列表（有 0 条评论，20人围观）

还没有评论，来说两句吧...

相关阅读

相关用java程序编程实现从三个红球，五个白球，六个黑球中任意取出八个球，且必须有白球，输出所有可能的方案。...

可以使用组合排列数学原理来解决这个问题，具体实现可以使用 Java 程序。首先，要从三个红球，五个白球，六个黑球中取出八个球，需要计算出红球最多取出的个数，白球最多取出的个数，

谁践踏了优雅/ 2024年03月25日 11:46/ 0 赞/ 73 阅读

相关模拟双色球

玩法说明：双色球投注区分为红球号码区和蓝球号码区，红球号码范围为1~ 33，蓝球号码范围为1~16，双色球每期从33个红球中开出6个号码，从16个蓝球中开出1个号码作为中

拼搏现实的明天。/ 2023年12月31日 06:06/ 0 赞/ 93 阅读

相关 python 三色球问题

2. 三色球问题有红、黄、蓝三种颜色的求，其中红球 3 个，黄球 3 个，绿球 6 个。先将这 12 个球混合放在一个盒子中，从中任意摸出 8

妖狐艹你老母/ 2023年07月16日 11:59/ 0 赞/ 9 阅读

相关 100个白球100个黑球，取出两个球，同色则补充黑色，异色则补充白色。最后剩什么颜色

【题目描述】桶中取黑白球有一个桶，里面有白球、黑球各100个，人们必须按照以下规则把球取出来： 1、每次从桶中那两个球 2、如果是两个同色的球，那就再放入一

柔情只为你懂/ 2023年06月07日 05:50/ 0 赞/ 21 阅读

相关每天一道算法题：n个球中取出m个球不同思路分析

楔子在开始算法分析之前，这里需要引入数学中组合、排列的概念，先基本介绍一下组合、排列：排列： 1. 定义：从n个不同的元素中任取m个(m<=n)元素，按照

我不是女神ヾ/ 2022年10月28日 03:59/ 0 赞/ 296 阅读

相关【专题】小球与盘子在4中限制下的放置可能性——同球同盘、异球同盘、同球异盘、异球异盘，C++算法实现

0\引入考试时遇到同球同盘的问题，一开始想用插板法，终究失败，只拿了20分，回家问了老师，老师告了我方法并让我自己研究剩下三种。 1\同球同盘——递推或递归（+记忆

╰+攻爆jí腚メ/ 2022年08月29日 10:04/ 0 赞/ 54 阅读

相关双色球小游戏

import java.util.Arrays; import java.util.Random; import java.util.Scanner;

今天药忘吃喽~/ 2022年06月17日 09:21/ 0 赞/ 345 阅读

相关双色球随机数

![70][] package com.job; public class randomtest { public static

短命女/ 2022年05月19日 14:21/ 0 赞/ 318 阅读

相关 python双色球

1、红色球6个，1，33，蓝色球1个，1-16 1、先从1，33之间取6个 random.sample([1,33],6) 2，再从1-1

墨蓝/ 2021年12月14日 11:45/ 0 赞/ 406 阅读

相关项目4：三色球问题

问题及代码： /\ \copyright (c) 2014,烟台大学计算机学院 \All rights reserved. \文件名称：test.cpp

妖狐艹你老母/ 2021年06月10日 20:41/ 0 赞/ 353 阅读