对应力扣原题
简述一下题目:
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就好啦。