`
OpenMind
  • 浏览: 179810 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

车羊问题的一种简洁证明

阅读更多
在csdn上看到一篇关于车羊问题的文章(http://blog.csdn.net/naturebe/article/details/7272232),我编了个程序证明了结论,然后给出了一种简洁的数学证明。如下:

   车羊问题(Car and Goats problem)又叫蒙提霍尔问题(Monty Hall Problem)或三门问题。这个问题来源于美国电视娱乐节目Let’s Make a Deal,问题的名字则来自该节目的主持人蒙提·霍尔(Monty Hall)。问题是这样的:参赛者会看见三扇关闭了的门,其中一扇的后面有一辆汽车,选中后面有车的那扇门就可以赢得该汽车,而另外两扇门后面则各藏有一只山羊。当参赛者选定了一扇门,但未去开启它的时候,节目主持人会开启剩下两扇门的其中一扇,露出其中一只山羊。主持人其后会问参赛者要不要换另一扇仍然关上的门。明确的限制条件如下:参赛者会被问是否保持他的原来选择,还是转而选择剩下的那一道 那么换与不换,哪种策略答对的机率高呢?

   思考了一下,感觉换的概率可能是1/3,1/2,2/3,无法确定,于是写个程序找到正确答案先:
程序证明
	static Random random1 = new Random();
	static Random random2 = new Random();
	static Random random3 = new Random();
	static int COUNT = 100000000;

	public static void main(String[] args) {
		//whether re-choise after prompt. 
		boolean retry = true;
		int got = 0;
		for (int i = 0; i < COUNT; i++) {
			int[] data = generateData();
			int c = Math.abs(random2.nextInt()) % 3;
			if (retry) {
				int p = prompt(data, c);
				int choise = excluse(c, p);
				got += data[choise];
			} else {
				got += data[c];
			}
		}
		System.out.println("retry:" + retry + ",got car:" + got + ",count="
				+ COUNT + ",probability=" + got * 1.0 / COUNT);
	}

	static int excluse(int c, int p) {
		if (c + p == 1) {
			return 2;
		} else if (c + p == 2) {
			return 1;
		} else if (c + p == 3) {
			return 0;
		}
		return -1;
	}
	
	static int prompt(int[] data, int c) {
		int[] choise = new int[2];
		int j = 0;
		for (int i = 0; i < data.length; i++) {
			if (i != c) {
				if (data[i] == 1)// car
					choise[j++] = -1;
				else
					choise[j++] = i;
			}
		}
		if (choise[0] >= 0 && choise[1] >= 0) {// c is not car
			return choise[Math.abs(random3.nextInt()) % 2];
		} else if (choise[0] < 0) {
			return choise[1];
		} else {
			return choise[0];
		}
	}
	/**
	 * 1 for car,0 for goat
	 */
	static int[] generateData() {
		int[] data = new int[3];
		data[Math.abs(random1.nextInt()) % 3] = 1;
		return data;
	}


上面的程序,当把retry设成true和false,count设成1亿,得到的输出分别是:
// retry:true,got car:66671490,count=100000000,probability=0.6667149
// retry:false,got car:33331411,count=100000000,probability=0.33331411
从而从程序的角度证明:不换获得车的概率是1/3;换,获得车的概率是2/3.

数学证明
其实用逆推法很容易得出2/3的结论,仔细思考一下,就会发现:
   参赛者换了门而且获得了车,当且仅当参赛者第一次选择的门后面是羊。根据等价事件的概率相等的数学原理,问题转换成参赛者第一此选择的门后是羊的概率,也就是2/3.
分享到:
评论

相关推荐

    简洁非交互式零知识证明参数(zk-SNARKS),本文系统介绍了zk-SNARKS的数学理论,需要有一定的数学功底的人进行阅读

    我们构建了一个系统,为冯·诺依曼RISC体系结构上的程序执行提供简洁的非交互式零知识证明(zk SNARKs)。该系统由两部分组成:一个用于验证算术电路可满足性的密码验证系统,以及一个用于将程序执行转换为此类电路...

    vb.net 一种简洁的数组元素随机排序方法

    vb.net 一种简洁的数组元素随机排序方法

    简洁非交互零知识证明综述.pdf

    安全性是简洁非交互零知识证明的核心问题之一。这些协议的安全性可以通过不同的攻击模型来评估,例如,中间人攻击、重放攻击、选择平面攻击等。在实际应用中,需要根据不同的应用场景选择合适的攻击模型来评估协议的...

    简洁大气喜庆红2015羊年剪纸ppt模板.rar

    剪纸是一种传统的中国民间艺术,通常用红色纸张剪裁出各种图案,如生肖、花卉等,寓意吉祥如意。这个PPT模板将这些元素融入设计中,使得每一张幻灯片都充满节日气氛。 “简洁大气喜庆红2015羊年剪纸ppt模板”这一...

    平面电磁波特性的一种证明方法.pdf

    综上所述,本文提供了一种简洁的数学方法,利用麦克斯韦方程组的积分形式,直接证明了平面电磁波的横波特性,即电场和磁场矢量与波的传播方向垂直,且不随传播方向变化。这种方法对于理解和教学电磁波理论提供了有力...

    张辉-布道师-《简洁的力量 》

    在C/C++编程语言中,尤其是在处理字符串匹配问题时,简洁不仅仅是一种风格,更是一种高效解决问题的手段。传统的做法中,程序员可能会编写一个复杂的字符串遍历算法来查找符合特定模式的字符串,如电子邮件地址。...

    养羊技术培训简洁PPT学习教案.pptx

    养羊技术培训简洁PPT学习教案.pptx

    高效简洁的一种图像分割方法

    高效简洁的一种图像分割方法,分割效果好,执行速度快,是最新的全自动分割方法

    一种简洁单点登录系统设计与实现

    摘要:阐述了SSO的基本原理,并设计了一个简洁SSO系统,解决了不同Web应用系统之间的互访问题:用户 登录一次即可访问所有Web系统。系统设计简单实用,不需要建设昂贵复杂的认证服务器,对现有系统的改动很 少,扩展...

    企业法定代表人身份证明书.docx

    这是一种简洁的法人代表身份证明书格式,内容包括法人代表的姓名、身份证号码、单位地址、联系方式等信息。该证明书通常由法人代表本人签字,并加盖单位公章。 篇四:法人身份证明书 这是一种法人身份证明书的格式...

    2020年高考数学理科一轮复习 精品讲义 17.2 直接证明与间接证明 新人教A版.doc

    再者,反证法是一种间接证明方法,它假设结论不成立,然后推导出与已知事实或逻辑矛盾的结果,从而证明原命题的正确性。这种方法特别适合处理否定性的命题或需要讨论多种可能情况的问题。例如,证明某个等式总是不...

    实习证明模板(两种格式).rar

    在IT行业中,实习证明是大学生或求职者在完成实习经历后,由实习单位出具的一种官方文档,证实他们在实习期间的工作内容、表现及所积累的技能。这个名为“实习证明模板(两种格式).rar”的压缩包文件包含两个不同格式...

    Ruby 是一种动态、面向对象的编程语言,具有简洁而灵活的语法

    Ruby 是一种动态、面向对象的编程语言,具有简洁而灵活的语法。

    二手车购买合同简洁样本.doc

    二手车购买合同简洁样本.doc

    “线束原理”在几何证明中的应用[参照].pdf

    因此,我们需要一种更好的方法来解决这种问题,这就是“线束原理”。 “线束原理”可以将多条线段经过同一点的问题转化为一个简单的比例关系的问题,从而使得证明变得更加简洁明了。例如,在例1中,我们可以通过...

    用python编写的一款小游戏,实现人狼羊菜过河

    【标签】"python" 指出这款游戏的开发语言是Python,这是一种高级通用型编程语言,以其简洁明了的语法和丰富的库资源受到程序员的广泛喜爱。Python适合初学者入门,也适用于开发各种类型的应用程序,包括桌面应用、...

    2-附件2:工作证明模板(仅供参考,非指定模板) (1).docx

    在建筑行业中,工作证明是一种非常重要的文档,它用于证实个人在特定时间段内在某公司或机构工作的事实。这个模板提供了一个通用格式,可以帮助个人或企业快速出具工作证明。以下是该工作证明模板涉及的关键知识点:...

    filecoin时空证明论文1

    PoST是一种资源消耗证明机制,它鼓励用户在时间和空间上投入资源来参与网络活动,从而增加攻击的成本。 与传统的工作量证明(Proof of Work,PoW)不同,PoST更加注重能源效率。在PoW中,矿工需要通过大量的计算...

    羊了个羊(100行Python代码).zip

    Python是一种高级编程语言,以其简洁的语法和易于阅读的代码而闻名。在"羊了个羊"这个游戏中,Python将作为程序的后端,处理逻辑和交互。 pygame zero的核心概念是“一切都是对象”,这意味着游戏中的每一项——如...

Global site tag (gtag.js) - Google Analytics