逃生

来自计算思维百科
跳转至: 导航搜索
逃生.jpg

有一个人质关在一个房间里。这个房间有4个门。第一个门是一个隧道,出口又返回了这个房间,整条隧道需要13分钟走完。第二个门也是一个隧道,出口也是这个房间,整条需要17分钟。第三个门是一条通向外界获得自由的隧道,12分钟走完。第四个门也是通向自由的隧道,18分钟走完。问题是,这个人如果要获得自由,逃生的平均时间是多少分钟?

1

2

3

4

时间

13

17

12

18

出口

房间

房间

外界

外界

解决方案-穷举法

假设人质足够聪明,如果知道某条路走不通,不会走第二次。因此人质最多走三条隧道就可以获得自由,那么逃生的平均时间指的是所有可能的逃生路径所需时间的平均值。这里我们还需要考虑到选择该路径的概率。由于人质的选择有限,因此我们很容易就能够想到穷举列举所有可能情况。

人质要想获得自由,那么他最后一定要选择第3或第4个门,并且在此之前选择的门必然是走不通的,或者他第一次就选择了正确的门。那么我们可以列举出人质获得自由的所有可能路径如下:

(1)人质选择一次就获得了自由:3、4

(2)人质选择两次获得自由:13、14、23、24

(3)人质选择三次获得自由:123、124、213、214

对于每种路径计算逃生所需时间:

例如选择路径123,人质先走第一个门,花费13分钟,然后走第二个门,花费17分钟,最后走第三个门,花费12分钟,最后获得自由,总共花费了13+17+12=42分钟。

计算选择该路径的概率。第一次是从4个门中选择第一个门,概率是1/4;第二次从3个门中选择第二个门,概率是1/3;第三次从2个门中选择第三个门,概率是1/2。因此选择路径123的概率是1/4×1/3×1/2=1/24。其他可获得自由的路径依此类推。我们可以得到如下表格:

路径

3

4

13

14

23

24

123

124

213

214

概率

1/4

1/4

1/12

1/12

1/12

1/12

1/24

1/24

1/24

1/24

时间(分钟)

12

18

25

31

29

35

42

48

42

48

根据上述表格,计算人质的平均逃脱时间是t=12×0.25+18×0.25+(25+31+29+35)×(1/12)+(42+48+42+48)×(1/24)=25min。

运用的计算思维

因为可供选择的路径不多,所以利用穷举法列举出所有的逃脱可能路线,再利用概率论的知识计算出人质的平均逃脱时间,是最直观最简便的方式,这是一种机械化的思维方式。

参考文献

https://trello.com/c/SblFDlF5/52--