找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

算法 | 约瑟夫环

admin 2019-7-5 08:14 132人围观 C++相关

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

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

问题描述

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


 


微信号:算法与编程之美         



长按识别二维码关注我们!

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




----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:算法与编程之美,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

yafeilinux和他的朋友们微信公众号二维码

微信公众号

专注于Qt嵌入式Linux开发等。扫一扫立即关注。

Qt开源社区官方QQ群二维码

QQ交流群

欢迎加入QQ群大家庭,一起讨论学习!

我有话说......


第二期送书活动开始!
请关注微信公众号:yafeilinux和他的朋友们,查看最新一期推文。 我知道了