约瑟夫环-递推公式的个人理解

对应力扣原题

简述一下题目:

N个人围成一圈,编号为1到n。第一个人从1开始报数,报m的失败出局,下一个人接着从1开始报。如此反复,最后剩下一个即为胜利者,求最后的胜利者。

说一下我自己理解的推出答案的方法:

我们知道,在最终游戏结束的时候,有且只有一个胜利者。

假设这些人就是从1到n排成一队,【1,2,3,...,n】,最终的胜利者隐藏其中,位置未知。

我们实际要求的是他在这n个人的队伍中的位置(下标,假设从0开始)。因为有了位置就知道他的编号了。

我们先按照题目要求开始游戏,

当第一轮完成报数,下标为m-1(对应队伍第m个人)的人失败出局,队伍从下标m开始排,排在m之前的人则自动按顺序排到队伍末尾,队伍剩余n-1个人,变成【m+1,m+2,...,n,1,2,...,m-1】 (注意游戏开始前下标和编号的对应关系,下标+1=编号

翻译一下上述过程:

实际上就是队伍整体向前移动m个位置,然后让排在队伍最后的人出局:

移动一次:【2,3,...,n,1】

移动两次:【3,4,...,n,1,2】

...

移动m次:【m+1,m+2,...,n,1,2,...,m】

最后一个人出局,此时队伍为:【m+1,m+2,...,n,1,2,...,m-1】

至此完成一轮游戏。

现在剩余的n-1个人开始下一轮,按照规则,队伍继续整体向前移动m个位置,让排在队伍最后的人出局...后面每一轮都是如此。

其实在开始下一轮之前,这n-1个人在队伍中的下标加上m就是他在上一轮中的下标,比如第一个人(编号为m+1)现在下标为0,上一轮时他的下标为m(编号为m+1,也是他的起始编号)。

啰嗦这么多,就一句话:每一轮开始前,剩余成员的下标加上m就是他在上一轮中的下标(至于编号,先不考虑他~)

上述结论对于n=i,∀i∈[1,n]成立。

最终游戏在剩余一个人时结束,最终的胜利者就是这个仅剩的人,不管他的编号是多少,我们知道,此时他的下标是0

f(n,m)表示我们要求的胜利者的下标,则f(1,m) = 0。

那么根据上边的结论,上一轮(n=2时)他的编号就是0+m,写成式子就是f(2,m) = f(1,m) + m,当然要考虑边界问题,n=2时一共两个人,下标只能是0和1,所以要将n=1时的下标f(1,m)加m模2,即:

f(2,m) = (f(1,m) + m)%2

n=3时呢?一共三个人,下标只能是0、1、2,所以要对n=2时的下标f(2,m)加m模3

f(3,m) = (f(2,m) + m)%3

...

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

至此,递推公式得出,代码略...

注意,最终求出的f(n,m)最终的游戏胜利者在n个人时的下标,如果要求编号,直接取原始队列对应下标的值即可。

现在给出一个变种问题,比如我要在最开始指定一个k,从编号为k的人开始报数,相信你也能很快知道怎么解决:

只需要重新安排一下原始队列,让编号为k的人排在队伍开头即可。

写代码更简单,直接将求得的下标f(n,m)加上k就好啦。

相关推荐

  1. -个人理解

    2024-03-27 05:34:03       21 阅读
  2. 问题

    2024-03-27 05:34:03       35 阅读
  3. 问题解决

    2024-03-27 05:34:03       37 阅读
  4. C#实现算法

    2024-03-27 05:34:03       26 阅读
  5. Python 问题

    2024-03-27 05:34:03       14 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-03-27 05:34:03       18 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2024-03-27 05:34:03       19 阅读
  3. 【Python教程】压缩PDF文件大小

    2024-03-27 05:34:03       19 阅读
  4. 通过文章id递归查询所有评论(xml)

    2024-03-27 05:34:03       20 阅读

热门阅读

  1. 计算机网络(04)

    2024-03-27 05:34:03       22 阅读
  2. C# get set 访问器

    2024-03-27 05:34:03       18 阅读
  3. 智能媒体api调用

    2024-03-27 05:34:03       19 阅读
  4. C#语言规范及特殊用法笔记

    2024-03-27 05:34:03       20 阅读
  5. Python中类(class)的使用方法

    2024-03-27 05:34:03       18 阅读
  6. React Native获取及监听网络状态

    2024-03-27 05:34:03       18 阅读
  7. docker 安装 kibana

    2024-03-27 05:34:03       21 阅读
  8. python项目练习——4.手写数字识别

    2024-03-27 05:34:03       22 阅读
  9. eclipse启动报错

    2024-03-27 05:34:03       20 阅读