三门问题(Monty Hall problem)的代码模拟
今天偶尔看到有人在讨论三门问题，这个问题有点意思，但稍微有点绕。
三门问题(Monty Hall problem)亦称为蒙提霍尔问题、蒙特霍问题或蒙提霍尔悖论，大致出自美国的电视游戏节目Let‘s Make a Deal。问题名字来自该节目的主持人蒙提·霍尔(Monty Hall)。有三扇关闭的门，其中一扇门后面是汽车，另外两扇门后面各是一只山羊。节目主持人事先知道每扇门后面分别是什么东西(汽车还是山羊)。节目嘉宾可以从三扇门中挑选一扇门，如果选中后面有汽车的那扇门可赢得该汽车。当嘉宾选定了一扇门但未去开启它的时候，节目主持人会打开剩下两扇门中有山羊的那一扇门(如果剩下的两扇门都是山羊，那么主持人随机从两扇门中挑一扇打开)。主持人在打开有山羊的一扇门后，会问嘉宾要不要改为选择另一扇仍然关着的门。问题是：换另一扇门是否能增加嘉宾赢得汽车的机率？
周末没事，给出一个C代码的模拟，模拟上面这个“嘉宾先选一扇门、主持人打开一扇门、嘉宾决定是否换门”的操作，模拟次数定义为MAX_TRIES。模拟完后，打印出总次数、嘉宾首次即选中汽车的概率、嘉宾换门之后赢得汽车的概率。
#include "pch.h"#include#include#include
classCRand
{public:
CRand()
{
m_weakRndReady= false;
m_hProv=NULL;if (!CryptAcquireContext(&m_hProv, NULL, NULL, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT))
{
srand(GetTickCount());
m_weakRndReady= true;
}
}~CRand()
{if(m_hProv)
CryptReleaseContext(m_hProv,0);
}
DWORD GenDWORD()
{
DWORD r;if (m_hProv && CryptGenRandom(m_hProv, sizeof(DWORD), (BYTE*)&r))returnr;if (!m_weakRndReady)
{
srand(GetTickCount());
m_weakRndReady= true;
}return rand() *GetTickCount();
}private:
HCRYPTPROV m_hProv;boolm_weakRndReady;
};enum{
GOAT= 0, //山羊
CAR = 0xFF, //汽车
};
constexpr DWORD NUM_DOORS= 3;
DWORD doors[NUM_DOORS];
CRand rnd;
inlinevoidInitDoors()
{
memset(doors, GOAT,sizeof(doors)); //每个门都初始化为山羊
doors[rnd.GenDWORD() % NUM_DOORS] = CAR; //其中随机的一个门初始化为汽车
}const DWORD doorsLeftTable[NUM_DOORS][NUM_DOORS - 1]
{
{1, 2 }, //首次选编号为0的门时，则剩下编号为1、2的门
{ 0, 2 }, //首次选编号为1的门时，则剩下编号为0、2的门
{ 0, 1 } //首次选编号为2的门时，则剩下编号为0、1的门
};
inlinevoid OpenTheDoorWithGoat(const DWORD doorChosen, DWORD &doorOpen, DWORD &doorLeft)
{const DWORD *doorsLeft =doorsLeftTable[doorChosen];
DWORD doorIndex= rnd.GenDWORD() % (NUM_DOORS - 1); //剩下的两个门中先随机选一个
doorOpen =doorsLeft[doorIndex];
doorLeft= doorsLeft[1 -doorIndex];if (doors[doorOpen] == CAR) //随机选中的门里是汽车，则改成不是汽车的那个门
{
DWORD t= doorOpen; //交换
doorOpen =doorLeft;
doorLeft=t;
}
}int main(int argc, char**argv)
{
constexpr DWORD MAX_TRIES= 100000;
DWORD winOnFirst= 0; //首次即选中汽车的次数 = 不更换门时选中汽车的次数
DWORD winOnChange = 0; //更换门之后，选中汽车的次数
for (DWORD k = 0; k < MAX_TRIES; ++k)
{
InitDoors();
DWORD doorChosen= rnd.GenDWORD() % NUM_DOORS; //随机选个门
if (doors[doorChosen] ==CAR)++winOnFirst;
DWORD doorOpen, doorLeft;
OpenTheDoorWithGoat(doorChosen, doorOpen, doorLeft);//打开剩下两个门中有山羊的门
if (doors[doorLeft] ==CAR)
++winOnChange;
}
printf("%u, %.3f%%, %.3f%%", MAX_TRIES, (float)winOnFirst * 100.0 / (float)MAX_TRIES,
(float)winOnChange * 100.0 / (float)MAX_TRIES);return 0;
}
使用Windows Crypto API提供的随机数。可以看到，模拟次数越多，随机数越接近理想状态，这是自然的。
首次选中汽车的概率，加上换门选中汽车的概率，为100%，看起来很巧合。这是因为：
1、首次如果选中了汽车(概率为1/3)，那么换门就必然丢掉汽车，换句话说，不换门就必然赢得汽车。这个分支的结论和主持人开两个门中的哪个门完全没关系。
2、首次如果没选中汽车(概率为2/3)，那么必须换门才能赢得汽车(这个和主持人开门无关)。而且换门就必然赢得汽车(想想是为什么？因为主持人的开门暴露了剩下的那个没汽车的门才导致的呀！)。
综合1和2，换个方式说：
如果嘉宾采取换门的策略，有2/3的概率赢得汽车；
如果嘉宾采取不换门的策略，有1/3的概率赢得汽车；
如果你是嘉宾，你会选哪种策略？
C:WINDOWSsystem32> C:UsershappysourceeposProject1ReleaseProject1.exe100000000, 33.333%, 66.667%
C:WINDOWSsystem32> C:UsershappysourceeposProject1ReleaseProject1.exe100000000, 33.324%, 66.676%
C:WINDOWSsystem32> C:UsershappysourceeposProject1ReleaseProject1.exe10000000, 33.347%, 66.653%
C:WINDOWSsystem32> C:UsershappysourceeposProject1ReleaseProject1.exe1000000, 33.388%, 66.612%
C:WINDOWSsystem32> C:UsershappysourceeposProject1ReleaseProject1.exe100000, 33.560%, 66.440%
