约瑟夫环

约瑟夫环实验报告约瑟夫环是一个经典的数学问题，它涉及到一个有趣的游戏。

这个游戏的规则是：有N个人站成一圈，从某个人开始，每报数到第M个人，就将该人从圈中移出去，再从下一个人开始重新报数，如此循环，直到只剩下一个人为止。

那么，我们将通过实验来探究一下约瑟夫环的性质和一些有趣的现象。

首先，我们设定了一组实验条件。

假设有10个人，从1到10编号，报数为3。

我们选择从编号为1的人开始报数，然后每次报数到第3个人。

接下来，我们按照约瑟夫环的规则进行实验。

实验开始后，我们可以观察到一系列有趣的现象。

首先，被淘汰的人并不会立即离开圈子，而是继续留在原位，但不再参与后续的报数和淘汰。

当每次报数到达M的倍数时，即到了第3个人、第6个人、第9个人等等，这些人就会被逐渐淘汰出圈。

在实验过程中，我们发现了一个有趣的规律。

剩下的人似乎总是固定按照一定的顺序被淘汰。

为了更好地观察这个规律，我们进行了多组实验，并记录了淘汰顺序。

首先，在报数为3的情况下，我们记录了当有10个人时的淘汰顺序。

开始时，第1轮淘汰的是第3个人，然后是第6个人，之后是第9个人。

接着，轮到第2个人被淘汰，然后是第7个人，最后是第1个人。

可见，在这个实验条件下，被淘汰的顺序是3、6、9、2、7、1。

我们可以看到，在最后几轮淘汰时，被淘汰的顺序逐渐回到了初始的编号1。

接着，我们将实验条件略作改变，观察是否会出现相似的淘汰顺序。

这次，我们依然有10个人，报数为4。

开始时，第1轮淘汰的是第4个人，然后是第8个人，之后是第2个人。

接着，轮到第5个人被淘汰，然后是第10个人，最后是第6个人。

通过这次实验，我们可以观察到一些不同之处。

尽管淘汰的顺序在最后几轮回到了初始的编号1，但淘汰的间隔变得更长了，而且整体的淘汰顺序也有了一定的变化。

通过对约瑟夫环实验的多次观察和记录，我们可以总结出一些结论。

首先，淘汰的顺序呈现出周期性，并在最后几轮回到了初始的编号。

其次，在不同的实验条件下，淘汰的规律可能会有所不同。

约瑟夫环课课程设计一、教学目标本节课的教学目标是让学生掌握约瑟夫环的基本概念、算法及其应用。

通过本节课的学习，学生应能够理解约瑟夫环的原理，运用约瑟夫环算法解决实际问题。

具体来说，知识目标包括：1.了解约瑟夫环的定义及其数学基础；2.掌握约瑟夫环算法的实现方法及其时间复杂度；3.能够运用约瑟夫环算法解决生活中的排队问题。

技能目标包括：1.能够使用编程语言实现约瑟夫环算法；2.能够分析代码的执行过程，优化算法性能；3.能够将约瑟夫环算法应用到实际问题中，解决问题。

情感态度价值观目标包括：1.培养学生对计算机科学的兴趣，激发学生主动探究的精神；2.培养学生团队协作意识，提高学生沟通表达能力；3.培养学生解决问题的能力，增强学生面对挑战的信心。

二、教学内容本节课的教学内容主要包括约瑟夫环的定义、算法及其应用。

具体安排如下：1.引言：介绍约瑟夫环的背景知识，激发学生兴趣；2.约瑟夫环的定义：讲解约瑟夫环的数学基础，让学生理解其含义；3.约瑟夫环算法：讲解约瑟夫环算法的实现方法，让学生掌握算法步骤；4.算法优化：分析算法的时间复杂度，引导学生思考如何优化算法；5.应用实例：介绍约瑟夫环算法在实际问题中的应用，让学生学会解决问题；6.课堂练习：安排练习题，让学生巩固所学知识。

