求解报数游戏（约瑟夫环）的六种方法原理与Python实现源码

问题描述：

有n个人围成一圈，按顺时针顺序编号，从第一个人开始从1到k（例如k=3）报数，报到k的人退出圈子，圈子缩小，从下一个人继续游戏从1到k报数，问最后留下的一个人的编号是什么。

下图演示了n=8和k=3的游戏过程，右上角的箭头表示顺时针报数，同心圆从外向内表示人数越来越少、圈越来越小，圆上的数字表示人的编号，斜线表示当前编号的人出圈，浅色背景表示下一个开始报数的人。最内圈深色背景的数字7表示最后剩下的一个人的编号。

下面函数func1()的思路是使用列表来模拟环，每次第一个人报数之后如果不是k就移动到列表尾部，否则就出圈不再回到列表中。由于列表在删除和插入元素时自动收缩和扩展内存的特点导致大量元素移动，这些开销会影响效率。

下面函数func2()的思路是使用标准库itertools中的cycle类把列表转换为环，避免了频繁的元素移动，但每次有人出圈时的切片和列表连接操作开销也很大，效率提升不明显。

下面函数func3()的思路是使用求余运算来模拟环，同时直接定位要出圈的人，减少了大量元素移动且避免了列表连接操作，效率提升非常明显。

下面代码使用面向对象程序设计自定义了循环链表来模拟环，使用节点删除操作来避免元素移动带来的开销，但循环链表的节点遍历操作耗时比列表下标计算要大。

下面的代码用于测试上面的6种方法的功能和性能。

运行结果为：