酒店发生了一起谋杀案。作为镇上最好的侦探,你应该立刻检查酒店所有的n个客房。然而,所有客房的门都锁上了,而且钥匙都锁在客房里。真是一个陷阱!每个客房里恰好只有一把锁匙,而且分布的概率相同。例如,如果n=3,有6种可能的分布,分布的概率都是1/6。为方便起见,我们将客房从1到n编号,并且记1号客房的钥匙为key1,2号客房的钥匙为key2,等。
要检查所有的客房,不得不用武力破坏一些门,但又不想破坏太多,所以采取以下策略:开始时,因为手里没有钥匙,必须随意破坏一个锁着的门,进入客房,检查房间,拿走里面的钥匙。接着可以用新的钥匙打开另一个客房,检查并拿走第二把锁匙。一直重复,直到不能打开新的客房。如果仍有客房没有检查,就要随机选择另一个未打开的门并破门而入,重复上述过程,直到检查完所有的客房。
现在规定只允许破坏k个门。更重要的是,有一位要人住在1号客房,这个门不能破坏,只能用钥匙打开它并检查。编程计算,要检查所有的客房,其概率是多少。