约瑟夫环

问题描述

已知n个人以编号1,2,3...n分别表示，围坐在一张圆桌周围。从编号为1的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

解题思路

方法一模拟

当nm数据量很小的时候，我们可以用循环链表模拟约瑟夫环的过程。当模拟到人数等于1的时候，输出剩下的人的序号即可。这种方式很好理解，时间复杂度O(mn)

方法二数学推导

为了简化过程我们把这个n个人的序号编号为0,1,2...n-1(这样编号可以简化后续过程)那么最后的人就是序号 + 1,假设当前总人数那么第一个出列的人就是。
方便起见我们假设，那么实际上第一个出列的人就是第个人。第一个人出列之后，我们得到了一个新的序列,当前序列总人数

这个新序列依然从0开始报数，那么第二次每个人报的相应数字与第一次时自己相应的编号对应起来的关系则为：



…

这其实就转换了成了n-1个人的约瑟夫环问题，我们重复上述过程，继续推导n-1个人的约瑟夫环问题。
为了方便，我们把剩下这个n-1个人编号为0,1,2...n-2，那么此时出列的人的编号就是，同样假设 ,那么此时出列的人的编号就是，出列之后得到了一个新的序列

在这个新的序列里面，依然从0开始报数。这样其实就转换成了n-2个人的约瑟夫环问题。
后面继续递推下去，直到只剩一个人便可以得到结果。

根据上述推导，很容易得到

进一步化简公式