三、教学方法为了提高教学效果，本节课采用多种教学方法相结合的方式：1.讲授法：讲解约瑟夫环的基本概念、算法及其应用；2.讨论法：学生分组讨论，培养学生的团队协作能力；3.案例分析法：分析实际问题，引导学生将理论知识应用于实践；4.实验法：安排课堂练习，让学生动手实践，巩固所学知识。

四、教学资源为了支持教学内容和教学方法的实施，本节课准备以下教学资源：1.教材：提供约瑟夫环相关知识的文本资料；2.参考书：为学生提供更多的学习资料，拓展知识面；3.多媒体资料：制作PPT，生动形象地展示约瑟夫环的原理和应用；4.实验设备：提供计算机等设备，让学生动手实践。

约瑟夫环递推推导过程问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。

求胜利者的编号。

下面利用数学推导，如果能得出一个通式，就可以利用递归、循环等手段解决。

下面给出推导的过程：(1)第一个被删除的数为（m-1）%n;(2)第二论的开始数字为k，那么这n-1个数构成的约瑟夫环为k,k+1,k+2,...k-3,k-2做一个简单映射。

（p(x)=(x-k)%n）k--->0k+1--->1k+2--->2------k-2--->n-2这是一个n-1个人的问题，如果能从n-1个人的问题的解退出n 个人问题的解，从而得到一个递推公式，那么问题就解决了。

假如我们已经知道了n-1个人时，最后胜利者的编号为x，利用映射关系逆推，就可以得出n个人时，胜利者的编号为(x+k)%n。

其中k=m%n。

代入（x+k）%n<=>(x+(m%n))%n<=>(x%n + (m%n)%n)%n<=> (x%n+m%n)%n <=> (x+m)%n(3)第二个被删除的数为（m-1）%n-1(4)假设第三轮的开始数字为o，那这n-2个数构成的约瑟夫环为o,o+1,o+2,...,o-3,o-2。

继续做映射p(x)=(y-o)%(n-2)o--->0o+1--->1o+2--->2------o-2--->n-3这是一个n-2个人的问题。

假设最后胜利者为y，那么n-1个人时，胜利者为(y+o)%(n-1)，其中o等于m%(n-1)。

代入可得(y+m)%(n-1)要得到n-1个人问题的解，只需要得到n-2个人问题的解，倒退下去。

只有一个人时，胜利者就是编号0.小面给出递推式：f(1)=0;f(i)=(f[i-1]+m)%i;(i>1)有了递推公式，实现就非常简单了，给出循环的两种实现。

约瑟夫环
约瑟夫环是一个数学的应用问题：
已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。

从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

程序输出出列顺序.
要通过输入n, k , m三个正整数，来求出列的序列
例如n=12, k=3,m=7时，出队序列为9 4 12 8 6 5 7 11 3 10 1 2
解决问题的核心步骤：
1.建立一个具有n个链结点，无头结点的循环链表
2.确定第1个报数人的位置
3.不断地从链表中删除链结点，直到链表为空
运行结果截图：。

约瑟夫环上机实验报告1. 概述约瑟夫环问题是一个经典的数学问题，该问题是以约瑟夫·弗拉维奥(Josephus Flavius)命名的，故称为约瑟夫环。

问题的具体描述如下：在编号为1到n的n 个人围成一个圆圈，从第一个人开始报数，报到m的人出列，然后从出列的下一个开始重新从1到m报数，再次报到m的人再次出列，如此循环下去，直到所有的人都出列为止。

本次实验旨在使用程序实现约瑟夫环的模拟，并观察对于不同的参数n和m，最后剩余的人的编号特点。

2. 实验设计2.1 算法设计本实验中采用循环链表来模拟约瑟夫环，首先构建一个含有n个结点的循环链表，每个结点表示一个人，每个结点的数据域存储该人的编号。

然后根据报数规则，依次遍历链表，当报数为m时，删除对应的结点。

直到链表中仅剩一个结点为止。

