约瑟夫环,约瑟夫环数学解法

约瑟夫环（单循环链表）

m个人围成一个圈，指定一个数字n,从第一个人开始报数，每轮报到n的选手出局，由下一个人接着从头开始报，最后一个人是赢家。其中m1，n2。

用一个不带头节点的循环链表来处理，先构成一个有m个节点的单循环链表，然后由n节点开始计数，每计数到n时对应节点从链表中删除，然后再从删除节点的下一个节点又从1开始计数，直到最后一个节点从链表中删除算法结束。

1.创建一个空指针first，这个first暂时不动，只指向第一个加入进来的对象。

2.先创建第一个节点，并用first指向它，同时它的next是它自己，形成一个闭环。同时创建一个currentNode节点指向最后一个节点，为增加其它节点做准备。

3.加入其它节点时，首先将currentNode的next设置为新的节点node，然后把新节点的next指向回没有动的first节点形成闭环，最后将currentNode指向新的节点。

建立一个重要的指针helper，辅助弹出功能

first 当前计数的节点，helper则指向first的上一个节点

first和helper指针同时前移的时候，first数到对应的数字n,helper还是到它的前一个。弹出first后，first前移以为，helper的next指向first，就弹出了对应的那个节点

约瑟夫环的算法原理

约瑟夫环运作如下：

1、一群人围在一起坐成 环状（如：N）

2、从某个编号开始报数（如：K）

3、数到某个数（如：M）的时候，此人出列，下一个人重新报数

4、一直循环，直到所有人出列 ，约瑟夫环结束

关于约瑟夫环的历史

约瑟夫环（Josephus）问题是由古罗马的史学家约瑟夫（Josephus）提出的，他参加并记录了公元66—70年犹太人反抗罗马的起义。约瑟夫作为一个将军，设法守住了裘达伯特城达47天之久，在城市沦陷之后，他和40名死硬的将士在附近的一个洞穴中避难。在那里，这些叛乱者表决说“要投降毋宁死”。于是，约瑟夫建议每个人轮流杀死他旁边的人，而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签，并且，作为洞穴中的两个幸存者之一，他说服了他原先的牺牲品一起投降了罗马。

约瑟夫环问题的具体描述是：设有编号为1，2，……，n的n(n0)个人围成一个圈，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。

【生活处处皆算法】巧用约瑟夫环

约瑟夫环 （约瑟夫问题）是一个数学的应用问题：

已知n个人（以编号1，2，3....n分别表示）围坐在一张圆桌周围。

从编号为k的人开始报数，数到m的那个人出圈；他的下一个人又从1开始报数，数到m的那个人又出圈；依次规律重复下去，直到剩余最后一个胜利者。

例如：有10个人围成一圈进行此游戏，每个人编号为1-10。若规定数到3的人出圈。则游戏过程如下：

(1) 开始报数，第一个数到3的人为3号，则3号出圈

? ? ? ? 1，2，【3】，4，5，6，7，8，9，10

(2) 从4号重新从1开始计数，则接下来数到3的人为6号，6号出圈

? ? ? ? 1，2，【3】，4，5，【6】，7，8，9，10

(3) 从7号重新从1开始计数，则接下来数到3的人为9号，则9号出圈

? ? ? ? 1，2，【3】，4，5，【6】，7，8，【9】，10

(4)? 从10重新从1开始计数，由于10个人称环形结构，则接下来数到3的人为2号，2号出圈

? ? ? ? 1，【2】，【3】，4，5，【6】，7，8，【9】，10

(5) 从4号重新从1开始计数，则接下来数到3的人为7号，7号出圈

? ? ? ? 1，【2】，【3】，4，5，【6】，【7】，8，【9】，10

(6) 从8号重新从1开始计数，则接下来数到3的人为1号，1号出圈

? ? ? ? 【1】，【2】，【3】，4，5，【6】，【7】，8，【9】，10

(7) 从4号重新从1开始计数，则接下来数到3的人为8号，8号出圈

? ? ? ? 【1】，【2】，【3】，4，5，【6】，【7】，【8】，【9】，10

(8) 从10重新从1开始计数，则接下来数到3的人为5号，5号出圈

? ? ? ? 【1】，【2】，【3】，4，【5】，【6】，【7】，【8】，【9】，10

(9) 从10重新从1开始计数，则接下来数到3的人为10，10号出圈

? ? ? ? 【1】，【2】，【3】，4，【5】，【6】，【7】，【8】，【9】，【10】

(10) 最终剩余4号，4号为胜利者

? ? ? ? 用数组求解的基本思想就是用一个数组去标识这n个人的状态，默认全为1，也就是都在圈子内。

? ? ? ? 当数到m的人出圈之后，标识置为0（就是出圈了），同时报数器清0，下一个要从1开始。

? ? ? ? 在每次报数之前要判断他是否在圈子内（也就是他的标识是否为1），如果在圈子里面才会继续报数。定义一个变量记录出圈的人数，出圈? ? ? ? ? ? 的人数等于n-1时，则游戏结束。