算法 | 约瑟夫环

欢迎点击「算法与编程之美」↑关注我们!

本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。

问题描述

猴子选大王,让N只候选猴子围成一圈,从某位置起顺序编号为1~N号。从第1号开始报数,每轮从1报到3,凡报到3的猴子即退出圈子,接着又从紧邻的下一只猴子开始同样的报数。如此不断循环,最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王?

问题分析

根据题目我们可以看出这道题的最大难点是将N只猴子围成一个圈,其次是将报到3的猴子退出然后更新列表。

解决方案

解题思路:我们首先将N只猴子从1-N进行编号存到列表L里面,既然有N只猴子那么就要进行N-1次报数最后剩余一只猴子,接着我们来解决环问题,我们将猴子由1到N编号对应的索引是由0到N-1。

第一次报数由编号为1的猴子开始往后数3次编号为3索引为2的猴子退出,我们将索引为2的猴子从列表L中删除,之后更新列表编号在3之后的猴子的索引全部减1;

第二次报数由编号为4的猴子依次往后报数,编号为6索引为4猴子退出,之后再次更新列表同理编号在6之后的猴子的索引全部减1;

到这里我们还是没有较多的头绪,那么我们再往后推两次。

第三次报数编号为9索引为6的猴子退出,编号为10的猴子索引再次减1;

第四次报数由编号为10的猴子开始,但是在列表中10号猴子的后面没有猴子可以继续数数,到这里我们不妨思考一下如果列表尾部接着列表的头部,那么退出的将会是编号为2索引为1的猴子,那么我们要怎么实现呢?我们不妨将第10只猴子的索引值加上3再对列表的长度求余数再减去1,发现正好是编号为2索引为1的猴子。

由此我们对以上数据进行分析可以得到这样一个公式:首先设置一个变量x值为0,然后推出公式x=(x+3)%len(L)-1。经过N-1次遍历最后输出L[0]。下面是代码图:

总结

通过一周的学习又增加了自己的知识储备,在解题的过程中需要不断的思索,算法我现在对他的定义是一种解题的步骤——思路和公式。也许看书、看视频我们会觉得算法不就如此吗?动手才知道那是既带给我困惑又带来兴奋的一门知识。

where2go 团队


微信号:算法与编程之美

温馨提示:点击页面右下角“写留言”发表评论,期待您的参与!期待您的转发!

本文分享自微信公众号 - 算法与编程之美(algo_coding)

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

原始发表时间:2019-07-05

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏达达前端

第35节:Java面向对象中的多线程

在Java面向对象中的多线程中,要理解多线程的知识点,首先要掌握什么是进程,什么是线程?为什么有多线程呢?多线程存在的意义有什么什么呢?线程的创建方式又有哪些?...

15140
来自专栏Vegout

final关键字详解

final修饰的类不能被继承,修饰的方法不能被重写,修饰的变量不能被二次赋值,总之,final就是最终的意思,保证了不变性。除了对不变性的保障,对有序性fina...

13020
来自专栏达达前端

第37节:多线程安全问题

创建线程的方法 继承类Thread并重写run(),run()称为线程体;用这种方法定义的类不能再继承其他类。

7840
来自专栏牛客网

字节跳动2020(游戏服务端研发工程师)笔试

去给大佬们当分母系列。不知道游戏服务端工程师是干啥的。求职意向不在此。之所以参加是想看看字节跳动的笔试是个什么样的。以下给出问题,答案的话,自己找,也是学习的过...

29040
来自专栏达达前端

第36节:Java当中的线程

Java当中的线程,进程和线程的关系?进程就是线程吗?不是的。线程的运行,和方法。

7840
来自专栏Vegout

算法——union-find

今天跟大家分享一个算法,如题union-find。这个算法要解决的就是一个动态连通性问题,什么是动态连通性呢?首先是连通性,给出两个对象,可以判断两个对象是否相...

11430
来自专栏达达前端

第33节:Java面向对象中的异常

Exception:RuntimeException为空指针异常,数组下标越界异常,算数异常,类型转换异常等,IO异常(IOException),SQL异常(S...

10120
来自专栏流川疯编写程序的艺术

机器视觉3——电磁波

通过以上图我们可以看出,正弦波上的点和圆上的点相对应,我们假想圆是一个时钟的表盘,那么指针每走的一步都会相应体现在正弦波的前进起伏上。

8450
来自专栏Vegout

二分查找

数据是海量的,从中提取有价值的信息是必要的,提取的过程也就是查找的过程。简单粗暴就是顺序查找,任何东西我一个一个来,不管你是有序无序,对我来说都一样。跟今天咱们...

10530
来自专栏达达前端

第32节:Java中-构造函数,静态方法,继承,封装,多态,包

在现实世界当中,继承就是儿子得到老子的东西,在面向对象的世界当中,继承就是一个类得到了另一个类当中的成员变量和成员方法

12260

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励