100囚徒难题解法

alexandrell

刚刚看到本版有noski发的点击率超过15000的100囚徒难题http://bbs.mf8-china.com/viewthread.php?tid=699&extra=page%3D1这个贴子，在这个相对冷清的版块里，算是很难得了。我说一下我的解法。有两种思路，一种是保命思路，即只有在确定不死的前提下，才向国王提出特赦，hw236的大体思路是对的，但是具体做法还可以更优化。做法就是首先第一天先打开那盏灯，然后在第2天到第100天这个过程中，如果有囚徒是第2次或更多次出来放风时，则关闭那盏灯，因为只要有一个人是2次以上出来放风，就意味着所有人都不可能在100天之前出来了。然后再约定在第101天放风的囚徒，将灯点亮，所有人的计数都清零，从101到300天之间，如果有人是3次或更多次出来放风（从101天清零的数算起）则将灯熄灭，这就意味着所有人都不可能在300天之前出来。依次类推，在第301天放风的囚徒，将灯点亮，所有人的计数再清零，在后301到600天之间，如果有人是4次或更多次出来放风（从301天清零的数算起）则将灯熄灭，这就意味着所有人都不可能在600天之前出来。以上的策略是基于鸡兔同笼法则，用这种试错的方式，估计出来的日期会提前很多。而考率到100天，200天之内出来的可能性很低，大家也可以约定从500天或用更长的日期做为一个特赦周期。
       第二种思路是赌博思路，就是说不保证肯定可以活命，而是权衡利弊，只要活命的可能性大于一个概率，就提出特赦，假设前提是每天所有人放风的机率是一样的，都为0.01。在第X天，X>=100时，所有囚徒都至少出来过一次的概率为：
       (100^x - 99^x - 98^x -. .. 1^x) / 100^x。

       下面是我编写的用于计算在第x天可以成功特赦的php程序。
<?
$MaxDaysExpectedOut = 1000;
$TotalGuys = 100;

for ($DaysExpectedOut = 100; $DaysExpectedOut <= $MaxDaysExpectedOut; $DaysExpectedOut += 100)
{
  $CantOutRatio = 0;
   
  for ($Guys = 1; $Guys < $TotalGuys; $Guys ++)
  {
   $CantOutRatio += exp(log($Guys / $TotalGuys) * $DaysExpectedOut);
  }
  
  $SuccessOutRatio = 1 - $CantOutRatio;

  echo "<p>The ratio of ".$TotalGuys." guys would success out of the prison after ".
  $DaysExpectedOut." days  is ".$SuccessOutRatio."</p>";
}
?>

结果为：
The ratio of 100 guys would success out of the prison after 100 days is 0.427885933629
The ratio of 100 guys would success out of the prison after 200 days is 0.845846692964
The ratio of 100 guys would success out of the prison after 300 days is 0.948514054585
The ratio of 100 guys would success out of the prison after 400 days is 0.9817349154
The ratio of 100 guys would success out of the prison after 500 days is 0.993388248453
The ratio of 100 guys would success out of the prison after 600 days is 0.997589538541
The ratio of 100 guys would success out of the prison after 700 days is 0.99911896674
The ratio of 100 guys would success out of the prison after 800 days is 0.999677681922
The ratio of 100 guys would success out of the prison after 900 days is 0.999882043503
The ratio of 100 guys would success out of the prison after 1000 days is 0.99995682707

可以看到第1000天之后，只要是国王不有意为难大家的话，应该都可以出去了，500天的话其实也差不多，要是图个刺激，一定要在最短时间内出狱的话，其实第100天就申请特赦成功的机率也是很大的。

javidliu

乱码好多啊，。。。。。。。

javidliu

乱码好多啊，。。。。。。。

Cielo

原帖由 javidliu 于 2008-11-18 20:22 发表
乱码好多啊，。。。。。。。

那不是乱码吧，应该是lz的程序

ben_zheng

LZ好强啊   加油啊

mrliao123

沙发和板凳的回复太雷人了~~

kexin_xiao

坐地上和LZ学习一下

魔鱼儿

楼主编写的程序看不到哦,这个题好像有人发过哦,

我喜欢你

乱码好多啊，。。。。。。。