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

昨日题解

每日一题 | 约瑟夫问题

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

种方法是模拟法，也就是说我们用一个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个抽屉。如果每个人都可以找到和自己编号一样的卡片，那么就将囚犯们全员释放。

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

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