2.2 程序实现pythonclass ListNode:def __init__(self, val=0):self.val = valself.next = Nonedef josephus(n, m):if n == 0:return -1构建循环链表dummy = ListNode(-1)cur = dummyfor i in range(1, n + 1):node = ListNode(i)cur.next = nodecur = cur.nextcur.next = dummy.next模拟游戏过程count = 0while cur.next != cur:count += 1if count == m:cur.next = cur.next.nextcount = 0else:cur = cur.nextreturn cur.val3. 实验结果为了观察不同参数n和m对最后剩余的人的编号的影响，我们进行了多组实验。

结果如下：n m 最后剩余的人的编号5 2 310 3 415 4 1420 5 6从实验结果可以看出，最后剩余的人的编号与参数m有关，而与参数n无关。

数据结构实验报告约瑟夫环约瑟夫环是一个古老而有趣的问题，也是数据结构中一个经典的应用。

它的故事发生在公元前1世纪，当时犹太人正面临罗马的入侵。

为了避免被俘虏，一群犹太士兵决定以一种特殊的方式自杀，而不是被罗马人俘虏。

他们围成一个圈，按照某个规则进行自杀，直到只剩下一个人为止。

这就是著名的约瑟夫环问题。

在这个问题中，我们有n个人，编号从1到n，围成一个圈。

按照一定的规则，从第一个人开始报数，每次报到m的人将被淘汰。

然后，从下一个人开始重新报数，如此循环，直到只剩下一个人为止。

这个问题的解决方法有很多，其中最常见的是使用链表数据结构。

我们可以将每个人表示为一个节点，节点之间通过指针连接，形成一个环形链表。

每次淘汰一个人后，只需要将指针跳过被淘汰的节点，重新连接链表。

为了更好地理解这个问题，我们可以通过一个简单的例子来演示。

假设有10个人，编号从1到10，每次报数到3的人将被淘汰。

首先，我们将这10个人表示为一个环形链表：1->2->3->4->5->6->7->8->9->10->1。

按照规则，第一次报数到3的人是3号，所以我们将3号节点从链表中删除：1->2->4->5->6->7->8->9->10->1。

接下来，从4号节点开始重新报数。

第二次报数到3的人是6号，所以我们再次将6号节点从链表中删除：1->2->4->5->7->8->9->10->1。

以此类推，直到只剩下一个人为止。

通过这个例子，我们可以看到约瑟夫环问题的解决方法非常简单直观。

使用链表数据结构，每次淘汰一个人后，只需要将指针跳过被淘汰的节点，重新连接链表。

这种方法的时间复杂度为O(n*m)，其中n为人数，m为报数的次数。

除了链表，还有其他数据结构可以用来解决约瑟夫环问题。

约瑟夫环问题的两种解法（详解）约瑟夫环问题的两种解法（详解）题⽬：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。

0123456789 12345678910 4567891012 789101245 10124578 4578101
810145
45810
1045
104
4约瑟夫环——递推公式
递推公式：
f(N,M)=(f(N−1,M)+M)%N
f(N,M)表⽰，N个⼈报数，每报到M时杀掉那个⼈，最终
f(N−1,M)表⽰，N-1个⼈报数，每报到M时杀掉那个⼈，最终胜利者的编号
现在假设有10个⼈，报到3的⼈就会被杀掉，我们⽤数字给这⼗个⼈编号为
1 2 3 4 5 6 7 8 9 10
第·⼀⾏绿⾊那⾏是数组下标，第⼆⾏是每个⼈的编号
现在逆向推导
f(1,3):只剩最后⼀个⼈，胜利者的数组下标为0
f（2,3）=(f(1,3)+3)%2=1,只有两个⼈的时候，胜利者下标为1。

f（10,3）=3，因为我们数组下标是从0开始的，所以⼈的编号是下标+1，也就是4
那么这个公式是怎么推导的呢？
1.假设我们已经知道了10个⼈时，胜利者的下标为3，那下⼀次9个⼈时，胜利者的下标为多少？
其实就是10个⼈时杀掉了编号为3（即数组下标为2）的⼈后，后⾯的⼈都往前移动了3位，所以胜利者的下标由3变成了0
2.那我们倒过来我们知道9个⼈时，胜利者的下标为0，那10个⼈时胜利者的下标为多少？
其实这和上⾯的问题⼀样，这是这是上个问题的逆过程，就是把⼤家都往后移动3位，所以f(10,3)=f(9,3)+3,不过可能会出现数组越界所以要取模变成f（10,3）=（f（9,3）+3）%10
3.那么⼈数改为n报到m时就杀掉数组怎么移动呢
⼀样的，杀⼀⼈则后⾯的⼈的下标都往前移动m则，f（n，m）=（f（n-1，m）+m）%n。

