约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后 [1] 结果+1即为原问题的解。

一、概念

在开始正题之前，还是解释一下约瑟夫环是什么。约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后 [1] 结果+1即为原问题的解。

二、通过数组循环实现

最常规的思路就是通过一个数组，数组中每个元素都是一个人，然后对数组进行循环处理，每当数组中的人数到m时，将其标记为淘汰。直到最后数组中只有一个人未被淘汰。

所以，首先，我们需要一个计算方法，参数中有总数和淘汰数两个参数。

第二步，我们需要一个长度为total的布尔值数组，数组的index就表示了第几个人，元素的true和false表示了这个人是否被淘汰。一开始我们需要将所有人都设置为未被淘汰。

接下来第三步，我们需要三个变数：

·第一个变数记录还剩多少人为被淘汰，这个变数的初始值为总人数；

·第二个变数记录数到了多少，当这个参数等于淘汰数时归零；

·第三个参数记录当时数到了第几个人，当这个参数等于总人数时归零（因为是一个圈，所以最后一个人数完后又轮到第一个人数数）

第四步就开始循环计算了，首先判断剩余的人数是否大于一，如果大于一进入循环，取index，如果这个人未被淘汰，则计数器加一，如果等于keyNumber则淘汰这个人，否则跳过计数继续，当index等于总人数时

最后，计算结束后，数组中只有一个元素为true，而这个就是最后没被淘汰的那个人，现在我们就开开始找到是谁赢得了这次比赛。

我们验证一下结果：

OK，第一种方法成功。

三、通过链表方式实现

最早了解到这种方法是通过马士兵Java教学视频了解到的方法，其实通过这个方式可以让人更好的理解面向对象的思想和双向循环链表。

第一步，我们要抽象出一些对象，在约瑟夫环这个命题中，有这样两个对象：人和环。人具有几个属性：编号，左边的人和右边的人。环具有几个属性和方法：总人数，第一个人，最后一个人，添加人和移除人。

好了，第二步我们就开始实现自己抽象出来的对象，先是People对象：

接下来是Circle对象：

最后，我们开始计算了，先向环里添加人，然后取到第一个人进行处理，处理完第一个之后取到第一人之后的一个人继续处理，最后返回处理完的环。

下面我们来看一下执行结果：

成功，是不是觉得思想上有点绕，但是这是典型的面向对象思想，可以多消化消化。

四、Java自带链表实现（LinkedList）

其实使用Java自带的LinkedList就可以很简单的实现我们要的效果。直接上代码了：

是不是很简单，能够这么简单的基础是因为链表的remove()方法的特殊性，第一轮循环时，index=2的元素就是3，但它找到需要删除的元素后链表size-1，此时index=2指向的是原index=3的元素，也就说index不用变，这样正好满足了我们的需求。

约瑟夫环还有其他的方法可以实现，但是我目前学习到的只有这三种方法实现，如果以后学习到其他的方法实现，再回来进行补充。

原文地址：https://my.oschina.net/jack90john/blog/1791110

作者：珂jack