前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >每日一题 | 约瑟夫问题

每日一题 | 约瑟夫问题

作者头像
TechFlow-承志
发布2020-08-05 23:49:44
9660
发布2020-08-05 23:49:44
举报
文章被收录于专栏:TechFlow

昨日题解

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

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

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

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

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

代码语言:javascript
复制
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,求最终剩下的罪犯编号,你能想出对应的解法吗?

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-08-05,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Coder梁 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 每日一题 | 不确定参与人数的抽奖问题
  • 今日问题
    • 约瑟夫问题
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档