约瑟夫环问题

在看剑指offer中看到一个问题。面试题45题：圆圈中最后剩下的数字。看书的时候没看懂，随后查找一波，嗯……现在把心得体会写下来。

这个问题很简单，只需要大家了解以下三个点，就行了

1. 新环和旧环。首先看下图（图片来源https://blog.****.net/byn12345/article/details/79487253），10人环表示的是初始的情况，称之为旧环。9人环表示是删除第4个人之后（步长为4），再将环重新由0到8进行排列，这称之为新环。简而言之，一个环删除某一个节点后，在进行从0到n的排列，这个环称为新环，没删这个节点之前的环称为旧环，新环和旧环是相对概念，及10人环相对9人环是旧环，9人环相对10人环是新环，9人环相对8人环是旧环。

 

2.  新环中的任意一个点的编号对应可以转换为旧环中的一个点的编号，转换公式为：  旧环的编号 = （新环的编号+步长）% 旧环的长度。

3. 最后留下来得人，其新环的编号一定为0.

 

 

OKOK，只需要了解上述三点。那么重点来了：

最后一个留下的人的新环的编号一定为0，那么是不是可以通过上述的第二点计算出其对应的旧环的编号，OK，用所计算出其对应的旧环的编号，是不是可以计算出旧环的旧环的对应的编号，依次类推，就能计算出原始环中的对应的编号，是不是很简单。

 

下面举个例子，这个图和上面那个图是对应的，图片来源（https://blog.****.net/byn12345/article/details/79487253）

首先，该题中步长为4。在1人环，也就是最后幸存下来的那个编号。在新环中编号一定为0，因为新环中就你一个，必须为0啊。

再者，根据公式，旧环的编号 = （新环的编号+步长）% 旧环的长度。那么是不是可以计算出2人环中对应的编号。

再者，根据公式，旧环的编号 = （新环的编号+步长）% 旧环的长度。那么是不是可以计算出3人环中对应的编号。

依次类推，最后计算出来得十人环中的编号，就是我们想要的结果啦。简单吧。