下载文档原格式
约瑟夫环数据结构实验报告约瑟夫环数据结构实验报告引言约瑟夫环是一种经典的数学问题，它涉及到一个有趣的数据结构。
本次实验旨在通过实现约瑟夫环数据结构，深入理解该问题，并探索其在实际应用中的潜力。
本报告将介绍实验的设计和实现过程，并分析实验结果。
实验设计在本次实验中，我们选择使用链表来实现约瑟夫环数据结构。
链表是一种非常灵活的数据结构，适合用于解决约瑟夫环问题。
我们设计了一个Josephus类，其中包含了创建环、添加元素、删除元素等操作。
实验实现1. 创建环在Josephus类中，我们首先需要创建一个循环链表。
我们使用一个头节点来表示环的起始位置。
在创建环的过程中，我们可以选择指定环的长度和起始位置。
2. 添加元素在创建环之后，我们可以通过添加元素来向约瑟夫环中插入数据。
我们可以选择在环的任意位置插入元素，并且可以动态地调整环的长度。
3. 删除元素根据约瑟夫环的规则，每次删除一个元素后，下一个元素将成为新的起始位置。
我们可以通过删除元素的操作来模拟约瑟夫环的运行过程。
在删除元素时，我们需要考虑环的长度和当前位置。
实验结果通过实验，我们得出了以下结论：1. 约瑟夫环数据结构可以有效地模拟约瑟夫环问题。
通过创建环、添加元素和删除元素的操作，我们可以模拟出约瑟夫环的运行过程，并得到最后剩下的元素。
2. 约瑟夫环数据结构具有一定的应用潜力。
除了解决约瑟夫环问题，该数据结构还可以用于其他类似的问题，如任务调度、进程管理等。
3. 约瑟夫环数据结构的时间复杂度较低。
由于约瑟夫环的特殊性质，我们可以通过简单的链表操作来实现该数据结构，使得其时间复杂度较低。
结论本次实验通过实现约瑟夫环数据结构，深入理解了该问题，并探索了其在实际应用中的潜力。
通过创建环、添加元素和删除元素的操作，我们可以模拟出约瑟夫环的运行过程，并得到最后剩下的元素。
约瑟夫环数据结构具有一定的应用潜力，并且具有较低的时间复杂度。
通过本次实验，我们对数据结构的设计和实现有了更深入的理解，并为将来的研究和应用奠定了基础。
循环单链表的概念
循环单链表是一种链表的变体，它与普通的单链表最大的不同在于，循环单链表的尾节点指向链表的头节点，形成一个闭环。
具体来说，循环单链表中每个节点除了存储数据之外，还包括一个指向下一个节点的指针。
最后一个节点的指针不指向空，而是指向头节点，这样就形成了一个循环。
与普通的单链表相比，循环单链表可以更方便地实现某些操作，比如遍历整个链表。
因为链表的尾节点指向头节点，所以可以从任意节点出发，一直遍历到尾节点并回到头节点，实现循环遍历。
循环单链表的操作和普通的单链表类似，包括插入、删除、搜索等。
不过在插入和删除节点时，需要注意维护链表的循环性，即在插入新节点时将其指针设置为下一个节点，而在删除节点时需要更新前一个节点的指针。
循环单链表的一个应用场景是约瑟夫问题，即一群人围成一个环形，从某个位置开始报数，每报到某个数时，该人出列，然后下一个人继续从1开始报数。
通过循环单链表可以很方便地模拟这个过程。
约瑟夫环问题⼩结⼀问题描述约瑟夫环问题的基本描述如下：已知n个⼈(以编号1，2，3...n分别表⽰)围坐在⼀张圆桌周围。
从编号为1的⼈开始报数，数到m的那个⼈出列；他的下⼀个⼈⼜从1开始报数，数到m的那个⼈⼜出列；依此规律重复下去，要求找到最后⼀个出列的⼈或者模拟这个过程。
⼆问题解法在解决这个问题之前，⾸先我们对⼈物进⾏虚拟编号，即相当于从0开始把⼈物重新进⾏编号，即⽤0,1,2,3,...n-1来表⽰⼈物的编号，最后返回的编号结果加上1，就是原问题的解(为什么这么做呢，下⽂有解释)。
⽽关于该问题的解通常有两种⽅法：1.利⽤循环链表或者数组来模拟整个过程。
具体来讲，整个过程很明显就可以看成是⼀个循环链表删除节点的问题。
当然，我们也可以⽤数组来代替循环链表来模拟整个计数以及出列的过程。
此处只给出利⽤数组来模拟这个过程的解法，最终结果为最后⼀个出列的⼈的编号：#include<iostream>#include<unordered_map>#include<queue>#include<cstring>#include<cstdlib>#include<cmath>#include<algorithm>#include<sstream>#include<set>#include<map>using namespace std;int main(){int n,m;cin>>n>>m;vector<int>rs(n);for(int i = 0 ; i < n; i++)rs[i] = i + 1;//对⼈物重新进⾏编号，从0开始int cur_index = 0;//当前圆桌状态下的出列⼈的编号int out_cnt = 0;//⽤以表⽰出列的⼈数int cnt = n;//表⽰当前圆桌的总⼈数while(out_cnt < n - 1)//当out_cnt等于n-1时，循环结束，此时圆桌师⽣最后⼀个⼈，即我们要的结果{if(cur_index + m > cnt){if((cur_index + m) % cnt == 0)//这种情况需要单独考虑，否则cur_index就变成负值了cur_index = cnt - 1;elsecur_index = (cur_index + m) % cnt - 1;}elsecur_index = cur_index + m - 1;cnt--;out_cnt++;cout<<"当前出列的为："<<*(rs.begin() + cur_index)<<endl;rs.erase(rs.begin() + cur_index);//从数组中删去需要出队的⼈员}cout<<"最后⼀个出列的⼈物为："<<rs[0]<<endl;}该⽅法的时间复杂度为O(nm)，空间复杂度为O(n)，整个算法的基本流程还是⽐较清晰的，相当于每次循环更新cur_cnt、cnt和out_cnt这三个变量，当out_cnt == n-1时，此时出队的⼈数⼀共有n-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. 理解并掌握约瑟夫问题的基本概念和解题思路。
2. 掌握使用循环链表解决约瑟夫问题的方法。
3. 通过编程实现约瑟夫问题，验证算法的正确性。
二、实验内容1. 约瑟夫问题背景及问题描述约瑟夫问题（Josephus Problem）是一个经典的数学问题，其描述如下：有n个人围成一圈，从第一个人开始报数，每次报到第k个人时，他就会被淘汰出局，然后从下一个人重新开始报数。
如此循环，直到只剩下最后一个人。
我们需要求出最后这个人最初的编号。
2. 约瑟夫问题的递归解法对于n个人围成的圈，我们可以将其分解为两部分：剩余的n-1个人和被淘汰的1个人。
设最后剩下的人的编号为J(n, k)，则有如下递推关系：J(n, k) = (J(n-1, k) + k) % n当n=1时，即只有一个人时，J(1, k) = 0。
3. 使用循环链表解决约瑟夫问题为了解决约瑟夫问题，我们可以使用循环链表来模拟这个问题。
在循环链表中，每个节点表示一个人，节点的data字段存储该人的编号，next字段指向下一个节点。
以下是使用循环链表解决约瑟夫问题的步骤：（1）创建一个循环链表，包含n个节点，节点的编号从1到n。
（2）设置一个指针指向链表的头节点，开始从该节点开始报数。
（3）每次报数到第k个人时，将该节点删除，并更新指针指向下一个节点。
（4）重复步骤（3），直到链表中只剩下一个节点，该节点的data字段即为最后剩下的人的编号。
4. 实验实现以下是使用C语言实现的约瑟夫问题求解程序：```c#include <stdio.h>#include <stdlib.h>typedef struct Node {int data;struct Node next;} Node;Node createCircle(int n) {Node head = NULL;Node tail = NULL;for (int i = 1; i <= n; i++) {Node newNode = (Node)malloc(sizeof(Node)); newNode->data = i;newNode->next = NULL;if (head == NULL) {head = newNode;tail = newNode;} else {tail->next = newNode;tail = newNode;}}tail->next = head; // 形成循环链表return head;}int josephus(int n, int k) {Node head = createCircle(n);Node pcur = head;Node ptail = NULL;int count = 0;while (pcur->next != pcur) {count = (count + k) % (n - 1);ptail = pcur;pcur = pcur->next;if (count == 0) {ptail->next = pcur->next;free(pcur);pcur = ptail->next;count = 0;}}printf("最后剩下的人的编号为：%d\n", pcur->data); free(pcur);return pcur->data;}int main() {int n, k;printf("请输入总人数n和报数间隔k：");scanf("%d %d", &n, &k);josephus(n, k);return 0;}```三、实验结果与分析1. 实验结果通过运行上述程序，我们可以得到最后剩下的人的编号。
《数据结构》课程设计报告书题目：约瑟夫环系别：计算机科学与应用学号：学生姓名：指导教师：完成日期：2012年6月7日目录1．需求分析 (3)1.1 功能分析 (3)1.2开发平台 (3)2．概要设计 (3)3. 程序设计主要流程 (5)4．调试与操作说明 (5)4.1调试情况 (5)4.2操作说明 (6)总结 (8)致谢 (9)附录 (9)参考文献 (13)指导教师评语： (14)1．需求分析1.1 功能分析本次选做的课程设计是改进约瑟夫(Joseph)环问题。
约瑟夫环问题是一个古老的数学问题，本次课题要求用程序语言的方式解决数学问题。
此问题仅使用单循环链表就可以解决此问题。
在建立单向循环链表时，因为约瑟夫环的大小由输入决定。
为方便操作，我们将每个结点的数据域的值定为生成结点时的顺序号和每个人持有的密码。
进行操作时，用一个指针r指向当前的结点，指针H指向头结点。
然后建立单向循环链表，因为每个人的密码是通过scanf()函数输入随机生成的，所以指定第一个人的顺序号，找到结点，不断地从链表中删除链结点，直到链表剩下最后一个结点，通过一系列的循环就可以解决改进约瑟夫环问题。
1.2开发平台WindowsXP操作系统；Microsoft Visual C++ 6.0；2．概要设计编号为1，2… n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。
一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。
这个问题采用的是典型的循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。
r->next=H。
解决问题的核心步骤：首先建立一个具有n个链结点，无头结点的循环链表。
然后确定第1个报数人的位置。
最后不断地从链表中删除链结点，直到链表为空。
数据结构实验报告题目：约瑟夫环问题一．设计内容[问题描述]约瑟夫环问题的一种描述是：编号为1, 2, 3,…，n的n个人按顺时针方向围坐一圈，每人手持一个密码（正整数）。
一开始任选一个整数作为报数上限值，从第一人开始顺时针自 1 开始顺序报数,报到m 时停止报数。
报m 的人出列, 将它的密码作为新的m 值,从他在顺时针方向上的下一个人开始重新从 1 报数, 如此下去直到所有人全部出列为止。
试设计程序实现之。
[基本要求] 利用循环链表存储结构模拟此过程,按照出列的顺序打印各人的编号。
[ 实验提示] 程序运行后首先要求用户指定初始报数上限值。
然后读取各人的密码。
设n<=30 。
程序执行后,要求用户在计算机终端上显示“提示信息”后,用键盘输入“提示信息”中规定的命令,以“回车符”为结束标志。
相应的输入数据和运算结果显示在其后。
二、设计目的1. 达到熟练掌握C++ 语言的基本知识和技能；2. 能够利用所学的基本知识和技能,解决简单的面向对象程序设计问题。
3. 把课本上的知识应用到实际生活中,达到学以致用的目的。
三、系统分析与设计（确定程序功能模块）1、为实现上述程序的功能,应以有序链表表示集合。
基本操作：InitList(&L)操作结果：构造一个空的有序表L。
DestroyList(&L)初始条件：有序表L 已存在。
操作结果：销毁有序表L。
ListEmpty(L)初始条件：有序表L 已存在。
操作结果：若L为空表，则返回TRUE，否则返回FALSE。
ListLength(L)初始条件：有序表L 已存在。
操作结果：返回L 中数据元素个数。
GetElem(L,i)初始条件：有序表L已存在，并且K i< ListLength(L)。
操作结果：返回L 中第i 个数据元素。
LocatePos(L,e)初始条件：有序表L已存在，e和有序表中元素同类型的值。
操作结果：若L中存在和e相同的元素，则返回位置；否则返回0。
数据结构实验报告约瑟夫环约瑟夫环是一个古老而有趣的问题，也是数据结构中一个经典的应用。
它的故事发生在公元前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为报数的次数。
除了链表，还有其他数据结构可以用来解决约瑟夫环问题。
/*据说是华为面试的一道题目:有一个数组a[1000]存放—1000(干扰);要求每隔二个数删掉一个数，到末尾时循环至开头继续进行，求最后一个被删掉的数的原始下标位置。
以个数为例：{0,1,2,3,4,5,6,7} (干扰,其实完全没有必要非得从0-(n-1))0-->1-->2（删除）-->3-->4-->5(删除)-->6-->7-->0（删除），如此循环直到最后一个数被删除。
程序就不写1000数组的了,10个元素吧,解决问题即可*/#include<iostream>#include<assert.h>#include<time.h>usingnamespace std;int deleted(int a[],constint size,constint cnt){assert(a!=NULL&&size>0&&cnt>0);//该for循环并非算法必须for(int i=0;i<size;i++)a[i]=i;int curCnt=0;int Deleted;int DelCnt=0;int flag=-1;do{for(int i=0;i<size;i++){/*在遍历过程中,只要遇到不是flag的数字,计数器+1当计数器=cnt时,删除当前数字(置为flag),将下标记录到delete,同时增加已经删除的个数DelCnt,重置计数器curCnt=0;*/if(a[i]!=flag){curCnt++;if(curCnt==cnt){a[i]=flag;Deleted=i;DelCnt++;curCnt=0;if(size==DelCnt)break;}}//以下代码显示当前数组情况/*for(inti=0;i<size;i++)cout<<a[i]<<",";cout<<endl;*/}}while(size!=DelCnt);return Deleted;}int main(){int b[10]={0,1,2,3,4,5,6,7,8,9};cout<<"最后一个删除的数组元素的下标:"<<deleted(b,10,3)<<endl; system("pause");}/*运行结果:0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,-1,3,4,5,6,7,8,9,0,1,-1,3,4,5,6,7,8,9,0,1,-1,3,4,5,6,7,8,9,0,1,-1,3,4,-1,6,7,8,9, 0,1,-1,3,4,-1,6,7,8,9, 0,1,-1,3,4,-1,6,7,8,9, 0,1,-1,3,4,-1,6,7,-1,9, 0,1,-1,3,4,-1,6,7,-1,9, 0,1,-1,3,4,-1,6,7,-1,9, 0,-1,-1,3,4,-1,6,7,-1,9, 0,-1,-1,3,4,-1,6,7,-1,9, 0,-1,-1,3,4,-1,6,7,-1,9, 0,-1,-1,3,4,-1,6,7,-1,9, 0,-1,-1,3,4,-1,6,7,-1,9, 0,-1,-1,3,4,-1,-1,7,-1,9, 0,-1,-1,3,4,-1,-1,7,-1,9, 0,-1,-1,3,4,-1,-1,7,-1,9,0,-1,-1,3,4,-1,-1,7,-1,9,-1,-1,-1,3,4,-1,-1,7,-1,9, -1,-1,-1,3,4,-1,-1,7,-1,9, -1,-1,-1,3,4,-1,-1,7,-1,9, -1,-1,-1,3,4,-1,-1,7,-1,9, -1,-1,-1,3,4,-1,-1,7,-1,9, -1,-1,-1,3,4,-1,-1,7,-1,9, -1,-1,-1,3,4,-1,-1,7,-1,9, -1,-1,-1,3,4,-1,-1,-1,-1,9, -1,-1,-1,3,4,-1,-1,-1,-1,9, -1,-1,-1,3,4,-1,-1,-1,-1,9, -1,-1,-1,3,4,-1,-1,-1,-1,9, -1,-1,-1,3,4,-1,-1,-1,-1,9, -1,-1,-1,3,4,-1,-1,-1,-1,9, -1,-1,-1,3,4,-1,-1,-1,-1,9, -1,-1,-1,3,-1,-1,-1,-1,-1,9, -1,-1,-1,3,-1,-1,-1,-1,-1,9, -1,-1,-1,3,-1,-1,-1,-1,-1,9, -1,-1,-1,3,-1,-1,-1,-1,-1,9, -1,-1,-1,3,-1,-1,-1,-1,-1,9, -1,-1,-1,3,-1,-1,-1,-1,-1,9, -1,-1,-1,3,-1,-1,-1,-1,-1,9, -1,-1,-1,3,-1,-1,-1,-1,-1,9, -1,-1,-1,3,-1,-1,-1,-1,-1,9,-1,-1,-1,3,-1,-1,-1,-1,-1,9, -1,-1,-1,3,-1,-1,-1,-1,-1,9, -1,-1,-1,3,-1,-1,-1,-1,-1,9, -1,-1,-1,3,-1,-1,-1,-1,-1,9, -1,-1,-1,3,-1,-1,-1,-1,-1,9, -1,-1,-1,3,-1,-1,-1,-1,-1,-1, -1,-1,-1,3,-1,-1,-1,-1,-1,-1, -1,-1,-1,3,-1,-1,-1,-1,-1,-1, -1,-1,-1,3,-1,-1,-1,-1,-1,-1, -1,-1,-1,3,-1,-1,-1,-1,-1,-1, -1,-1,-1,3,-1,-1,-1,-1,-1,-1, -1,-1,-1,3,-1,-1,-1,-1,-1,-1, -1,-1,-1,3,-1,-1,-1,-1,-1,-1, -1,-1,-1,3,-1,-1,-1,-1,-1,-1, -1,-1,-1,3,-1,-1,-1,-1,-1,-1, -1,-1,-1,3,-1,-1,-1,-1,-1,-1, -1,-1,-1,3,-1,-1,-1,-1,-1,-1, -1,-1,-1,3,-1,-1,-1,-1,-1,-1, -1,-1,-1,3,-1,-1,-1,-1,-1,-1, -1,-1,-1,3,-1,-1,-1,-1,-1,-1, -1,-1,-1,3,-1,-1,-1,-1,-1,-1, -1,-1,-1,3,-1,-1,-1,-1,-1,-1, -1,-1,-1,3,-1,-1,-1,-1,-1,-1,-1,-1,-1,3,-1,-1,-1,-1,-1,-1,-1,-1,-1,3,-1,-1,-1,-1,-1,-1,-1,-1,-1,3,-1,-1,-1,-1,-1,-1,-1,-1,-1,3,-1,-1,-1,-1,-1,-1,-1,-1,-1,3,-1,-1,-1,-1,-1,-1,最后一个删除的数组元素的下标:3请按任意键继续. . .*//*下面采用一种新方法来实现在solve Joseph’s problem时,常用的方法是使用链表,但在这个题目中只给定了一个数组,虽然没有说用链表不行,不过能充分利用当前的条件解决问题也是一种好品质,话说回来,谁说链表一定要离散存储了?连续存储的链表不就是数组吗?如果链表节点只有一个NEXT指针,呵呵,数组,纯数组!这个想法,我是从泰安师专崔进平教授在2001年写的一篇《约瑟夫问题的几种算法》中看到的，文中提到了四种方法：1．逻辑数组方法(true,false标记)2．整形数组方法(1,0标记,报数时采用累加求和)3．数组链表方法(这就是下面的程序的思维源泉)4．单循环方法各个方法之间有细微的差别，别的算法我们就不详细介绍了,首先把崔进平教授的数组链表方法写的约瑟夫算法列出来(代码有些老了,看不太明白,直接抄过来的,抄写过程没有文字错误.@_@)PROGRAM joseph3(input,ouput);CONST max=100;VAR a:ARRAY[1..max] OF integer;n,m,I,j,k:integer;BEGINwrite(‘input n,m=);readln(n,m);FOR i:=1 TO n-1 DO a[i]:=i+1;a[n]:=1;k:=n;FOR i:=1 TO n DOBEGINFOR j:=I TO m-1 DO k:=a[k];write(a[k]:5);a[k]:=a[a[k]];IF I mon I0=0 THEN writelnENDEND回到前面的华为笔试题目,结合崔教授的思想,自己用C++语言实现了一下,也方便后来人.同时把崔教授喜欢的i,j,k之类的统统除去了关于I,j,k这样的变量,自己在写程序的时候最好不要跟风,如果不是一个很简单的变量(比如简单的循环过程中的控制变量),变量的命名应该见名知意,否则难以理解,给其他读代码的人造成障碍。
约瑟夫环问题班级：学号：姓名：问题描述：设编号为1，2…，n(n>0)个人按顺时针方向围坐一圈，每人持有一个正整数密码。
开始时任意给出一个报数上限值m，从第一人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺指针方向上的下一个人起重新自1起顺序报数；下去，直到所有人全部出列为止。
要求：设计一个程序模拟此过程。
#include <stdio.h>#include <malloc.h>typedef struct LNode{int number;int password;struct LNode *next;}LNode,*LinkList;LinkList create(int n)//建立一个没有头结点的循环链表{LinkList head,p1,p2;int i;for(i=1;i<=n;i++){p1=(LinkList)malloc(sizeof(LNode));printf("第%d个人的密码为：",i);scanf("%d",&p1->password);p1->number=i;if(i==1)head=p1;elsep2->next=p1;p2=p1;}p2->next=head;return(head);}int main(){LinkList head,p,s;int m,N,j,k,count=0;printf("输入总的人数：");scanf("%d",&N);printf("输入初始密码：");scanf("%d",&m);head=create(N);for(j=N;j>=1;j--){count++;p=head;for(k=1;k<m+j;k++){s=p;p=p->next;}m=p->password;printf("第%d个退出的是编号为%d的人，密码为%d\n",count,p->number,m);s->next=p->next;head=p->next;free(p);}return 0；}运行结果：。
约瑟夫环问题（最简单的数学解法）基本问题描述：已知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即可。
约瑟夫实验报告约瑟夫实验报告约瑟夫实验是一个经典的数学问题，它以约瑟夫斯·弗拉维奥（Josephus Flavius）的名字命名。
约瑟夫是一位古罗马时期的犹太历史学家和将军，他在犹太战争中被困在了一个洞穴里。
为了避免被敌人俘获，他和其他39名战士决定进行一项实验。
实验的规则是这样的：40个人站成一个圆圈，每个人都有一个编号，从1到40。
开始时，约瑟夫被指定为第一个被杀的人，而剩下的人依次按照顺时针方向报数，报数到3的人将被杀死。
然后，从下一个人开始，继续按照同样的规则进行报数，直到只剩下一个人为止。
这个问题的关键在于找到最后一个存活的人的编号。
我们可以通过编写一个简单的程序来解决这个问题。
首先，我们需要创建一个循环链表，其中每个节点都包含一个编号。
然后，我们可以使用一个循环来模拟报数的过程，并在每次报数到3时删除相应的节点。
最后，当链表中只剩下一个节点时，该节点的编号就是最后一个存活的人的编号。
通过对这个问题进行实验，我们可以得出一些有趣的结论。
首先，我们发现无论圆圈中的人数是多少，最后一个存活的人的编号总是1。
这是因为每次删除节点后，剩下的节点会重新排列，而最后一个节点的编号总是1。
其次，我们还发现当圆圈中的人数是2的幂次方时，最后一个存活的人的编号总是2。
这是因为每次删除节点后，剩下的节点会按照一定的规律重新排列，而最后一个节点的编号总是2的幂次方。
这个问题还可以引申出一些其他的数学问题。
例如，我们可以考虑每次报数的步长不是3，而是其他的数字。
我们可以通过修改程序中的报数规则来解决这个问题。
另外，我们还可以考虑圆圈中的人数不是固定的，而是一个变量。
我们可以通过修改程序中的链表长度来解决这个问题。
除了数学问题，约瑟夫实验还可以引发一些关于人性和生存的思考。
在这个实验中，每个人都面临着生与死的抉择。
他们必须决定是坚持到最后，还是在某个时刻选择自杀。
这个实验可以让我们思考人类对生命的珍视和对自身利益的权衡。
实验报告：约瑟夫环问题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。
