算法 | 约瑟夫环

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

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

问题描述

猴子选大王，让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 团队

微信号：算法与编程之美

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