欢迎点击「算法与编程之美」↑关注我们!
本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。
问题描述
猴子选大王,让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 团队
微信号:算法与编程之美
温馨提示:点击页面右下角“写留言”发表评论,期待您的参与!期待您的转发!