循环队列之约瑟夫环问题约瑟夫问题 约瑟夫环（约瑟夫问题）是⼀个数学的应⽤问题：已知n个⼈（以编号1，2，3...n分别表⽰）围坐在⼀张圆桌周围。

从编号为k的⼈开始报数，数到m的那个⼈出列；他的下⼀个⼈⼜从1开始报数，数到m的那个⼈⼜出列；依此规律重复下去，直到圆桌周围的⼈全部出列。

通常解决这类问题时我们把编号从0~n-1，最后结果+1即为原问题的解。

循环队列求解（链式）#include<stdio.h>#include<stdlib.h>//循环队列//typedef int ElemType;typedef struct QueueNode{int data;struct QueueNode *next;}QueueNode;typedef struct Queue{QueueNode *front;QueueNode *rear;}Queue;void InitQueue(Queue *q){q->front=q->rear=NULL;}void EnQueue(Queue *q , int value){QueueNode *temp=(QueueNode*)malloc(sizeof(QueueNode));temp->data=value;if(q->rear==NULL){temp->next=temp;q->rear=q->front=temp;}else{temp->next=q->rear->next;q->rear->next=temp;q->rear=temp;}}//enter a element from the tailvoid DeQueue(Queue *q, int *value){QueueNode *temp=(QueueNode*)malloc(sizeof(QueueNode)); if(q->rear==NULL){return;}// It's nullelse if(q->rear->next==q->rear){*value=q->front->data;free(q->rear);q->rear=q->front=NULL;}//It just has one nodeelse{*value=q->front->data;temp=q->front;q->front=temp->next;q->rear->next=q->front;}//more one nodefree(temp);}//delete a element from the headint main(){Queue *q=(Queue*)malloc(sizeof(Queue));int i,m,n,count,temp;printf("请输⼊⼈数n和循环要报的数m（两数之间留个空格）\n"); scanf("%d%d",&n,&m);for(i=1;i<=n;i++)EnQueue(q,i);printf("出圈序列：\n");while(q->front){ count=1;while(count<m){q->front=q->front->next;q->rear=q->rear->next;count++;}count=1;DeQueue(q,&temp);printf("%d ",temp);}putchar('\n');}简单解法#include <stdio.h>int josephus(int n, int m) {if(n == 1) {return0;}else {return (josephus(n-1, m) + m) % n;}}int main() {int n, m;while (scanf("%d", &n) == 1) {if (!n) {break;}scanf("%d", &m);int result = josephus(n, m);printf("%d\n", result+1);}return0;}。

约瑟夫环问题的三种解法约瑟夫问题是个著名的问题：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，2，3...n分别表⽰）围坐在⼀张圆桌周围。

从编号为1的⼈开始报数，数到m的那个⼈出列；他的下⼀个⼈⼜从1开始报数，数到m的那个⼈⼜出列；依此规律重复下去，直到圆桌周围的⼈全部出列。

（也类似于变态杀⼈狂问题）通常解决这类问题时我们把编号从0~n-1，最后结果+1即为原问题的解。

通常，我们会要求输出最后⼀位出列的⼈的序号。

那么这⾥主要研究的是最后⼀个出列的⼈的序号要怎么确定。

当n，m数据量很⼩的时候，我们可以⽤循环链表模拟约瑟夫环的过程。

当模拟到⼈数等于1的时候，输出剩下的⼈的序号即可。

这种⽅法往往实现起来⽐较简单，⽽且也很容易理解。

但是时间复杂度却是很糟糕的，达到了O（n m），这样的话，其实在n，m⽐较⼤的时候（n m达到10^8或者更⼤），那么要得出结果往往需要耗费很长的时间，但是我们可以运⽤⼀点数学上的技巧，将最后结果推导出来。

