高效实现Josephus算法

高效实现Josephus算法2011-04-14Josephus定义：假设N个人编号1－N，围成圈。从1号开始报数，报到M时，此人退出，然后继续从1开始报数，直到所有人退出为止。简单的实现是使用循环单链表，设置一个计数器 count，当count == M ，删除当前节点，并将count重置。

假设M = 9,N = 5;

这里有两处地方可以优化：

1.当M>N时，取M`= M mod N，即M` = 9 % 5 = 4；报数到9与报数到4效果一致，但少遍历一次链表；

2.当M` > N / 2时，可逆向走N - M" + 1步，此时反向走比正向走距离更近，但需要将数据结构设置为循环双链表。

对于M = 9,N = 5，实现优化后流程如下：

---

链表:1 2 3 4 5

N = 5
M` = 9 mod 5 = 4
M` = 4 > N / 2 = 2

反走（5 - 4 + 1） = 2 步，删除节点4，此时起点在节点3;

---

链表:1 2 3 5

N = 4
M` = 9 mod 4 = 1
M" = 1 < N / 2 = 2

正走1步，删除节点5，此时起点在节点3;

---

链表:1 2 3

N = 3
M` = 9 mod 3 = 0
M` = 0 < N / 2 = 1

正走0步，删除节点3，此时起点在节点2;

---

链表:1 2

N = 2
M` = 9 mod 2 = 1
M` = 1 = N / 2 = 1