(约瑟夫问题)N个人围成一圈,从第一个开始报数,第k个退出,再从1开始报数,依次循环,直到最后一个人

1．约瑟夫问题：n个人围成一圈，从第s（s<n）个人开始报数，数到m的人出圈；再由下一个人开始报数，数到m的人出圈；……。

输出依次出圈的人的编号。

m的值预先选定，n由键盘输入。

分析：我们将这n个人组成一个链表，表中每一个元素为一记录类型，第一个域变量lvalue为人的编号，第二个域变量next指向下一个人，这样链接下去构成一个环形链。

然后由lvalue值为s的记录开始，对链中的元素逐一记数，数到第m个记录时，将它删去，即把第（m-1）个记录的指针改成指向第（m+1）个记录，然后从第（m+1）个向下记数，这样重复进行下去，直到剩下一个记录。

出列的人也组成一条链，r是其首指针，只要打印这条链就得到结果。

源程序如下：#include <iostream.h>#include <stdio.h>#include <stdlib.h> // 使用malloc()函数的库函数#include <malloc.h>typedef struct linknode{int lvalue;struct linknode *next;} point;int main(){int n,m,s,node,i;point *p,*q,*r;cout<<"Input total number, initial number and distance: ";cin>>n>>s>>m;p=(point *)malloc(sizeof(point));q=p;for(i=1; i<=n-1; i++){ // 生成链表q->lvalue=s;s=s%n+1;q->next=(point *)malloc(sizeof(point));q=q->next;}q->lvalue=s;q->next=p; // 生成循环链表node=n;r=(point *)malloc(sizeof(point));q=r;while(node>1){if(m==1){r->next=p;node=1;}else{for(i=1; i<=m-2; i++)p=p->next;q->next=p->next; // 将数到m的人出圈，链到出列人的链表中q=q->next;p->next=p->next->next;p=p->next;node--;}}for(i=1; i<=n-1; i++){ // 依次打印出列人的序号r=r->next;cout<<"The"<<i<<"th person is number:"<<r->lvalue<<endl;}if(m==1)cout<<"The last one is number:"<<r->next->lvalue<<endl;elsecout<<"The last one is number:"<<p->lvalue<<endl;return 1;}2．设单链表中存放着n个字符，试设计算法判断字符串是否中心对称。

约瑟夫效应的原理与应用简介约瑟夫效应（Josephus problem）是一个著名的数学问题和游戏，也被称为约瑟夫斯问题。

问题描述如下：假设有n个人围成一圈，从某个人开始报数，报到m的人出列，接着从出列的下一个人开始重新报数，直到最后只剩下一个人为止。

问题的关键是确定最后剩下的这个人在最初的位置。

约瑟夫问题的解法有很多，包括数学推导和编程算法等。

原理解析约瑟夫效应的原理可以用数学计算来解释。

假设有n个人围成一圈，从第一个人开始报数，每报到m的人出列。

假设第一个出列的人的位置是k，我们可以推导出第二个出列的人的位置是(k+m-1)%n，第三个出列的人的位置是(k+m-1+m-1)%n，以此类推。

最后剩下的那个人的位置就是从1开始数的序号。

应用场景虽然约瑟夫问题看似只是个数学问题或游戏，但实际上它在很多实际场景中都有应用。

下面列举几个常见的应用场景：1.编程算法约瑟夫问题可以用于编程算法的设计与困难的解决。

例如，给定一个数组，要求按照某种规则删除元素，直到最后只剩下一个元素。

这个问题可以通过约瑟夫问题的解决思路来解决。

2.网络协议在一些分布式系统中，节点之间需要按照某种规则进行通信。

约瑟夫问题的解决思路可以用于设计节点间的通信协议，确保每个节点都能按照规则顺序接收到消息。

3.人员调度在一些团队或组织中，需要对人员进行轮换、调度或排班工作。

约瑟夫问题的解决思路可以用于确定轮换、调度或排班的规则，确保公平公正。

编程实现约瑟夫问题的解决方法有很多，其中一种常见的实现方式是使用循环链表。

