现在的位置: 首页 > 综合 > 正文

编程之美4.11的问题

2013年05月19日 ⁄ 综合 ⁄ 共 2755字 ⁄ 字号 评论关闭

首先,这道问题我还没有准确的答案,准备在这里一边写一边整理思路:

 

题目:不再重复了,涉及到图形,比较难以叙述清楚。写一些关键点:游戏盘为16x16。已知一共有40个地雷。除此之外唯一知道的信息是有8个格子中只有一颗雷;有8个格子中有两颗雷。这8个格子的关系如下:

 

***

*1*

***

*2*

***

 

第一问:当40个地雷都没有发现时,a,b,c处有地雷的概率是多少?

*a*

*1*

*b*

*2*

*c*

 

分析:

挨个看条件:

1)游戏为16*16的维度,一共有40个地雷。如题目所说,第一次点击后才生成地雷。因为可以认为游戏的生成过程为40个地雷均匀的分布在(16*16-1=255)个格子中。注意一个格子中是不能放两颗地雷的。因此在不知道任何其它条件的情况下一个格子中有地雷的概率是:40/255。

2)在一个呈现8字形的图形中,上面的口中有一颗地雷,下面的口中有两颗地雷。可以分析出在一共15个格子中,一共有两种可能:只有2颗地雷,或者只有3颗地雷。2颗地雷的情况,一定有且仅有一颗地雷出现在中间的3个格子中,另一颗出现在下方的5个格子中。3颗雷的情况上方的5个格子中一定有一颗地雷,中间的3个格子没有地雷,下方的5个格子中有2颗地雷。现在可以看出如下图所示,所有的a,b,c拥有相同的概率:

 

a a a

a 1 a

b b b

c 2 c

c c c

 

我们在这里写出两个条件:

A:这15个空格中有3颗地雷

B:这15个空格中有2颗地雷

 

现在考虑第一个比较难的问题,一共有40个地雷和P(a),P(b),P(c)到底有没有关系?如果有,有什么样的关系。在某些情况下他们的关系很明确,比如如果地雷总数为(256-15+3=244)个地雷,则可以确定除掉这个8字型的所有空格都有地雷,且8字型中有3颗地雷,即P(A)=1; P(B)=0。但现在的问题是在241个空格中有38或者37个地雷。这个条件会对P(A),P(B)产生影响吗?我曾经一度觉得没有影响,即它们是独立的事件。但是,想想好象不对。具体的原因部详细解释了,起码如果没有第一个条件,我们都无法得知P(A)和P(B)的大小。再写出两个已知的条件:

C:256个格子中有40颗地雷

D:这15个空格中只有能2颗或者3颗地雷

好,现在我们求P(A|CD)及P(B|CD)。

根据条件概率,有P(A|CD) = P(ACD)/P(CD)

 

先求P(CD)。

 

先写到这,明天继续。

 

同时小小的怀疑一下,ms的同志们是否已经有了可靠的答案?能不能在哪里公布一下呢?

 

〈继续〉

 

先求P(CD):256个格子有40颗雷(严格来说是255个格子),平均一个格子中有地雷的概率为Peg=40/255。15个格子(严格来说是14个格子)中只有两个格子有地雷的概率是C(14,2)*POW(Peg,2)*POW((1-Peg),12)。只有3个格子有地雷的概率是C(14,3)*POW(Peg, 3)*POW((1-Peg),11)。所以有:

P(CD) = C(14,2)*POW(Peg, 2)*POW((1-Peg),12) + C(14,3)*POW(Peg, 3)*POW((1-Peg),11)。

 

P(ACD) = C(14,3)*POW(Peg,3)*POW((1-Peg),11)。

P(BCD) = C(14,2)*POW(Peg,2)*POW((1-Peg),12)。

 

P(A|CD) = C(14,3)*POW(Peg,3)*POW((1-Peg),11) / (C(14,2)*POW(Peg, 2)*POW((1-Peg),12) + C(14,3)*POW(Peg, 3)*POW((1-Peg),11))

P(B|CD) = C(14,2)*POW(Peg,2)*POW((1-Peg),12) / (C(14,2)*POW(Peg, 2)*POW((1-Peg),12) + C(14,3)*POW(Peg, 3)*POW((1-Peg),11))

 

有了这两个概率,接下来求P(A),P(B),P(C)

 

P(A) = P(A|CD) * (1/5) + P(B|CD) * 0

P(B) = P(A|CD) * 0 + P(B|CD) * (1/3)

P(C) = P(A|CD) * (2/5) + P(B|CD) * (1/5)

 

下面是我算出来的具体数值:

P(ACD) ~ 0.00042

P(BCD) ~ 0.00452

P(A|CD) ~ 0.085

P(B|CD) ~ 0.915

P(A) ~ 0.017

P(B) ~ 0.305

P(C) ~ 0.217

 

对这个答案我不是很有把握。仅从常理上大概分析,P(A|CD)之所以比较低,P(B|CD)之所以比较高,是255个格子中放入40

颗雷的合理反映。40/255*14~2.196。所以在那个8字型的图案中最有可能存在两颗雷。在这种情况下,中间的B点存在雷的可能性反而最大,而C点其次。A点是可能性最小的点。当然,我们在玩挖雷时就不一定了,记得这个结果和40与255这两个数是有关系的。

 

再看该问题的第二问:

第一问比较明确,P(A),P(B),P(C)和当前局面中的地雷总数肯定是有关系的。但是具体的关系和是否相交就要考察一下数学中函数的知识了。当Peg变大时P(ACD)和P(BCD)应该不是单调的。但是依常理分析,P(A|CD)应该是保持单调增长的,P(B|CD)应该是保持单调减少的(这个严格的数学证明有时间再说,先看看能不能得到一个合理的结果)。这样我们可以这样认为,P(A)应该单调增长,P(B)应该单调减少,P(C)也会跟随p(a)保持单调增长。这个第二问我这里纯粹是推断,没有任何证明。需要有时间好好回忆一下这种类型函数的性质了。先看看再有10颗雷和240颗雷时的情况分别怎样吧:

 

10颗雷:

P(ACD) ~ 0.014137

P(BCD) ~ 0.086591

P(A|CD) ~ 0.14035

P(B|CD) ~ 0.85965

P(A) ~ 0.02807

P(B) ~ 0.28655

P(C) ~ 0.22807

 

40颗雷:

P(ACD) ~ 0.00042

P(BCD) ~ 0.00452

P(A|CD) ~ 0.085

P(B|CD) ~ 0.915

P(A) ~ 0.017

P(B) ~ 0.305

P(C) ~ 0.217

 

240颗雷:

P(ACD) ~ 8.855e-12

P(BCD) ~ 1.3836e-13

P(A|CD) ~ 0.9846

P(B|CD) ~ 0.0154

P(A) ~ 0.19692

P(B) ~ 0.0051

P(C) ~ 0.39692

 

从这个结果看,P(A)P(B)P(C)并非单调,而是出现了先下降再上升的过程。无外乎两种可能,问题1种的计算不对,或者问题2的推断不对。应该说问题2种推理并不严谨,所以还很难判断问题出现哪里。但假如问题1的结果正确,至少可以看到P(A)P(B)P(C)是会相交的。回来再进一步考证哪里出了问题。

【上篇】
【下篇】

抱歉!评论已关闭.