每日一题 | 一百个囚犯与一百个抽屉问题

2020-08-06 00:00:00 算法 囚犯 抽屉 死了 种方法


昨日题解

每日一题 | 约瑟夫问题

约瑟夫问题是一道非常经典的问题,有很多非常巧妙的解法,我们今天分享其中比较简单的两种。

种方法是模拟法,也就是说我们用一个n个节点的链表来模拟算法运行的过程,直到链表当中只剩下一个元素为止。这样当然是可以的,实现难度也不是很大,但是有一个缺点是计算的复杂度很高,是。当n和m都很大的时候,我们是无法很快得出答案的。

这个时候就需要用第二种方法了,第二种方法就是递推法,我们仔细分析这个问题,会发现它其实是隐藏着递推的规律的。

我们举个例子,假设n=8,m=3.

1 2 3 4 5 6 7 8,显然轮死的是3,死了3之后剩下的人是1 2 4 5 6 7 8.从4开始继续。

我们先打住,来思考一个问题,n=8,死了一个人,不就是n=7的情况吗?只不过n=7的正常情况是从1开始的,而我们n=8死了一个之后是从4开始的。但也没问题,这中间相差了一个m。既然相差了一个m那么我们加上不就完了?

所以我们假设我们有一个函数f(n, m)可以直接根据n和m算出后的赢家,那么我们可以得到f(n, m) = (f(n-1, m) + m) % n。

也就是说f(n, m)是f(n-1, m)加上m,因为是围成一个圈所以要对n取模。

显然当n=1的时候,答案就是1,所以我们根据上面这个递推式一推,很容易得到答案。

这题还有更快的算法,同样是基于递推实现,大家感兴趣可以思考一下。如果想不出来也没问题,能够吃透递推的解法已经足够了。


今日问题

一百个囚犯和一百个抽屉问题

这题来自粉丝推荐

说是在一个监狱里有100个囚犯,他们有各自的编号1-100.有一天监狱长准备和他们玩一个游戏考验他们的智商和运气,监狱长准备了100个抽屉,另外准备了100张卡片,分别写有1-100放入了抽屉当中。

监狱长和囚犯们说,每一个人都有一次打开抽屉寻找卡片的机会,每个人多可以打开50个抽屉。如果每个人都可以找到和自己编号一样的卡片,那么就将囚犯们全员释放。

请问,囚犯们应该采取什么样的策略呢?

注意:囚犯们依次进入房间寻找,每一个人在寻找结束之后都必须把所有抽屉合上。囚犯只能在游戏开始之前交流策略,游戏一旦开始之后不能交流,也不能以任何方式传递信息。

相关文章