为了简化出列的过程：⾸先我们把这n个⼈的序号编号从0~n-1（理由很简单，由于m是可能⼤于n的，⽽当m⼤于等于n时，那么第⼀个出列的⼈编号是m%n，⽽m%n是可能等于0的，这样编号的话能够简化后续出列的过程），当数到m-1的那个⼈出列，因此我们编号完成之后，开始分析出列的过程：第⼀次出列：⼀开始的时候，所有⼈的编号排成序列的模式即为：0,1,2,3,4,5...n-2，n-1那么第⼀次出列的⼈的编号则是(m-1)%n1，那么在第⼀个⼈出列之后，从他的下⼀个⼈⼜开始从0开始报数，为了⽅便我们设k1 =m%n1（n1为当前序列的总⼈数）那么在第⼀个⼈出列之后，k1则是下⼀次新的编号序列的⾸位元素，那么我们得到的新的编号序列为：k1，k1+1，k1+2，k1+3...n-2，n-1，0，1，2...k1-3，k1-2 (k1-1第⼀次已出列)那么在这个新的序列中，第⼀个⼈依旧是从0开始报数，那么在这个新的序列中，每个⼈报的相应数字为：0,1，2,3....n-2那么第⼆次每个⼈报的相应数字与第⼀次时⾃⼰相应的编号对应起来的关系则为：0 --> k11 --> k1+12 --> k1+2...n-2 ---> (k1+n-2)%n1(n1为当前序列的总⼈数，因为是循环的序列，k1+n-1可能⼤于总⼈数)那么这时我们要解决的问题就是n-1个⼈的报数问题（即n-1阶约瑟夫环的问题）可能以上过程你还是觉得不太清晰，那么我们重复以上过程，继续推导剩余的n-1个⼈的约瑟夫环的问题：那么在这剩下的n-1个⼈中，我们也可以为了⽅便，将这n-1个⼈编号为：0,1,2,3,4...n-2那么此时出列的⼈的编号则是（m-1） % n2（n2为当前序列的总⼈数），同样的我们设k2 = m % n2，那么在这个⼈出列了以后，序列重排，重排后新的编号序列为：k2，k2+1，k2+2，k2+3...n-2，n-1，0，1，2...k2-3，k2-2 (k2-1第⼀次已出列)那么在这个新的序列中，第⼀个⼈依旧是从1开始报数，那么在这个新的序列中，每个⼈报的相应数字为：1,2，3,4....n-2那么这样的话是不是⼜把问题转化成了n-2阶约瑟夫环的问题呢？后⾯的过程与前两次的过程⼀模⼀样，那么递归处理下去，直到最后只剩下⼀个⼈的时候，便可以直接得出结果当我们得到⼀个⼈的时候（即⼀阶约瑟夫环问题）的结果，那么我们是否能通过⼀阶约瑟夫环问题的结果，推导出⼆阶约瑟夫环的结果呢？借助上⾯的分析过程，我们知道，当在解决n阶约瑟夫环问题时，序号为k1的⼈出列后，剩下的n-1个⼈⼜重新组成了⼀个n-1阶的约瑟夫环，那么假如得到了这个n-1阶约瑟夫环问题的结果为ans（即最后⼀个出列的⼈编号为ans），那么我们通过上述分析过程，可以知道，n阶约瑟夫环的结果(ans + k)%n(n为当前序列的总⼈数)，⽽k = m%n则有：n阶约瑟夫环的结果(ans + m % n)%n，那么我们还可以将该式进⾏⼀下简单的化简：当m<n时，易得上式可化简为：（ans + m）% n⽽当m>=n时，那么上式则化简为：（ans % n + m%n%n）% n即为：（ans % n + m%n）% n⽽（ans + m）% n = （ans % n + m%n）% n因此得证(ans + m % n)%n = （ans + m）% n这样的话，我们就得到了递推公式，由于编号是从0开始的，那么我们可以令f[1] = 0； //当⼀个⼈的时候，出队⼈员编号为0f[n] = (f[n-1] + m)%n //m表⽰每次数到该数的⼈出列，n表⽰当前序列的总⼈数⽽我们只需要得到第n次出列的结果即可，那么不需要另外声明数组保存数据，只需要直接⼀个for循环求得n阶约瑟夫环问题的结果即可由于往往现实⽣活中编号是从1-n，那么我们把最后的结果加1即可。

