约瑟夫环python 约瑟夫环

约瑟夫环问题的数学解下午和朋友聊天的时候，有朋友提到了约瑟夫环问题。你和另外 n-1 个人围成一个圈，按 1，2，...，n 依次编号。第一个人从 1 开始报数，数到 k 的人会被杀掉，然后下一个人重新从 1 开始报数。如此往复，直到最后只剩下一个人。问题是，你应该如何选择自己的初始位置，才能保证最后不被杀掉呢？
速度越快的算法当然越好，毕竟这是一个生死攸关的问题。下面你将会看到，我们如何通过一些基本的数学推导最终得到这个问题的递推解。
考虑这样一种相对简单的情况：总共有 5 个人，数到 3 的人被杀掉。那么，死亡过程如下图所示：
经过一番模拟之后，我们已经对约瑟夫环问题有了一个大概的直观理解。下面，尝试使用数学语言来描述这个问题。
哦对了，假如圆圈里只有你自己，那么你肯定就是最后的幸存者，这是一个极其有用的特殊情况。
这些是我们的已知条件：
这个是我们的未知数：
现在考虑一种泛化情形：总共有 n 个人，数到 k 的人被杀掉，其中 n = k 。幸存者的位置为 p n。
显而易见，初始位置为 k 的人将会第一个被杀掉。此时，经过重新排序之后，问题变成了 n-1 个人的情形。幸存者的位置为 p n-1。如果能够找到从 p n-1到 p n的递推关系，那么问题就解决了。
重新排序之后，每个人的位置发生了下面这些变化：
很容易我们能得到这样一个关系式：p n= (p n-1+ k) % n。再加上刚才讨论的特例，只有一个人的情况时，p 1= 1。递推式就已经很明显了。
当然上文只讨论了 n=k 的情形，实际上对于 nk 的情形，刚才所得到的递推式依然适用，我们就不展开讨论了。
既然递推式这么简洁明确，那么编码实现就不用写了吧？

文章插图
约瑟夫环（单循环链表）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）的时候，此人出列，下一个人重新报数
【约瑟夫环python 约瑟夫环】4、一直循环，直到所有人出列，约瑟夫环结束

约瑟夫环python 约瑟夫环

秒懂生活扩展阅读