在牛客网上做到一道题，是约瑟夫环的变型，所以借此学习一下新知识，并且巩固一下对题目意思的理解，这一篇仅作约瑟夫环问题的解释，下一篇再写题目：
约瑟夫环（Josephus）问题是由古罗马的史学家约瑟夫（Josephus）提出的，他参加并记录了公元66—70年犹太人反抗罗马的起义。约瑟夫作为一个将军，设法守住了裘达伯特城达47天之久，在城市沦陷之后，他和40名死硬的将士在附近的一个洞穴中避难。在那里，这些叛乱者表决说“要投降毋宁死”。于是，约瑟夫建议每个人轮流杀死他旁边的人，而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签，并且，作为洞穴中的两个幸存者之一，他说服了他原先的牺牲品一起投降了罗马。 约瑟夫环问题的具体描述是：设有编号为1，2，……，n的n(n>0)个人围成一个圈，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。
正如文章 Data Structures With JavaScript: Singly-Linked List and Doubly-Linked List 中所言，链表这种数据结构非常像电视节目里的 寻宝游戏 —— 而不是 火车。
面试中可能经常会遇到约瑟夫环问题，逻辑上很简单，就是看怎么实现了，一般而言，最简单最直观的就是利用链表，然后构建一个循环结构，正好是环，最后计算出结果。
昨晚春晚上刘谦的两个魔术表演的都非常 nice，其中第二个魔术就是非常经典的约瑟夫环问题！
约瑟夫环问题（Josephus problem）是一个古老而经典的数学问题。问题的场景通常是有n个人（编号从1到n）站在一个圆形排列的位置上。接下来，从第一个人开始，每隔k个人就删除一个人，然后重新开始数，直到所有人都被删除。问题的目标是确定最后剩下的那个人的编号。
据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。 然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？
今年春晚刘谦的魔术堪称惊艳全场，那么他这个魔术实现的原理是什么呢？今天，就让咱们使用 JS 是实现这个魔术。
所谓迭代，是重复反馈过程的活动，其目的通常是为了接近并到达所需的目标或结果。每一次对过程的重复被称为一次“迭代”，而每一次迭代得到的结果会被用来作为下一次迭代的初始值。
相关代码：https://github.com/taishan1994/golang_data_structure/tree/master
/** * 约瑟夫环问题主要是考虑下标问题，只要解决了下标控制问题，这个题目就不难了 * 在这里我是分成了3中情况： * 1，下标小于剩余人数时：删除当前元素，并将下标后移 * 2.下标大于剩余人数时：用下标对剩余人数取于，删除元素，并下移下标 * 3.下标等于剩余人数或者是剩余人数的倍数的时候：移除最后一个元素，并让下标后移 */
这一篇文章将讲述Redis中的list类型命令，同样也是通过demo来讲述，其他部分这里就不在赘述了。
有时候，队列会有优先级。比如 VIP 用户总是比普通用户服务优先一些，头等舱总比经济舱要好。实现这样一功能需要在原来的队列基础上加上优先级：当 push 操作时，我们可以传入两个参数，第一个为数据，第二个是优先级大小（数字类型），传入的数值越大优先级越高。
队列和栈非常相似。但是使用的是FIFO（First In First Out，先进先出）原则。在尾部添加元素，在顶部移除元素。
在牛客上跑通过了，本着追求机器效率的原则，去leetcode上找到了同样的题，再跑了一遍，发现超时。看了几篇博客并思索许久后打算写这篇博客来探究
约瑟夫环（Josephus Problem）是一个经典的数学问题，涉及一个编号为 1 到 n 的人围成一圈，从第一个人开始报数，报到某个数字 m 的人出列，然后再从下一个人开始报数，如此循环，直到所有人都出列。本篇博客将详细解析约瑟夫环问题，并使用 Python 实现算法。
约瑟夫问题，相信对有一点数学或者信息学竞赛背景的同学应该都不会很陌生，这是数学竞赛中常见的一个考题背景以及数据结构中用循环链表建模的一个代表性应用。而我懵懂地第一次接触到它居然是在一个魔术流程里，那是我小学时候的事了。而当我很多年以后再在数学和计算机的书上看到它时，竟然有一种从心头涌动的兴奋。于是，我决定从多个视角来回顾一番，并从数学模型，数据结构，数学推导，以及用到这个原理的若干魔术几个角度，来共同探讨这一古老又迷人的议题。
题目： 约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号0，1，2，3…n-1分别表示）围坐在一张圆桌周围。从编号为0的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，求最后一个出列的人。
约瑟夫游戏的大意：30个游客同乘一条船，因为严重超载， 加上风浪大作，危险万分。因此船长告诉乘客，只有将全船 一半的旅客投入海中，其余人才能幸免于难。无奈，大家只 得同意这种办法，并议定30 个人围成一圈，由第一个人数起，依次报数，数到第9人，便把他投入大海中，然后再从 他的下一个人数起，数到第9人，再将他投入大海中，如此 循环地进行，直到剩下 15 个游客为止。问：哪些位置是将 被扔下大海的位置？
环形链表，类似于单链表，也是一种链式存储结构，环形链表由单链表演化过来。单链表的最后一个结点的链域指向NULL，而环形链表的建立，不要专门的头结点，让最后一个结点的链域指向链表结点。 简单点说链表首位相连，组成环状数据结构。如下图结构：
题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&
思路： 用链表模拟约瑟夫环，每次要删除的地方应该是当前索引加上要走的步数，由于我们不要转n圈，所以这可以对链表长度取余，1圈内就找到要删除的位置；
1 一个问题的解可以分解为几个子问题的解 2 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样 3 存在递归终止条件
约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
给定一个从 到 排序的整数列表。首先，从左到右，从第一个数字开始，每隔一个数字进行删除，直到列表的末尾。第二步，在剩下的数字中，从右到左，从倒数第一个数字开始，每隔一个数字进行删除，直到列表开头。我们不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。返回长度为 的列表中，最后剩下的数字。
今天呢，阿Q给大家带来一个小故事，那就是著名的约瑟夫问题。公元66年，约瑟夫不情愿地参与领导了犹太同胞反抗罗马统治的起义，后来起义失败，他和一些宁死不降的起义者被困于一个山洞之中。罗马将军韦斯巴芗(Vespasian)派人来劝降，他主张投降，其余的人不答应，并以死相逼。最后，约瑟夫提议，与其死在自己的手上，不如死在彼此的手上。因此他便将游戏规则告知众人：N个人围成一圈，从第一个人开始报数，报到m的人被杀，剩下的人继续从1开始报数，报到m的人继续被杀；如此往复，直到剩下最后一个人。他就是运用这个游戏规则最终活了下来，被后人称为约瑟夫环问题。
约瑟夫环原理运作如下： N个人围在一起坐成环状 从K编号开始报数 数到某个数M的时候，此人出列，下一个人重新报数 一直循环，直到所有人出列，约瑟夫环结束 joselooplink.c（编译环境： Ubuntu18.04 ，Vim） #include <stdio.h> #include <stdlib.h> typedef struct node /*头指针型约瑟夫环*/ { int item; struct node *next;
Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数 到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由
约瑟夫问题是个著名的问题：N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。
约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知 n 个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为 k 的人开始报数，数到 m 的那个人出圈；他的下一个人又从 1 开始报数，数到 m 的那个人又出圈；依此规律重复下去，直到剩余最后一个胜利者。
约瑟夫环问题请参考： Python版本的报数游戏 微课|中学生可以这样学Python（例5.3）：报数游戏 使用Python列表方法模拟约瑟夫环问题 问题描述： 使用约瑟夫环生成伪随机数。 技术
已知 n 个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。. 从编号为 k 的人开始报数，数到 m 的那个人出圈；他的下一个人又从 1 开始报数，数到 m 的那个人又出圈；依此规律重复下去，直到剩余最后一个胜利者。. 例如：有10个人围成一圈进行此游戏，每个人编号为 1-10 。. 若规定数到 3 的人出圈。. 则游戏过程如下。（1）开始报数，第一个数到 3 的人为 3 号，3 号出圈。（2）从4号重新从1开始计数，则接下来数到3的人为6号，6号出圈。（3）按以上的方法依次类推。
约瑟夫环问题是算法中相当经典的一个问题，其问题理解是相当容易的，并且问题描述有非常多的版本，并且约瑟夫环问题还有很多变形，这篇约瑟夫问题的讲解，一定可以带你理解通通！
这是力扣的 933 题，难度为简单，解题方案有很多种，本文讲解我认为最奇妙的一种。
约瑟夫问题 约瑟夫问题 有 n 个囚犯站成一个圆圈，准备处决。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过 k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。 问题是，给定了n和k，一开始要站在什么地方才能避免被处决？ 这个问题是以弗拉维奥·约瑟夫命名的，它是1世纪的一名犹太历史学家。他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约
0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
原文链接： 具体数学-第2课 - WeiYang Bloggodweiyang.com 今天主要讲了关于递推式和求和的一些方法，主要是成套方法。 约瑟夫环推广 上一节课说到，约瑟夫环问题的解是 其
前天提出了一个关于囚犯排队报数，谁能留到最后的问题： 一道囚徒问题 有人看出来，这是“约瑟夫环”问题的改编版，在网上可以搜到原版的问题，和很多种解法。 这里说一下我的解法： 大体思路就是，用一个列表表示所有囚犯，用循环去模拟报数的过程，如果报到奇数，就把当前值从列表中移除。循环一次之后，如果剩下的人超过 1 个，就对剩下的列表再进行循环。如此反复，直到剩下 1 个为止。代码如下： def lucky(n): lst = range(1, n + 1) count = 0 while
https://www.nowcoder.com/practice/41c399fdb6004b31a6cbb047c641ed8a?tab=note
数据结构开讲啦！！！🎈🎈🎈 本专栏包括： 抽象数据类型 线性表及其应用 栈和队列及其应用 串及其应用 数组和广义表 树、图及其应用 存储管理、查找和排序 将从简单的抽象数据类型出发，深入浅出地讲解复数 到第二讲线性表及其应用中会讲解，运动会分数统计，约瑟夫环，集合的并、交和差运算，一元稀疏多项式计算器 到最后一步一步学会利用数据结构和算法知识独立完成校园导航咨询的程序。 希望我们在学习的过程中一起见证彼此的成长。💡💡💡 问题描述 约瑟夫环问题的一种描述是：将编号为1，2，...n的n个人按顺
:编号为1,2…n的n个人按顺时针方向围坐在一张圆桌周围，没人持有一个密码(正整数)。一开始人选一个正整数作为报数上线值m,从第一个人开始按顺时针方向自1报数，报到m时停止报数，报m的那个人出列，将他的密码作为新的m值，从他顺时针方向的下一个人开始重新从1报数，数到m的那个人又出列；如此下去，直至圆桌周围的人全部出列为止。这个游戏的实现只需将每个人的信息作为一个结点，节点中存放每个人的编号和密码，由于要反复做删除操作，所以采用单项循环链表实现较为方便。 算法分析: 采用单向循环链表的数据结构，即将链表的尾元素指针指向链首元素。每个结点除了指针域外，还有两个分别存放每个人的编号和所持有的密码。
从判断一个单链表是否存在循环而扩展衍生的问题，有则称之为有环链表问题，也就是经典的约瑟夫问题，也称为约瑟夫环。
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
在上一篇文章中，我们聊到了约瑟夫问题的定义，以及其用环的数学模型来建模，最后用循环单链表的数据结构解决该问题等内容。这些只是基本内容，当我们有了数学模型把这个问题变成数学问题以后，就可以在数学结构内去研究更多的东西，而不局限于仅仅求出最后那个被杀的人，比如：
## 题目： 设有 n 个人围坐在圆桌周围，现从某个位置 k 上的人开始报数，报数到 m的人就站出来。下一个人，即原来的第 m+1m+1 个位置上的人，又从 11 开始报数，再报数到 mm 的人站出来。依次重复下去，直到全部的人都站出来为止。试设计一个程序求出这 nn 个人的出列顺序。
原文链接： 具体数学-第8课 - WeiYang Bloggodweiyang.com 今天主要讲了取整与递归式的结合，还有取模的相关知识。 例题1 给出下列递归式： 现在不要求你求解，要你证明：
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
实时音视频
对象存储
即时通信 IM
