约瑟夫环

问题:1~n个人围成一圈,从1开始报数,每次数到m这个人就出列,问最后剩下的是几号?

做法:递归。

假设剩下的是f(n)号,那么要找f(n)与f(n-1)等的关系,又因为这个游戏是过程式的,可以发现:n个人,出列一个之后,就是n-1个人,我们把编号改一下的话,就f(n-1)这个问题完全一样了:

1  2  3 ...  (m)  m+1  m+2  ...  n
...              (  )      1        2   .....

这个n-1的问题里面, 每个编号都是原来编号 + m,再mod n。所以,要求的那个人的编号也是这个:

f(n) = (f(n-1) + m)%n

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 第n个出列 ? ---> 0(**) 从上面可以总结规律: 1. f(*) = (f(**)+m)%n n指当前未...
    贫僧吃猪蹄阅读 4,365评论 0 0
  • 参考文章 约瑟夫环之二(用递归的思想解决Josephus问题) 解释 解法 初始情况: 0, 1, 2 ........
    Mjolnir1107阅读 4,603评论 0 1
  • 百度百科: 约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆...
    KPort阅读 9,316评论 0 4
  • 复习一下关于约瑟夫环的实现原理: 如果用C来写的话,也会有许多的方法,比如1:采用链表(双向链表)2:递归3:队列...
    碧影江白阅读 6,936评论 0 3
  • 好久没有看有关算法的问题了,今天废了不少劲,再感叹一句:要想学好算法就要常练习,没什么捷径可走。废话不多说,如下:...
    时间已静止阅读 11,799评论 0 11

友情链接更多精彩内容