1．约瑟夫环问题（实验类型：综合型）1）问题描述：有编号为1, 2…n 的 n 个人按顺时针方向围坐一圈，每人持有一个正整数密码。

开始给定一个正整数 m，从第一个人按顺时针方向自1开始报数，报到m者出列，不再参加报数，这时将出列者的密码作为m，从出列者顺时针方向的下一人开始重新自1开始报数。

如此下去，直到所有人都出列。

试设计算法，输出出列者的序列。

2）实验要求: 采用顺序和链式两种存储结构实现3) 实现提示：✧用顺序表来存储围座者的序号和密码(顺序存储结构).⏹用number 和code分别表示围座者的序号和密码.假设围座者人数为j,当前使用密码为m,开始报数者位置为s, 那么下一出列者位置为s=(s+m-1) mod j.⏹当我们要在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表的第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。

若要删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。

✧用链式存储解决此问题时可以采用循环链表.4）注意问题:顺序存储和链式存储实现此算法时计算出列位置的不同方法，人员出列后所做操作的区别。

#include<stdio.h>#include<stdlib.h>typedef struct Node{int key;//密码int num;//编号struct Node *next;}Node,*Link;void InitList(Link &L){//创建空链表L=(Node*)malloc(sizeof(Node));if(!L)exit(1);L->key=0;L->next=L;}void Creatlinklist(int n,Link&L){//初始化链表Link p,q;q=L;for(int i=1;i<=n;i++){p=(Node*)malloc(sizeof(Node));if(!p)exit(1);scanf("%d",&p->key);p->num=i;L->next=p;L=p;}L->next=q->next;free(q);}Link Locate_m(Link &p,int m){//找到第m个Link q;for(int j=1;j<m;j++)p=p->next;q=p->next;m=q->key;return q;}void Delete_m(Link &L,Linkp,Link q){//删除第m个p->next=q->next;free(q);}int main(){Link L,p,q;int n,m;L=NULL;InitList(L);//构造一个只有头节点的空链表printf("输入初始密码：");scanf("%d",&m);//初始密码为m printf("输入总人数：");scanf("%d",&n);//总人数为nprintf("输入每个人手中的正整数密码：");Creatlinklist(n,L);//建立约瑟夫环p=L;printf("出列者顺序为：") ;for(int i=1;i<=n;i++){q=Locate_m(p,m);//找到第m个printf("%d ",q->num);Delete_m(L,p,q);//删除第m个}}5）实验心得：大部分的时间都用在了编程上，主要是因为C语言掌握的问题，C语言基础不好特别是对于C语言中链表的一些定义和基本操作不够熟练，导致在编程过程中还要不断的拿着c语言的教材查找，所以今后还要对C语言多练习，多动手，多思考。

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

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

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

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

2.实验目的：掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。

3.源程序代码：#include<stdio.h>#include<stdlib.h>typedef struct LNode{int order;int key;LNode *next;}*Linklist;Linklist putlist(){Linklist L,p;int n,i;p=L;printf("输入人的个数");scanf("%d",&n);for(i=1;i<=n;i++){p->next=(Linklist)malloc(sizeof(LNode));p=p->next;p->order=i;scanf("%d",&p->order);p->next=L;}return L;}void outorder(Linklist LG){Linklist p=LG,q=p->next;int i,m;printf("输入m:");scanf("%d",m);while(LG->next!=LG){i=1;while(i<m){p=q;q=q->next;if(q!=LG) i++;};printf("%d",p->order);m=q->key;p->next=q->next;free(q);q=p->next;if(q==LG){p=q;q=q->next;};};}void main(){Linklist L;L=putlist();outorder(L);}4测试数据m=20n=7密码次序：3,1,7,7,4,8,4 输出次序：6,1,4,7,2,3,5。