首页 > 代码库 > 约瑟夫环的递推方法
约瑟夫环的递推方法
可以这样理解这个方法:
当有n个人的时候,他们的编号依次是0、1、2、3、4、………、n-1。假设最后编号为x(n)的人会留下来。
因为数到m的那个人会出列,那么此轮中编号为(m-1)%n的人会出列,编号为(m+0)%n的人将做为下一轮编号为0的人,此轮编号为(m+i)%n的人将做为下一轮编号为i的人…
因此当有n-1个人的时候,编号为i的人对应着上一轮编号为(m+i)%n的人。假设此轮编号为x(n-1)的人最终会留下来。因为编号为x(n-1)的人肯定对应着上一轮的x(n),所以有x(n)=(m+x(n-1))%n。
有了这个递推公式,那我们就可以一直递推到x(2)=(m+x(1))%2,而x(1)=0。
所以我们可以这么来写这个函数:
j = 0
当有n个人的时候,他们的编号依次是0、1、2、3、4、………、n-1。假设最后编号为x(n)的人会留下来。
因为数到m的那个人会出列,那么此轮中编号为(m-1)%n的人会出列,编号为(m+0)%n的人将做为下一轮编号为0的人,此轮编号为(m+i)%n的人将做为下一轮编号为i的人…
因此当有n-1个人的时候,编号为i的人对应着上一轮编号为(m+i)%n的人。假设此轮编号为x(n-1)的人最终会留下来。因为编号为x(n-1)的人肯定对应着上一轮的x(n),所以有x(n)=(m+x(n-1))%n。
有了这个递推公式,那我们就可以一直递推到x(2)=(m+x(1))%2,而x(1)=0。
所以我们可以这么来写这个函数:
j = 0
for i 从 2 到 n:
j = (m+j)%i
最终第j个人会留下来(如果从1开始编号就是第j+1个人最终会留下来)。
链接:https://www.zhihu.com/question/20065611/answer/78681758
来源:知乎
约瑟夫环的递推方法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。