专栏首页深度学习技术前沿【六一儿童节】回忆一下“孩子们的游戏”!(码农版)

【六一儿童节】回忆一下“孩子们的游戏”!(码农版)

【导读】当您点进这个页面时,相信您无论在学习还是工作中还依旧怀有一颗童心!愿您出走半生,归来仍是少年!那今天就祝您儿童节快乐!(今天我们大家都是小孩子),下面就让我们来一起回顾一下孩子们的游戏(程序员版)

程序员版的儿童小游戏

今天,我们来回忆一下程序员版的儿童小游戏。六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。DL作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢?(注:小朋友的编号是从0到n-1)

解决方案

每次挑出一个小朋友后,从当前位置再计数。如果只求最后一个报数胜利者的话,其实这是个约瑟夫环问题,可以模拟游戏过程推出数学公式解:

  • 问题描述:n个人(编号0~(n-1)),从0开始报数,报到(m-1)的退出,剩下的人继续从0开始报数。求胜利者的编号。
  • 我们知道第一个人(编号一定是m%n-1) 出列之后,剩下的n-1个人组成了一个新的约瑟夫环(以编号为k=m%n的人开始):
  • k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2并且从k开始报0。

现在我们把他们的编号做一下转换:

k --> 0

k+1 --> 1

k+2 --> 2

...

...

k-2 --> n-2

k-1 --> n-1

变换后就完完全全成为了(n-1)个人报数的子问题,假如我们知道这个子问题的解:

例如x是最终的胜利者,那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗?

变回去的公式很简单,相信大家都可以推出来:x'=(x+k)%n。

令f[i]表示i个人玩游戏报m退出最后胜利者的编号,最后的结果自然是f[n]

递推公式:

f[1]=0;

f[i]= (f[i-1]+ m)%n; (i>1)

代码实现

  • C++
class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if(n < 1 || m < 1){
            return -1;
        }
        int winner = 0;
        for(int i = 2; i <= n; i++){
            winner = (winner + m) % i;
        }
        return winner;
    }
};
  • Python
class Solution:
    def LastRemaining_Solution(self, n, m):
        # write code here
        if n < 1 or m < 1:
            return -1
        winner = 0
        for i in range(2,n+1):
            winner = (winner + m) % i
        return winner

本文分享自微信公众号 - 深度学习技术前沿(gh_a540734f538c),作者:Evans

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-06-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【CVPR2020 Oral】只需一行代码就可提升迁移性能

    这就是我们出的新方法:批量核范数最大化(Batch Nuclear-norm Maximization)。

    深度学习技术前沿公众号博主
  • 【抠图中的注意力机制】HAttMatting---让抠图变得如此简单!

    【导读】图像抠图(Image Matting)是一个无论在工业界或者视觉研究领域都有非常重要价值的研究课题。从2000年开始,在进行图像抠图及相近研究问题的研究...

    深度学习技术前沿公众号博主
  • 【TPAMI2020】目标检测中的不平衡问题:综述论文,34页pdf

    本文介绍了一篇关于目标检测中不平衡的综述论文:Imbalance Problems in Object Detection: A Review (https:/...

    深度学习技术前沿公众号博主
  • 每次都要重新编译?太慢!让跨平台的 MSBuild/dotnet build 的 Target 支持差量编译

    发布于 2018-05-14 07:46 更新于 2018-07...

    walterlv
  • 5929 亲戚

    题目描述 Description 若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。 规...

    attack
  • 39. channel管道 | 厚土Go学习笔记

    channel 是有类型的管道,channel 的操作符是 <- ,可以用来发送或接收值。 ch <- v //赋值给管道,管道接收值 v := <- c...

    李海彬
  • 【蓝桥杯】PREV-37 分巧克力

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 【2020HBU天梯赛训练】7-37 玩转二叉树

    给定一棵二叉树的中序遍历和前序遍历,请你先将树做个镜面反转,再输出反转后的层序遍历的序列。所谓镜面反转,是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相...

    韩旭051
  • RedHat7下PostGIS源码安装

    顺便安装postgresql-devel、libxml2-devel,后边编译安装PostGIS会用到。

    Florian
  • RedHat7下PostGIS源码安装

    顺便安装postgresql-devel、libxml2-devel,后边编译安装PostGIS会用到。

    Florian

扫码关注云+社区

领取腾讯云代金券