每日一题 | 约瑟夫问题

昨日题解

每日一题 | 不确定参与人数的抽奖问题

这是一个非常经典的算法问题，对应的解法称作蓄水池算法。别看它有一个专门的算法名称，但是它的思维非常简单。

假设我们一共有n个人参与抽奖，在当下n未知，奖品一个有k个。我们用一个长度为k的数组存储中奖的人的信息。首先，我们将前k个出现的候选人放入数组当中。

从第k+1个出现的候选人开始，我们假设当前的候选人的序号是i，i > k。我们随机一个1 ~ i的数r，如果得到的结果小于k，那么我们将i替换掉中奖数组当中r位置的人，如果大于k，说明此人没中奖。

我们用代码写出整个过程非常简单：

Import random
win = []

def reservoir(n, k):
 if n < k:
  win.append(n)
  return
 r = random.randint(0, n)
 if r < k:
  win[r] = n

怎么样，我们看代码逻辑是不是非常简单呢？

这样的确是实现了随机性，但是能满足每一个人的中奖概率一样吗？会不会出现的时机不同，中奖概率也不一样？

我们可以来试着算一下这个概率，对于不同的位置我们要分不同的情况。对于前k个出现的人来说，他们一开始就出现在了中奖名单当中，要想最终中奖，需要在中途的时候不被替换。

当走到第k+1个人时，他要想不被替换的概率是1 - k+1个人中奖的概率乘上刚好替换他的概率。

同理，我们可以得到对于k+2个人他不被替换的概率是。我们以此类推得到第n个人不被替换的概率是。

我们把这些概率乘在一起就得到了总体中奖的概率：

同样，对于k之后出现的人，我们假设他出现的次序是j。那么他留下来的概率是，对于j+1到n的人，他需要留下来不被替换，我们也可以得到他最终获奖的概率：

这样我们就证明了，无论在什么位置出现，中奖的概率都是。也就是说这是一个公平的抽奖算法。

今日问题

约瑟夫问题

这是一道经典的算法题，说是有n个罪犯围成一圈，分别编号1到n。从1号开始报数，当报到m时，将报m的罪犯处决。接着再从1开始报数，直到最后只剩下一个罪犯为止。

请问给定n和m，求最终剩下的罪犯编号，你能想出对应的解法吗？