具体的算法如下：```python def josephus(n, m): # 创建循环链表 circle = [i for i in range(1, n+1)]idx = 0while len(circle) > 1:# 找到要删除的位置idx = (idx + m - 1) % len(circle)# 删除该位置上的元素del circle[idx]return circle[0]测试n = 10 m = 3 result = josephus(n, m) print(。

实验一：约瑟夫问题问题描述：用数组和链表存储方式实现约瑟夫问题。

约瑟夫问题：n个人围成一个圆圈，首先第1个人从1开始一个人一个人顺时针报数，报到第m个人，令其出列。

然后再从下一个人开始，从1顺时针报数，报到第m个人，再令其出列，…，如此下去，直到圆圈中只剩一个人为止。

此人即为优胜者。

基本要求：用顺序存储和链式存储方式实现。

试验报告内容：1．问题描述：设有n个人围坐在圆桌周围，现从某个位置m（1≤m≤n）上的人开始报数，报数到k 的人就站出来。

下一个人，即原来的第k+1个位置上的人，又从1开始报数，再报数到k的人站出来。

依此重复下去，直到全部的人都站出来为止。

2. 算法描述：可以先建一个单向循环链表；而整个“约瑟夫环”问题的过程，最终是把这个链表删空为止。

但在删时不能顺着删，而是按该问题的方案来删。

3.源程序#include <stdio.h>#include <stdlib.h>#define MAX_NODE_NUM 100#define TRUE 1U#define FALSE 0Utypedef struct NodeType{int id; /* 编号 */int cipher; /* 密码 */struct NodeType *next;} NodeType;/* 创建单向循环链表 */static void CreaList(NodeType **, const int);/* 运行 "约瑟夫环 "问题 */static void StatGame(NodeType **, int);/* 打印循环链表 */static void PrntList(const NodeType *);/* 得到一个结点 */static NodeType *GetNode(const int, const int);/* 测试链表是否为空, 空为TRUE，非空为FALSE */static unsigned EmptyList(const NodeType *);int main(void){int n, m;NodeType *pHead = NULL;while (1){printf( "请输入人数n（最多%d个）: ", MAX_NODE_NUM); scanf( "%d ", &n);printf( "和初始密码m: ");scanf( "%d ", &m);if (n > MAX_NODE_NUM){printf( "人数太多，请重新输入！\n ");continue;}elsebreak;}CreaList(&pHead, n);printf( "\n------------ 循环链表原始打印 -------------\n "); PrntList(pHead);printf( "\n-------------- 出队情况打印 ---------------\n "); StatGame(&pHead, m);printf( "\n\ "约瑟夫环\ "问题完成!\n ");return 0;}static void CreaList(NodeType **ppHead, const int n){int i, iCipher;NodeType *pNew, *pCur;for (i = 1; i <= n; i++){printf( "输入第%d个人的密码: ", i);scanf( "%d ", &iCipher);pNew = GetNode(i, iCipher);if (*ppHead == NULL){*ppHead = pCur = pNew;pCur-> next = *ppHead;}else{pNew-> next = pCur-> next;pCur-> next = pNew;pCur = pNew;}}printf( "完成单向循环链表的创建!\n ");}static void StatGame(NodeType **ppHead, int iCipher){int iCounter, iFlag = 1;NodeType *pPrv, *pCur, *pDel;pPrv = pCur = *ppHead;/* 将pPrv初始为指向尾结点，为删除作好准备 */while (pPrv-> next != *ppHead)pPrv = pPrv-> next;while (iFlag) /* 开始搞了! */{/* 这里是记数，无非是移动iCipher-1趟指针! */for (iCounter = 1; iCounter < iCipher; iCounter++) {pPrv = pCur;pCur = pCur-> next;}if (pPrv == pCur) /* 是否为最后一个结点了 */iFlag = 0;pDel = pCur; /* 删除pCur指向的结点，即有人出列 */pPrv-> next = pCur-> next;pCur = pCur-> next;iCipher = pDel-> cipher;printf( "第%d个人出列, 密码: %d\n ",pDel-> id, /* 这个编号标识出列的顺序 */pDel-> cipher);free(pDel);}*ppHead = NULL; /* 没人了！为了安全就给个空值 */}static void PrntList(const NodeType *pHead){const NodeType *pCur = pHead;if (EmptyList(pHead))return;do{printf( "第%d个人, 密码: %d\n ", pCur-> id,pCur-> cipher); pCur = pCur-> next;} while (pCur != pHead);}static NodeType *GetNode(const int iId, const int iCipher){NodeType *pNew;pNew = (NodeType *)malloc(sizeof(NodeType));if (!pNew){printf( "Error, the memory is not enough!\n ");exit(-1);}pNew-> id = iId;pNew-> cipher = iCipher;pNew-> next = NULL;return pNew;}static unsigned EmptyList(const NodeType *pHead){if (!pHead){printf( "The list is empty!\n ");return TRUE;}return FALSE;}4.实验测试数据（要求有多组）：第一组测试结果人数n为7, 初始密码m为20第1个人, 密码: 3第2个人, 密码: 1第3个人, 密码: 7第4个人, 密码: 2第5个人, 密码: 4第6个人, 密码: 8第7个人, 密码: 4-------------- 出队情况打印 ---------------第6个人出列, 密码: 8第1个人出列, 密码: 3第4个人出列, 密码: 2第7个人出列, 密码: 4第2个人出列, 密码: 1第3个人出列, 密码: 7第5个人出列, 密码: 4第二组测试结果人数n为8, 初始密码m为15第1个人, 密码: 5第2个人, 密码: 4第3个人, 密码: 3第4个人, 密码: 2第5个人, 密码: 9第6个人, 密码: 1第7个人, 密码: 7第8个人, 密码: 8-------------- 出队情况打印 ---------------第7个人出列, 密码: 7第6个人出列, 密码: 1第8个人出列, 密码: 8第3个人出列, 密码: 3第1个人出列, 密码: 5第4个人出列, 密码: 2第2个人出列, 密码: 4第5个人出列, 密码: 95.总结：1. 通过本次上机实践,对链表存储结构有了更深的理解和把握.2. 通过本次上机实践,应用链表的知识解决和分析问题的能力有了新的提高.3. 通过上机实践,掌握了用高级语言实现算法的基本步骤和方法.（最前面加班级、学号、姓名）。

实验一：约瑟夫问题求解一、问题描述1、实验题目：约瑟夫（Josephus）问题的一种描述是：编号为1，2，……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。

一开始任选一个正整数作为报数上线值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。

报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。

2、基本要求：试设计一个程序，按出列顺序印出个人编号。

3、测试数据：m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4。

ｍ的初值为6，正确的出列顺序应为：6，1，4，7，2，3，5。

二、需求分析１、本程序用来求出含有密码的约瑟夫问题，可以输出所有人的出列顺序。

2 、程序运行后显示提示信息，提示用户输入一圈的人数n，接着输入每个人的密码，最后提示输入初始密码。

3、用户输入完毕后，程序自动输出运算结果。

三、概要设计1、设计思路n个人围成一圈，每个人的手中都有一个密码，这个密码决定了下一次报数的上限。

游戏规则：①给定一个初始密码②循环报数，报到密码值的人要出列，依次类推，直到所有的人都出列本程序要求输入的内容：n个人的密码及初始密码；本程序要求输出的内容：n个人出列的顺序。

2、数据结构为了实现上述功能，可以采用链式存储结构。

采用链式存储结构，定义了一个存储个人信息的结构体，及两个自定义函数，分别用于创建链表和约瑟夫出列操作。

①链表抽象数据类型的定义： #define SLNODE struct slnodeADT SLNODE{数据对象：D={ i a |i a ∈SLNODE, i=1,2,3.... }数据关系：R=φ}ADT SLNODE;②自定义函数:void create_SLnode(SLNODE *p,int n)//创建队列{ 创建链表，为N 个人分配密码 }void Josef(SLNODE *p,int n)//进行约瑟夫操作{输入初始密码m;for(){ 将出列的结点删除，并输出出列序号；}}③本程序的保护模块：结构体模块主程序模块自定义函数模块调用关系：3、程序设计主要算法的流程图：create_SLnode( )算法流程图Josef( )算法流程图四、详细设计1、元素类型、结点的类型及指针#define SLNODE struct slnodeSLNODE//每个结点的结构体{int num;//num代表序号int code;//code代表密码SLNODE *next;};2、自定义函数：void create_SLnode(SLNODE *p,int n)//创建队列，并将其尾指针指向第一个序号{SLNODE *r,*s;s=p;int i,m;cout<<"请给这"<<n<<"个人分配密码："<<endl;for(i=0;i<n;i++){cout<<"请给第"<<i+1<<"个人输入密码："<<endl;cin>>m;r=(SLNODE *)malloc(sizeof(SLNODE));r->code=m;r->num=i+1;r->next=s->next;s->next=r;s=s->next;}p=p->next;s->next=p;}void Josef(SLNODE *p,int n)//进行约瑟夫操作{p=p->next;int m;int i,j;SLNODE *r;cout<<"请输入初始密码："<<endl;cin>>m;cout<<"依次出列的序号为:"<<endl;for(i=0;i<n-1;i++)p=p->next;for(i=0;i<n-2;i++){for(j=0;j<m-1;j++)p=p->next;cout<<(p->next)->num<<endl;m=(p->next)->code;r=p->next;p->next=r->next;}if(m%2==0)cout<<p->num<<endl<<(p->next)->num<<endl;elsecout<<(p->next)->num<<endl<<p->num<<endl;}3、主函数：int main(){SLNODE *p;int n;cout<<"请输入一圈的人数："<<endl;cin>>n;p=(SLNODE *)malloc(sizeof(SLNODE));p->next=NULL;create_SLnode(p,n);Josef(p,n);return 0;}4、函数的调用关系：主函数main()调用自定义函数void create_SLnode(SLNODE *p,int n);/*创建队列*/与void Josef(SLNODE *p,int n);/*进行约瑟夫操作*/。

这是17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。

问怎样排法，才能使每次投入大海的都是非教徒。

*问题分析与算法设计约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。

这里给出一种实现方法。

题目中30个人围成一圈，因而启发我们用一个循环的链来表示。

可以使用结构数组来构成一个循环链。

结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被扔下海的标记，为1表示还在船上。

从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。

这样循环计数直到有15个人被扔下海为止。

[编辑本段] 约瑟夫问题的一般形式：约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。

例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。

最后剩下1号。

假定在圈子里前K个为好人，后K个为坏人，你的任务是确定这样的最少M，使得所有的坏人在第一个好人之前被杀掉。

C++代码示例: #i n c l u d e<i o s t r e a m>u s i n g n a m e s p a c e s t d;v o i d m a i n()i n t n,m,a[101],k,i,j,n um; //计数器是从1开始的,所以100个人用101 c o u t<<"请输入参加游戏的玩家人数(不超过100人):";c i n>>n;c o u t<<"----------------------------------------"<<e nd l;i f(n>100){c o u t<<"玩家太多,请重新登陆此程序!"<<e nd l;r e t u r n;}c o u t<<"输入游戏中要玩的数字:";c i n>>m;c o u t<<"----------------------------------------"<<e nd l;f o r(i=1;i<=n;i++){ a【i】=1;//注意百度百科里不让使用ASCII里的方括号，这里是中文字符集里的方括号，}j=0;k=0;f o r(i=1;i<=n+1;i++){i f(a【i】==1){j=j+a【i】;i f(j==m)j=0;a【i】=0;k++;}i f(k==n){n u m=i;b r e a k;}}i f(i==n+1)i=0;}c o u t<<"最后获胜的玩家是第"<<n u m<<"号玩家!"<<e nd l;c o u t<<"----------------------------------------"<<e nd l;}写完密码约瑟夫就想到原来看到约瑟夫问题的一个数学解法很巧妙很简单不过只能推出最后一个出列的人无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。

约瑟夫环问题的简单解法（数学公式法）关于约瑟夫环问题，无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。

我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。

因此如果要追求效率，就要打破常规，实施一点数学策略。

为了讨论方便，先把问题稍微改变一下，并不影响原意：问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。

求胜利者的编号。

我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:k k+1 k+2 … n-2, n-1, 0, 1, 2, … k-2并且从k开始报0。

现在我们把他们的编号做一下转换：k-2 – n-2k-1 – n-1解x’ —- 解为x注意x’就是最终的解变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x’=(x+k)%n如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。

(n-2)个人的解呢？当然是先求(n-3)的情况—- 这显然就是一个倒推问题！下面举例说明：假设现在是6个人（编号从0到5）报数，报到（2-1）的退出，即 m=2。

那么第一次编号为1的人退出圈子，从他之后的人开始算起，序列变为2,3,4,5,0，即问题变成了这5个人报数的问题，将序号做一下转换：现在假设x为0,1,2,3,4的解，x’设为那么原问题的解（这里注意，2,3,4,5,0的解就是0,1,2,3,4,5的解，因为1出去了，结果还是一个），根据观察发现，x与x’关系为x’=(x+m)%n，因此只要求出x，就可以求x’。

约瑟夫环问题的两种解法（详解）约瑟夫环问题的两种解法（详解）题⽬：Josephus有过的故事：39 个犹太⼈与Josephus及他的朋友躲到⼀个洞中，39个犹太⼈决定宁愿死也不要被敌⼈抓。

于是决定了⾃杀⽅式，41个⼈排成⼀个圆圈，由第1个⼈开始报数，每报数到第3⼈该⼈就必须⾃杀。

然后下⼀个重新报数，直到所有⼈都⾃杀⾝亡为⽌。

然⽽Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与⾃⼰安排在第16个与第31个位置，于是逃过了这场死亡游戏。

对于这个题⽬⼤概两种解法：⼀、使⽤循环链表模拟全过程⼆、公式法我们假设这41个⼈编号是从0开始，从1开始报数，第3个⼈⾃杀。

1、最开始我们有这么多⼈：[ 0 1 2 3 4 5 ... 37 38 39 40 ]2、第⼀次⾃杀，则是(3-1)%41=2 这个⼈⾃杀，则剩下：[ 0 1 3 4 5 ... 37 38 39 40 ]3、然后就是从编号为3%41=3的⼈开始从1报数，那么3号就相当于头，既然是头为什么不把它置为0，这样从它开始就⼜是与第1,2步⼀样的步骤了，只是⼈数少了⼀个，这样不就是递归了就可以得到递归公式。

想法有了就开始做：4、把第2步中剩下的⼈编号减去3映射为：[ -3 -2 0 1 2 ... 34 35 36 37 ]5、出现负数了，这样不利于我们计算，既然是环形，37后⾯报数的应该是-3，-2，那么把他们加上⼀个总数（相当于加上360度，得到的还是它）[ 38 39 0 1 2 3 ... 34 35 36 37 ]6、这样就是⼀个总数为40个⼈，报数到3杀⼀个⼈的游戏。

这次⾃杀的是第5步中的(3-1)%40=2号，但是我们想要的是第2步中的编号（也就是最初的编号）那最初的是多少？对应回去是5；这个5是如何得到的呢？是（2+3)%41得到的。

⼤家可以把第5步中所有元素对应到第2步都是正确的。

7、接下来是[ 35 36 37 38 0 1 2... 31 32 33 34 ]⾃杀的是(3-1)%39=2，先对应到第5步中是(2+3)%40=5，对应到第2步是(5+3)%41=8。

约瑟夫环问题的三种解法约瑟夫问题是个著名的问题：N个⼈围成⼀圈，第⼀个⼈从1开始报数，报到k的⼈将被杀掉，接着下⼀个⼈⼜从1开始报，直到最后剩下⼀个，求最后留下的⼈的下标。

题⽬集合解法1：暴⼒可以直接暴⼒求解，时间复杂度为O(nk)解法2：递推设f(n,k)为当n个⼈围成⼀圈时，最后留下的⼈的下标。

对于f(n-1,k)来说，其结果相当于f(n,k)的结果向前移动k\%(n-1)位。

因为对于f(n,k)来说，去掉第⼀轮报的数(k\%n)后，现在就只剩下n-1个数，并且是以(k\%(n-1)+1)作为第⼀个数,即所有数向前移动k\%(n-1)位。

现在的结果就为f(n-1,k)对于f(5,3)来说,其结果为4。

当其去掉第⼀轮报的数后，其向前移动了(3\%4)位，以4为起始，f(4,3)结果为1，对应着f(5,3)的结果4向前移动了3位所以反过来看即为,即为f(n-1,k)的结果向后移动k\%(n-1)位即f(n+1,k)=(f(n,k)+k\%n)\%n (x下标从0开始,因为取模结果为[0,n-1])时间复杂度为O(n)ll josephus2(ll n,ll k){ll pos=0;for(int len=1;len<=n;len++){pos = (pos+k)%len;}return pos+1;}递推代码解法3：如果当前这⼀位⼈没被杀掉，则他可以放在幸存者的末尾，直到幸存者数量为1所以对于下标为i的⼈，如果在他前⾯已经被杀掉了q个⼈，那么他的新的下标为n+q(k-1)+x,(1\leq x <k)如下图所⽰，最后被淘汰的编号⼀定是n*k，所以幸存者最后的编号是n*k我们现在需要从幸存者最后的编号中恢复出最初编号假设幸存者这⼀次的编号为p os_{i}，在他后⾯包括他还有x位幸存者，则[pos_{i-1},pos_{i})间⼀定有x个不能被k整除的数这样才能使在他后⾯包括他还有x位幸存者。

有关经典约瑟夫问题的四种解法 约瑟夫问题是信息学奥赛中的⼀类经典且重要的题型，在平常的测试中屡屡出现。

通常题设可抽象为：⼀开始有n个⼈围成⼀个圈，从 1开始顺时针报数，报出m的⼈被踢出游戏.。

然后下⼀个⼈再从1开始报数，直到只剩下⼀个⼈。

　或者：曾经有个⼈在他⾝边，然⽽现在只剩他⼀个⼈。

Who are you? Who am I? Why am I here?⾛的越来越慢，⼈越来越少，可终于还是只剩⼀个了呢。

他们围成⼀圈，随机了⼀个⼈作为1号，然后逆时针依次编号。

1号开始报数，报到 1，他⾛了；然后2号开始报数，2号报了1，3 号报了2 ，于是3 号也⾛了……每⼀轮都从上⼀次出局的下⼀个⼈开始报数，第i轮从1 报到i，报i的⼈出局。

直到只剩他⼀个⼈。

却早已不记得他⾃⼰是谁。

针对不同的数据范围，可以存在如下⼏种做法：1. O(nm) O(nm)的复杂度适⽤于n,m都在30000以内的情况，此类题型较少，例如“约瑟夫游戏”⼀题，n,m<=30000，由于随着游戏的不断进⾏，需要枚举的⼈数越少，所以复杂度实际低于O(nm)。

算法思路：暴⼒模拟即可。

#include<bits/stdc++.h>using namespace std;int T,N,M; bool v[1000100];void wk(){memset(v,0,sizeof(v));scanf("%d%d",&N,&M);int t=0,num=0,pos=1;while(1){if(v[pos]){++pos;if(pos==N+1) pos=1;continue;}++num;if(num==M){if(t==N-1){printf("%d\n",pos);return;}v[pos]=1,++t,num=0;}++pos;if(pos==N+1) pos=1;}}int main(){scanf("%d",&T);while(T--) wk();return 0;}暴⼒模拟约瑟夫问题2.O(n) O(n)算法已经适⽤于⼤多数约瑟夫问题，让n<=1e7的数据范围可以被轻松解决，考虑以任意⼀⼈为起点，选出第m个⼈后的编号变化，设起始id==0，选出第m个⼈后，id−>(id+m)，再回归到原来的圆形，设i表⽰第i轮游戏，那么整体的公式即为(id+m)%(n−i+1)。

题目：约瑟夫（Joseph）问题的一种描述是：编号为1，2，......，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。

一开始任选一个整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。

报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个开始重新从1报数，如此下去，直至年有人全部出列为止。

试设计一个程序求出出列顺序。

班级：姓名：学号：完成日期：一、需求分析1．本演示程序中，利用单向循环链表存储结构存储约瑟夫环数据（即n个人的编号和密码）。

2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示"提示信息"之后，由用户在键盘上输入演示程序中需要输入的数据，运算结果显示在其后。

3．程序执行的命令包括：1)构造单向循环链表；2）4．测试数据m 的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6（正确的出列顺序为6，1，4，7，2，1，3，5）。

二、概要设计1．单向循环链表的抽象数据类型定义为：ADT List｛数据对象：D=｛ai | ai∈正整数，I=1，2，......，n,n≥0｝数据关系：R1=｛< ai-1，ai > |，ai-1，ai∈D,I=1，2，......，n｝基本操作：Init List(&L)操作结果：构造一个空的线性表L。

List Insert(&L,i,e)初始条件：线性表L已存在，1≤i≤List Length(L)+1.操作结果：在L中第i个位置之前插入新的数据无素e，L长度加1。

List Delete(&L,i,&e)初始条件：线性表L存在非空，1≤i≤List Length(L).操作结果：删除L的第i个元素，并用e返回其值，L长度减1。

2．程序包含四个模块：1）主程序模块：三详细设计typedef struct LNode{int password; //密码int No; //序号struct LNode *next; //下一成员指针}member; //成员结构体typedef int status;#define OVERFLOW -2#define OK 1#define ERROR 0#include <stdio.h>#include <stdlib.h>status CreateList_Circle(member **,int);status DeleteNode(member **);status main(){int n,m;member *head=NULL,*p=NULL; //头指针即首成员地址，遍历指针p printf ("Please enter number of people:\n");scanf ("%d",&n); //总成员数while (n<=0){printf ("n must be positive, please enter again:\n");scanf ("%d",&n);}if(!CreateList_Circle(&head,n)) //创建循环链表，返回头指针head return OVERFLOW;printf ("Please enter initial m:\n");scanf ("%d",&m); //初始mwhile (m<=0){printf ("m must be positive, please enter again:\n");scanf ("%d",&m);}printf ("\nThe order is:\n");p=head;while (n>=2) //寻找出列成员{int i;m=(m%n==0)?n:m%n; //化简m值for (i=1;i<m;i++)p=p->next; //p指向出列成员printf ("%d\n",p->No); //输出出列成员序号m=p->password; //修改mDeleteNode(&p); //删除链表中的出列成员n--; //成员数自减}printf ("%d\n",p->No); //输出最后一个成员序号return OK;}status CreateList_Circle(member **p_head,int n){//此算法创建一个无头结点的循环链表，结点数n,*p_head返回链表头指针即首结点地址int i;member *tail,*p;*p_head=(member *)malloc(sizeof(member));if (!(*p_head)) return OVERFLOW;(*p_head)->No=1; //储存成员一序号printf ("Please enter password of No. 1:\n");scanf ("%d",&(*p_head)->password); //储存成员一密码tail=*p_head;tail->next=NULL;for (i=2;i<n+1;i++){p=(member *)malloc(sizeof(member));if (!p) return OVERFLOW;p->No=i; //储存成员序号printf ("Please enter password of No. %d:\n",i);scanf("%d",&(p->password)); //储存成员密码tail->next=p;tail=p;}tail->next=*p_head;return OK;}status DeleteNode(member **pp){//此算法删除链表中的结点*pp,操作实质是将*pp下一结点复制到*pp后将其free member *temp;(*pp)->password=((*pp)->next)->password;(*pp)->No=((*pp)->next)->No;temp=(*pp)->next;(*pp)->next=(*pp)->next->next;free(temp);return OK;}四、调试分析程序的编写和调试基本正常。

约瑟夫问题约瑟夫问题约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。

例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。

最后剩下1号。

假定在圈子里前K个为好人，后K个为坏人，你的任务是确定这样的最少M，使得所有的坏人在第一个好人之前被杀掉。

举个例子：有64名战士被敌人俘虏了。

敌人命令他们拍成一圆圈，编上号码1，2，3…，64。

敌人把1号杀了，又把3号杀了，他们隔着一个杀一个这样转着圈杀。

最后只剩下一个人，这个人就是约瑟夫斯。

请问约瑟夫斯是多少号？（这就是“约瑟夫斯”问题。

）这个问题解答起来比较简单：敌人从1号开始，隔一个杀一个，第一圈把所有的奇数号码的战士圈杀光了。

剩下的32名战士需要重新编号，而敌人在第二圈杀死的是重新编号的奇数号码。

由于第一圈剩下的全部是偶数号2，4，6，…，64。

把它们全部用2去除，得1，2，3，…，32。

这是第二圈编的号码。

第二圈杀过以后，又把奇数号码都杀掉了，还剩16个人。

如此下去，可以想到最后剩下的必然是64号。

$64=2^6$，它可以连续被2整除6次，是从1到64中能被2整除次数最多的数，因此，最后必然把64 号留下。

如果有65名战士被俘，敌人还是按上述的方法残杀战士，最后还会剩下约瑟夫斯吗？经过计算，很容易得到结论，不是。

因为第一个人被杀后，也就是1号被杀后，第二个被杀的是必然3号。

如果把1号排除在外，那么还剩下的仍是64人，新1号就是3号。

这样原来的2号就变成了新的64 号，所以剩下的必然是2号。

进一步的归类，不难发现如果原来有$2^k$个人，最后剩下的必然$2^k$号；如果原来有$2^k+1$个人，最后剩下2号；如果原来有$2^k+2$个人，最后剩下4号……如果原来有$2^k+m$个人，最后剩下2m号.比如：原来有100人，由于$100=64+36=2^6+36$，所以最后剩下的就是36×2=72号；又如：原来有11 1人，由于$100=64+47=2^6+47$，所以最后剩下的就是47×2=94号传说古代有一批人被蛮族俘虏了，敌人命令他们排成圆圈，编上号码1，2，3，…然后把1号杀了，把3号杀了，总之每隔一个人杀一个人，最后剩下一个人，这个人就是约瑟夫斯。

线性表的操作及其应用一、问题描述线性表、队列是一种常用的数据结构，有顺序和链式两种存储结构，在实际中应用十分广泛，而链表又分为单链表和循环链表，队列又分为链式队列和循环队列。

这些数据结构都可用来解决约瑟夫环问题。

约瑟夫环问题是算法设计中的一个经典问题，是顺序编号的一组n个人围坐一圈，从第1个人按一定方向顺序报数，在报到m时该人出列，然后按相同方法继续报数，直到所有人出列。

设计算法求约瑟夫环中人员的出列顺序。

二、基本要求1、选择合适的存储结构，建立线性表；2、利用顺序存储结构求解约瑟夫环问题；3、利用单链表和循环链表分别求解约瑟夫环问题；4、利用队列求解约瑟夫环问题。

三、测试数据约瑟夫环的测试数据为7，报数为1至3。

四、算法思想由于用到四种不同的存储结构，它们的算法思想依次是：1、首先建立一个顺序表模拟整个约瑟夫环，手动输入顺序表长（即参加约瑟夫循环的人数）和循环的次数和表元素。

用已经输出总人数和顺序表长作比较，作为外层循环条件。

并对每一个输出后的元素重新赋值以为标记。

对于每次循环，首先检查顺序表此次是不是我们设立的标记，如果不是则循环次数加1，当达到要求的循环次数时就将循环次数设置为0，输出该元素到屏幕并将总输出元素加1。

每次外循环我们都会移到表的下一个位置，作为新的判断条件，每次报到表尾的时候，我们都将重新设置到表尾，作为下次循环的表元素。

2、首先采用链式循环链表建立整个约瑟夫环，手动输入第一次的循环次数和每个人所持下一个循环次数。

设立判断指针指向表头，并将该指针是否为空作为外层循环条件。

做一个内层循环，将判断指针移动到循环要输出的数，并设立一个前指针指向该指针的前一个位置，输出该元素后，将循环次数重新赋值成该元素。

接着判断前指针和判断指针比较，如果相等说明整个表已经输出完毕，否则将删除该位置的元素。

3、用链式队列建立循环约瑟夫环，手动输入人数，第一次的循环次数和每个人所持下一个循环次数。

并将每一个元素依次入队列，根据第一次循环次数，建立一个for循环，每一次循环都出队列，如果达到要求的循环次数就输出，否则进队列，这样这个数字就出现在队尾。

约瑟夫问题(数学解法及数组模拟)约瑟夫问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。

在计算机编程的算法中，类似问题又称为约瑟夫环。

又称“丢手绢问题”.）据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。

然而Josephus 和他的朋友并不想遵从。

首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。

接着，再越过k-1个人，并杀掉第k个人。

这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。

问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

? 以上来自百度百科约瑟夫问题是个很有名的问题：N个人围成一个圈，从第一个人开始报数，第M个人会被杀掉，最后一个人则为幸存者，其余人都将被杀掉。

例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。

约瑟夫问题其实并不难，但求解的方法多种多样；题目的变化形式也很多。

接下来我们来对约瑟夫问题进行讨论。

1.模拟解法优点 : 思维简单。

?缺点：时间复杂度高达O(m*n)当n和m的值较大时，无法短时间内得到答案。

为了叙述的方便我们将n个人编号为：1- n ，用一个数组vis 来标记是否存活：1表示死亡 0表示存活 s代表当前死亡的人数? cnt 代表当前报了数的人数用t来枚举每一个位置(当tn时 t=1将人首尾相连)? 那么我们不难得出核心代码如下：bool vis[1000]; --标记当前位置的人的存活状态int t = 0; --模拟位置int s = 0; --死亡人数int cnt = 0; --计数器if(t n) t = 1;if(!vis[t]) cnt++; --如果这里有人,计数器+1if(cnt == m) --如果此时已经等于m,这这个人死去cnt = 0; --计数器清零s++; --死亡人数+1vis[t] = 1 --标记这个位置的人已经死去coutt" "; --输出这个位置的编号}while(s != n);接下来我们来看另一种更为高效快速的解法数学解法我们将这n个人按顺时针编号为0~n-1，则每次报数到m-1的人死去，剩下的人又继续从0开始报数，不断重复，求最后幸存的人最初的编号是多少？我们只需要将最后求得的解加1就能得到原来的编号。

《数据结构》实验报告班级：姓名：学号：日期：08-10-20题目：约瑟夫环一、上机实验的问题和要求：问题描述：编号为1到n的n个人围成一圈，每人带一个密码c，以m为报数上限。

然后从第一个人开始顺时针自1开始报数，报到m的人出列，将其密码作为新的m值，从他的下一个人开始，同样顺时针自1开始报数，依次循环下去，直到所有的人都出列！要求得到依次出列的那些人的编号序列！基本要求：用C代码实现此活动，要求使用一定的算法进行操作，并最终通过程序运算出最后的结果！二、程序设计的基本思想，原理和算法描述：（包括程序的模块结构，数据结构，输入/输出设计，符号名说明等）基本思想：利用不带头结点单向循环链表模拟该活动，在实现了一切动作之后，运用一定的算法得到最终的结果。

程序的模块结构：定义了相关的结构体之后，主要有以下几大模块：1.建立由头指针指示的有n个结点的不带头结点的单向循环链表crt_CLinkList(H,n);2.寻找、输出、删除H单循环链表的第m个结点locfor(H,m);3.最后通过main函数体处理参数的输入与显示，并调用以上两函数，最终解决问题。

主要数据结构：单链的循环链表，即线性表的链式存储结构。

算法的伪码描述：结构体定义如下：typedef struct Lnode /*定义单链表*/{int number; /*编号*/int cipher; /*密码*/struct Lnode *next; /*指针*/}Lnode,*CLinklist; /*重定向命名*/CLinklist H; /*Ｈ为全局单链表*/算法的实现详见源程序。

输入/输出设计本程序并未采用任何二进制文件出入的方式，这点说明将在最后总结提到。

至于函数的出入口问题，在源程序及注释中将得到详细说明，这里不再赘述。

三、源程序及注释：(说明函数功能、入口及出口参数,其他)#include <stdio.h> /* 头文件*/#include <stdlib.h>#include <alloc.h>typedef struct Lnode /*定义单链表*/{int number; /*编号*/int cipher; /*密码*/struct Lnode *next; /*指针*/}Lnode,*CLinklist; /*重定向命名*/CLinklist H; /*Ｈ为全局单链表*/struct Lnode *crt_CLinkList(CLinklist H,int m) /*创建一个不带头结点的单向循环链表*/{ /*其中，Ｈ为全局单链表，m为链表结点总数*/ int i; /*循环记数用*/struct Lnode *ptr1; /*用于索引*/if((ptr1=(struct Lnode *)malloc(sizeof(struct Lnode)))==NULL) /*一旦动态内存分配失败，报错退出！*/ {perror("malloc");return ptr1;}H=ptr1; /*形成单个结点的单循环链表*/ptr1->next=H;for(i=1;i<m;i++) /*形成m个结点的不带头结点的单循环链表*/ {if((ptr1->next=(struct Lnode *)malloc(sizeof(struct Lnode)))==NULL){perror("malloc");ptr1->next=H;return H;}ptr1=ptr1->next; /*其中Ｈ指头，ptr指尾*/ptr1->next=H;}return H; /*返回成功新建的单链表Ｈ*/}void locfor(CLinklist H,int m) /*寻找输出删除链表Ｈ中的第m个结点*/{ /*H为全局链表，m为要查找删除的结点位置*/ int i; /*循环计数*/struct Lnode *ptr;for(i=1;i<=5;i++) /*考虑图形界面的美观问题*/printf("number\tcipher\t");i=1; /*初始化*/while(H->next!=H) /*只剩单个结点时停止循环，进行最后输出！*/ {if(m==1) /*考虑进行自身删除的情况，即m=1*/{for(ptr=H->next;ptr->next!=H;ptr=ptr->next);/*正因为是自身删除才要费大劲寻找其父结点*/printf("%-6d\t",H->number); /*找到后，先输出*/printf("%-6d\t",H->cipher);m=H->cipher; /*确定下一次寻找的m值*/ptr->next=H->next; *删除结点，即自身结点*/ptr=ptr->next;free(H); /*因为对于链表中的结点，每个之前都分配了内存，所以free是必要的*/H=ptr; /*不同于以下普通结点的删除，自身删除还要还原H*/i=1; /*i重置，以方便下一次的循环操作*/}else if(i==m-1) /*因为从自身开始即为1号，因为m-1,而不是m*/{ptr=H->next; /*结点的删除操作同于上面的情况!*/printf("%-6d\t",ptr->number);printf("%-6d\t",ptr->cipher);m=ptr->cipher;H->next=ptr->next;H=H->next;free(ptr);i=1;}else{H=H->next; /*若未找到，则继续遍历！*/i++;}}printf("%-6d\t",H->number); /*对于单个结点的单循环链表，进行最终的输出操作！*/ printf("%-6d",H->cipher);free(H); /*完成所有任务并释放所有内存占用！*/}void main() /*主函数接口*/{ /*调用所有函数，进行实验模拟，并得出实验结果！*/ int i,j,n=30,m,k;struct Lnode *ptr;randomize(); /*因为下面调用了random函数，故此处的初始化很有必要！*/ printf("Now the experiment will begin.You have two choices!\n");/*数据输入可以电脑随机，也可以自行输入*/printf("If you want to enter the datas all by yourself,please enter 1.\n");/*自行输入（方便检测程序问题）*/ printf("If you want to get the datas by the computer,please enter 0.\n"); /*电脑随机产生数据*/printf("Now your choice:"); /*用户选择*/scanf("%d",&j);while(j!=0&&j!=1) /*考虑程序的完善性，对于误输入的提示并报警！*/ {printf("\nYou enter is unillage!Please try again!\n");printf("Now your choice:"); /*重新输入*/scanf("%d",&j);}H=crt_CLinkList(H,n); /*初始化链表*/if(j==0) /*电脑随机充入数据*/for(i=1;i<=30;i++){H->number=i;H->cipher=rand(); /*随机函数*/H=H->next;}else /*此时选择实验者输入数据！*/{for(i=1;i<=30;i++){H->number=i;printf("Now number %d,please enter the cipher:",i);scanf("%d",&k);H->cipher=k;H=H->next;}}m=rand(); /*默认情况下，m随机产生*/printf("Do you want to enter the number m?Enter 1 to set or others cancel!\n");/*当然，如果想自已输，可以进行覆盖*/scanf("%d",&k);if(k==1) /*自行输入m值*/{printf("Please enter the number m:");scanf("%d",&m);}system("cls"); /*考虑屏幕大小，进行分屏显示*/printf("All followed are your datas!\n"); /*界面友善*/for(i=1;i<=5;i++)printf("number\tcipher\t");for(i=0;i<30;i++) /*显示所有处理前数据*/{printf("%-6d\t",H->number);printf("%-6d\t",H->cipher);H=H->next;}printf("And the number m is :%d\n",m);printf("\nAfter the program,the result is:\n");locfor(H,m); /*对所有数据进行实验处理，直至所有结点处理完！*/ getchar();printf("\nPress any key return!"); /*TC环境下，方便查看结果！*/getchar();}四、用户使用说明与测试运行结果：1．运行程序后，首先弹出界面，截图如右：理性化的选择：如果打1，则所有的cipher均由用户输入，这样方便对特殊数据进行程序测试！如果打0，那么所有的数据均由电脑产生！那如果打其他的呢？考虑到误输入，加了一个循环，以提高程序的健壮性！2．首先自行输入数据进行测试。

这是17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。

问怎样排法，才能使每次投入大海的都是非教徒。

*问题分析与算法设计约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。

这里给出一种实现方法。

题目中30个人围成一圈，因而启发我们用一个循环的链来表示。

可以使用结构数组来构成一个循环链。

结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被扔下海的标记，为1表示还在船上。

从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。

这样循环计数直到有15个人被扔下海为止。

[编辑本段] 约瑟夫问题的一般形式：约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。

例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。

最后剩下1号。

假定在圈子里前K个为好人，后K个为坏人，你的任务是确定这样的最少M，使得所有的坏人在第一个好人之前被杀掉。

C++代码示例: #i n c l u d e<i o s t r e a m>u s i n g n a m e s p a c e s t d;v o i d m a i n(){i n t n,m,a[101],k,i,j,n u m;.n-2,n-1,0,1,2,...k-2并且从k开始报0。

现在我们把他们的编号做一下转换：k-->0 k+1--> 1k+2--> 2......k-2-->n- 2k-1-->n- 1 变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k)m o d n 如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。

josephus问题数学解法Josephus 问题是一个经典的数学问题，描述如下：有 n 个人围成一圈，从第一个人开始往后报数，报到 m 的人出圈，后面的人继续从 1 开始报数，直到最后一个人留下来。

问最后留下的人的编号是多少？下面是 Josephus 问题的数学解法：设最后留下的人的编号为 f(n,m)，则可以得出以下递推式：f(1,m) = 0f(n,m) = (f(n-1,m) + m) % n其中，% 表示取模运算。

以上递推式基于以下思路：假设有 n 个人，编号分别为 0,1,2,...,n-1。

第一轮中，第 m 个人出圈，剩下的人编号为 0,1,...,m-2,m,...,n-1。

由于是围成一圈，所以下一轮中第一个人的编号为 m%n。

而在上一轮中，编号为 m%n 的人出圈了，所以编号为 m%n+1,...,n-1,0,1,...,m%n-1的人组成了一个新的圈。

我们需要求出这个新圈中最后留下的人的编号，即 f(n-1,m)。

由于新圈中每个人的编号都比原来的编号大 m，所以我们需要将 f(n-1,m) 加上 m，以得到在原圈中他的编号。

然而，如果加上 m 后编号超过了 n-1，那么我们需要将编号重新回到 0，这就是将加和结果取模的原因。

最终，当 n=1 时，无论 m 的值为多少，都只剩下编号为 0 的人。

下面是一个 Python 实现的例子：```def josephus(n, m):f = 0for i in range(2, n+1):f = (f + m) % ireturn fprint(josephus(5, 3)) # 输出 3```。