程序员入伙书——换还是不换
- 2016年05月7日
- 发布在 infotech . on my mind
- 留下评论
话说，这道题，十几年前，玩论坛的时代，就出现在网上了：
三道门，一道门后面有车，另外两道门，后面都是羊。
有个节目主持人，他知道车在那道门后。
他请你选一道门，但不立即打开。
他在剩下的两道门里，打开一道，放出一只羊给你看。
现在台上还剩两道门关着，一道是你选的，一道是谁也没碰过的。
主持人说：现在你有个机会，可以改变主意，挑另一道门。
不管你换还是不换，你最终选中的那道门，后头的东西都归你。
你换不换？——假设价值观是车比羊好。
当时，论坛上吵成一片，有说该换的，有说不该换的。对于不换而中奖的概率，大家比较一致：1/3。而对于换而中奖的概率，基本上有三个说法：1/3、1/2、2/3。
论坛上贴题的那人说：“正确答案是应该换，中奖概率会从1/3提升到2/3。并且，此答案经过了智商排名极靠前的一位人士的认可。不过，还是有许多不愿盲信权威的年轻人，自己动手，用各种办法做实验，有大活人亲自做的，有用计算机模拟的，而结果一致确认：该换，中奖概率确实提升到了2/3。另外，虽然实验结果如此，有相当多的亲手做实验的人依然坚持（理论上）不该换。”
时至今日，这道题提到人口稠密的社交媒体上来，依然能够引起争论。
为了让读者老爷们怀着轻松的心情观看余下的内容，我提前把答案确认一下：
应该换。
我不是从一道门换到另一道门，
而是从一道门换到另外两道门。
“换并且选到车”的概率 = “第一次没选到车”的概率
三道门的迷惑性较大，读者可以极端化一下：如果是一亿道门，你挑一扇（选中车的概率很悲观），然后主持人把许许多多门打开，放出来满坑满谷的羊，最后只留下一道门，你换不换？
或者再换一个思路：主持人挑你和另外一个现场观众上来，让你选一道门，让那位观众选两道门，然后问你，愿不愿意拿你的一道门换那位观众的两道门？
“开门放羊”只是个迷惑动作，当门的总数大于2时，挑剩下的门里，一定能放出至少一只羊。所以它没有增加任何信息，也没有改变概率分布，这一步骤和事后开奖并无不同。
用概率论的运算过程则是：
- 换而中车的概率 =
首次选羊的概率 × 拿羊换到车的概率 +
首次选车的概率 × 拿车换到车的概率 - 首次选羊的概率 = 2/3
- 首次选车的概率 = 1/3
- 拿羊换到车的概率 = 100%
- 拿车换到车的概率 = 0%
- 因此，换而中车的概率 = 2/3
如果你看到这里还是觉得数学上不该换，那就可以关掉页面了。接下来并没有理论上的新内容，而且因为要用程序表达，技术上会比较烧脑。我不想让你同时背两个包袱走路，会芯片过热的。
虽然这道题没有数学理论难度，我还是想拿它做个编程的例子。原因是，我发现用计算机的思维，可以洞穿这道题的本质。做完实验依然坚持不该换的人里面，一定没有用计算机模拟的。
我的第一版程序很简单（手机读者可用手指左右拖动代码区）：
import random
def lottery(n, change): # n是门的个数，change设置“换还是不换”
car = random.randint(0, n - 1) # 为车生成一个随机的门号
pick = random.randint(0, n - 1) # 我选择一个随机的门号
# 如果我未选中车但愿意换，或者我选中了车并且不换
if (pick != car and change) or (pick == car and not change):
return True # 我都会中奖
else: # 否则
return False # 就不会
repeat = 100 # 重复做此实验100次
win = 0 # “中奖”计数器置零
for i in range(repeat):
if lottery(3, True): # 每次都选择“换”
win += 1 # 如果中奖，计数器加一
# 打印中奖百分比
print("%.2f%%" % (win / repeat * 100))
结果如何呢？运行三遍：
=============== RESTART: cargoat.py =============== 68.00% >>> =============== RESTART: cargoat.py =============== 71.00% >>> =============== RESTART: cargoat.py =============== 68.00% >>>
100次实验，如果选择“换”，中奖次数确实在2/3左右。当然我们也得反过来做一下，把lottery函数的第二个参数设为False：
repeat = 100 # 重复做此实验100次
win = 0 # “中奖”计数器置零
for i in range(repeat):
if lottery(3, False): # 每次都选择“不换”
win += 1 # 如果中奖，计数器加一
# 打印中奖百分比
print("%.2f%%" % (win / repeat * 100))
运行三遍，选择“不换”的中奖概率确实较低：
=============== RESTART: cargoat.py =============== 34.00% >>> =============== RESTART: cargoat.py =============== 34.00% >>> =============== RESTART: cargoat.py =============== 27.00% >>>
还可以发现，实验的重复次数（repeat的值）越高，中奖概率越是稳定在2/3上，下面是repeat = 100000的三遍运行结果：
=============== RESTART: cargoat.py =============== 66.55% >>> =============== RESTART: cargoat.py =============== 66.81% >>> =============== RESTART: cargoat.py =============== 66.70% >>>
在这个程序里，原本热热闹闹的挑门、开门放羊、问你换不换的那些动作，一下子被简化成了“你第一次猜中的概率有多大”的问题。我刚才说：“做完实验依然坚持不该换的人里面，一定没有用计算机模拟的。”是因为写程序前，我先假装认为不该换，而写下lottery函数的前两行时，就找到了事情本质的描述方式（上面的粗大字体）。
然而，读者可能认为，我并没有精确地按照剧本来写，所以运算结果不可信。为此，我必须按照剧本写一遍程序，像宋小宝吃面那样，辣根和蒜瓣这些步骤都不能省。说实在的，因为需要彻底改变思路，写新程序很累，但我还是勉力完成了：
import random
def lottery(n, change, debug = False):
door = ['goat' for i in range(n)] # 把n道门后都放上羊。
car = random.randint(0, n - 1) # 生成随机中奖号码，从0到n-1，共n种可能。
door[car]= 'car' # 在此号码的门后放上车。
if debug: # 给后台观众看一下：门后都有什么。
print(door)
pick = random.randint(0, n - 1) # 我随机挑选一个门，也是0到n-1，n种可能。
if debug: # 为了照顾一般读者，
print('I pick ', pick + 1) # 打印pick+1是因为Python数组下标从0开始，下同。
if pick != car: # 切换到主持人视角，如果我没选到车，
left = car # 那么他就留下后面有车的这道门不打开。
else: # 而如果我选中了车（仍然是主持人视角），
while True: # 他就在剩下的门里，
left = random.randint(0, n - 1) # 随意挑选一个
if left != pick: # 用于保持关闭的门。
break
if debug: # 主持人打开n-2道门，
for i in range(n): # 放出n-2只羊，
if i != pick and i != left: # 只留一道关着。
print('Host opens ', i + 1, ' and shows me a ', door[i])
if change: # 如果我决定换，
pick = left # 那么我就挑这道留下来的门。
if debug:
print('I change my mind and pick ', pick + 1)
else: # 如果我决定不换，
if debug: # 一切不变。
print('I stick to ', pick + 1)
if debug: # 现在开奖。
print('Door ', pick + 1, ' opens and shows me a ', door[pick], end='. ')
if door[pick] == 'car': # 如果我选的是车，
if debug: # 那么我赢了奖，世界很美好。
print('I WIN!', end = '\n\n')
return True
else: # 否则，
if debug: # 领个羊回去也没什么……
print('I LOSE...', end = '\n\n')
return False
repeat = 100 # 重复做此实验100次
win = 0 # “中奖”计数器置零
for i in range(repeat):
if lottery(3, True, True): # 每次都选择“换”，打印中间过程
win += 1 # 如果中奖，计数器加一
# 打印中奖百分比
print("%.2f%%" % (win / repeat * 100))
为了取得读者的信任，我还放了一些调试打印语句，用来观察细节：起初哪扇门后面有车，我选了哪一扇，主持人打开了哪一扇，如果我改主意，是不是赢了奖，得到的是什么。
打开调试来看看运行五遍的结果，中奖率60%。五遍的结果稳定性会很差，主要是确认一下中间过程的模拟是不是够精确，又不想被一大堆调试信息刷屏。关掉调试信息，再跑几遍100000次循环的，结果就又稳在了2/3上：
=============== RESTART: cargoat.py =============== ['car', 'goat', 'goat'] I pick 3 Host opens 2 and shows me a goat I change my mind and pick 1 Door 1 opens and shows me a car. I WIN! ['goat', 'car', 'goat'] I pick 2 Host opens 1 and shows me a goat I change my mind and pick 3 Door 3 opens and shows me a goat. I LOSE... ['goat', 'goat', 'car'] I pick 1 Host opens 2 and shows me a goat I change my mind and pick 3 Door 3 opens and shows me a car. I WIN! ['goat', 'goat', 'car'] I pick 1 Host opens 2 and shows me a goat I change my mind and pick 3 Door 3 opens and shows me a car. I WIN! ['goat', 'car', 'goat'] I pick 2 Host opens 3 and shows me a goat I change my mind and pick 1 Door 1 opens and shows me a goat. I LOSE... 60.00% >>> =============== RESTART: cargoat.py =============== 66.50% >>> =============== RESTART: cargoat.py =============== 66.47% >>> =============== RESTART: cargoat.py =============== 66.30% >>>
在这个复杂的新版本里，大部分语句都用来打印中间结果了，如果我们把这些if debug的程序块都去掉，就能得到一个不简不繁的版本：
def lottery(n, change):
door = ['goat' for i in range(n)] # 把n道门后都放上羊
car = random.randint(0, n - 1) # 生成随机中奖号码，从0到n-1，共n种可能
door[car]= 'car' # 在此号码的门后放上车
pick = random.randint(0, n - 1) # 我随机挑选一个门，也是0到n-1，n种可能
#----------------------------------
if pick != car: # 切换到主持人视角，如果我没选到车……
left = car # 那么他就留下后面有车的这道门不打开
else: # 而如果我选中了车（仍然是主持人视角）
while True: # 他就在剩下的门里随意挑选一个
left = random.randint(0, n - 1) # 用于保持关闭的门
if left != pick:
break
#----------------------------------
if change: # 如果我决定换
pick = left # 那么我就挑这道留下来的门
if door[pick] == 'car': # 如果我选的是车
return True # 那么我赢了奖，世界很美好
else: # 否则
return False # 领个羊回去也没什么……
这里，我有意放了两行分割线，因为两行线之间，是这个节目最迷惑人的部分：主持人开门放羊。这段代码是个if-else块，分“如果我第一次没选中车”（if pick != car）和“如果第一下选中了”（else）来讨论。“如果第一次没选中车”的代码很简单，主持人没什么可说的，只要留着有车的那道门不开就行了（left = car）。而“如果第一下选中了”的代码稍微复杂些，主持人需要在所有的羊门里头，随机挑一个用来保持关闭的。为此我写了个while循环来达到这一功能：努力产生一个随机数，直到它不等于我挑的那扇门为止，把这扇门留下来。
虽然我模拟“随机”的诚意很足，但这段代码完全是浪费时间，因为在“第一次选中了车”的前提下，主持人无论留下哪道门，门后都铁定是只咩咩叫的羊。所以这段代码可以继续简化如下：
def lottery(n, change):
door = ['goat' for i in range(n)] # 把n道门后都放上羊
car = random.randint(0, n - 1) # 生成随机中奖号码，从0到n-1，共n种可能
door[car]= 'car' # 在此号码的门后放上车
pick = random.randint(0, n - 1) # 我随机挑选一个门，也是0到n-1，n种可能
#----------------------------------
if pick != car: # 切换到主持人视角，如果我没选到车……
carleft = True # 那么主持人留下的门后一定是车
else: # 而如果我选中了车（仍然是主持人视角）
carleft = False # 那么主持人留下的门后一定是羊
#----------------------------------
# 如果我决定换，并且主持人留下的门后是车
# 或者如果我不换，并且主持人留下的门后是羊
if (carleft and change) or (not charleft and not change):
return True # 那么我会中奖，世界很美好
else: # 否则
return False # 领个羊回去也没什么……
然后我们就看到door数组在新的简化版里完全不再用到，carleft和pick != car的对应关系十分简单，也可以省略运算。这段程序和开头的那个版本成功会师，可谓殊途同归：
def lottery(n, change):
car = random.randint(0, n - 1) # 生成随机中奖号码，从0到n-1，共n种可能
pick = random.randint(0, n - 1) # 我随机挑选一个门，也是0到n-1，n种可能
# 如果我未选中车但愿意换，或者我选中了车并且不换
if (pick != car and change) or (pick == car and not change):
return True # 那么我会中奖，世界很美好
else: # 否则
return False # 领个羊回去也没什么……
