数据结构约瑟夫环问题

约瑟夫环问题问题描述：有n个⼈，编号分别从0到n-1排列，这n个⼈围成⼀圈，现在从编号为0的⼈开始报数，当报到数字m的⼈，离开圈⼦，然后接着下⼀个⼈从0开始报数，依次类推，问最后只剩下⼀个⼈时，编号是多少？分析：这就是著名的约瑟夫环问题，关于来历不再说明，这⾥直接分析解法。

解法⼀：蛮⼒法。

我曾将在⼤⼀学c语⾔的时候，⽤蛮⼒法实现过，就是采⽤标记变量的⽅法即可。

解法⼀：循环链表法。

从问题的本质⼊⼿，既然是围成⼀个圈，并且要删除节点，显然符合循环链表的数据结构，因此可以采⽤循环链表实现。

解法三：递推法。

这是⼀种创新的解法，采⽤数学建模的⽅法去做。

具体如下：⾸先定义⼀个关于n和m的⽅程f(n,m)，表⽰每次在n个编号0，1，...，n-1中每次删除的报数为m后剩下的数字，在这n个数字中，第⼀个被删除的数字是(m-1)%n，为了简单，把(m-1)%n记作k，那么删除k之后剩下的数字为0，1，2，...，k-1，k+1，...，n-1并且下⼀次删除的数字从k+1开始计数，这就相当于剩下的序列中k+1排在最前⾯，进⽽形成k+1,..,n-1,0,1,2,...,k-1这样的序列，这个序列最后剩下的数字应该和原序列相同，由于我们改变了次序，不能简单的记作f(n-1,m),我们可以记作g(n-1,m),那么就会有f(n,m)=g(n-1,m).下⼀步，我们把这n-2个数字的序列k+1,..,n-1,0,1,2,...,k-1做⼀个映射，映射的结果是形成⼀个从0到n-2的序列。

k+1对0，k+2对1，......，n-1对n-k-2，0对n-k-1，1对n-k，....，k-1对n-2这样我们可以把这个映射定义为p,则p(x)=(x-k-1)%n,它表⽰如果映射前的数字是x，映射后为(x-k-1)%n,从⽽这个映射的反映射问为p-1(x)=(x+k+1)%n由于映射之后的序列和原始序列具有相同的形式，都是从0开始的序列，所以可以⽤函数f来表⽰，即为f(n-1,m)，根据映射规则有：g(n-1,m)=p-1[f(n-n,m)]=[f(n-1,m)+k+1]%n,最后把之前的k=(m-1)%n带⼊式⼦就会有f(n,m)=g(n-1,m)=[f(n-1,m)+m]%n.这样我们就可以得出⼀个递推公式，当n=1时，f(n,m)=0;当n>1时，f(n,m)=[f(n-1,m)+m]%n;有了这个公式，问题就变得多了。

2009级数据结构实验报告实验名称：实验线性表实现约瑟夫问题求解学生姓名：桂柯易班级：2009211120班内序号：07学号：09210580日期：2010年10月31日1.实验要求【实验目的】1．熟悉C++语言的基本编程方法,掌握集成编译环境的调试方法；2．学习指针、模板类、异常处理的使用；3．掌握线性表的操作实现方法；4．培养使用线性表解决实际问题的能力。

【实验内容】利用循环链表实现约瑟夫问题的求解。

约瑟夫问题如下：已知n个人（n>=1）围坐一圆桌周围，从1开始顺序编号。

从序号为1的人开始报数，顺时针数到m的那个人出列。

他的下一个人又从1开始报数，数到m 的那个人又出列。

依此规则重复下去，直到所有人全部出列。

请问最后一个出列的人的编号。

2.程序分析2.1 存储结构存储结构：循环链表2.2 关键算法分析【设计思想】首先，设计实现约瑟夫环问题的存储结构。

由于约瑟夫环本身具有循环性质，考虑采用循环链表，为了统一对表中任意节点的操作，循环链表不带头结点。

循环链表的结点定义为如下结构类型：struct Node{int number;Node *next;};其次，建立一个不带头结点的循环链表并由头指针first指示。

最后，设计约瑟夫环问题的算法。

【伪代码】1、工作指针first，r，s，p，q初始化2、输入人数（n）和报数（m）3、循环n次，用尾插法创建链表Node *q;for(int i=1;i<=n;i++){Node *p;p=new Node;p->number=i;p->next=NULL;if(i==1) L=q=p;else{q->next=p;q=q->next;}}q->next=L;if(L!=NULL){return(L);}4、输入报数的起始人号数k;5、Node *q = new Node;计数器初始化i=1;6、循环n次删除结点并报出位置（其中第一个人后移k个）当i<n时移动指针m-2次p=p->next;删除p结点的后一结点qq=p->next;p->next=q->next;*L = p->next;报出位置后Delete q;计数器i++;【复杂度】for(int i=1;i<=n;i++){Node *p;p=new Node;p->number=i;p->next=NULL;if(i==1) L=q=p;else{q->next=p;q=q->next;}时间复杂度：O（n）if(i==1) i+=LengthList(*L);Node *p;p=*L;int j=0;while(j<i-2) {p=p->next;j++;}q = p->next;p->next=p->next->next;*L = p->next;return(q);时间复杂度：O（n2）算法的空间复杂度：O（n2）2.3 其他程序源代码：#include<iostream>using namespace std;struct Node//循环节点的定义{int number;//编号Node *next;};Node *CreateList(Node *L,int &n,int &m);//建立约瑟夫环函数void Joseph(Node *L,int n,int m);//输出每次出列号数函数Node *DeleteList(Node **L,int i,Node *q);//寻找每次出列人的号数int LengthList(Node *L);//计算环上所有人数函数void main()//主函数{Node *L;L=NULL;//初始化尾指针int n, m;cout<<"请输入人数N：";cin>>n;//环的长度if(n<1){cout<<"请输入正整数!";}//人数异常处理else{cout<<"请输入所报数M：";cin>>m;if(m<1){cout<<"请输入正整数!";}//号数异常处理else{L=CreateList(L,n,m);//重新给尾指针赋值Joseph(L,n,m);}}system("pause");}Node *CreateList(Node *L,int &n,int &m)//建立一个约瑟夫环（尾插法）{Node *q;for(int i=1;i<=n;i++){Node *p;p=new Node;p->number=i;p->next=NULL;if(i==1) L=q=p;//工作指针的初始化else{q->next=p;q=q->next;}}q->next=L;if(L!=NULL){return(L);}//返回尾指针else cout<<"尾指针异常!"<<endl;//尾指针异常处理}void Joseph(Node *L,int n,int m)//输出每次出列的人{int k;cout<<"请输入第一个报数人：";cin>>k;if(k<1||k>n){cout<<"请输入1-"<<n<<"之间的数"<<endl;} else{cout<<"\n出列顺序:\n";for(int i=1;i<n;i++){Node *q = new Node;if(i==1) q=DeleteList(&L,k+m-1,q);//第一个出列人的号数else q=DeleteList(&L,m,q);cout<<"号数："<<q->number<<endl;delete q;//释放出列人的存储空间}cout<<"最后一个出列号数是："<<L->number<<endl;;//输出最后出列人的号数}}Node *DeleteList(Node **L,int i,Node *q) //寻找每次出列的人{if(i==1) i+=LengthList(*L);//顺序依次出列情况的处理方式Node *p;p=*L;int j=0;while(j<i-2) {p=p->next;j++;}q = p->next;p->next=p->next->next;*L = p->next;return(q);}int LengthList(Node *L)//计算环上的人数{if(L){cout<<"尾指针错误!"<<endl;}//异常处理else{int i=1;Node *p=L->next;while(p!=L){i++;p=p->next;}return(i);}}3.程序运行结果1.测试主函数流程：2.测试条件：如上图所示，人数为20人，所报数为6，第一个报数的人是1号。

约瑟夫环数据结构实验报告约瑟夫环数据结构实验报告引言约瑟夫环是一种经典的数学问题，它涉及到一个有趣的数据结构。

本次实验旨在通过实现约瑟夫环数据结构，深入理解该问题，并探索其在实际应用中的潜力。

本报告将介绍实验的设计和实现过程，并分析实验结果。

实验设计在本次实验中，我们选择使用链表来实现约瑟夫环数据结构。

链表是一种非常灵活的数据结构，适合用于解决约瑟夫环问题。

我们设计了一个Josephus类，其中包含了创建环、添加元素、删除元素等操作。

实验实现1. 创建环在Josephus类中，我们首先需要创建一个循环链表。

我们使用一个头节点来表示环的起始位置。

在创建环的过程中，我们可以选择指定环的长度和起始位置。

2. 添加元素在创建环之后，我们可以通过添加元素来向约瑟夫环中插入数据。

我们可以选择在环的任意位置插入元素，并且可以动态地调整环的长度。

3. 删除元素根据约瑟夫环的规则，每次删除一个元素后，下一个元素将成为新的起始位置。

我们可以通过删除元素的操作来模拟约瑟夫环的运行过程。

在删除元素时，我们需要考虑环的长度和当前位置。

实验结果通过实验，我们得出了以下结论：1. 约瑟夫环数据结构可以有效地模拟约瑟夫环问题。

通过创建环、添加元素和删除元素的操作，我们可以模拟出约瑟夫环的运行过程，并得到最后剩下的元素。

2. 约瑟夫环数据结构具有一定的应用潜力。

除了解决约瑟夫环问题，该数据结构还可以用于其他类似的问题，如任务调度、进程管理等。

3. 约瑟夫环数据结构的时间复杂度较低。

由于约瑟夫环的特殊性质，我们可以通过简单的链表操作来实现该数据结构，使得其时间复杂度较低。

结论本次实验通过实现约瑟夫环数据结构，深入理解了该问题，并探索了其在实际应用中的潜力。

通过创建环、添加元素和删除元素的操作，我们可以模拟出约瑟夫环的运行过程，并得到最后剩下的元素。

约瑟夫环数据结构具有一定的应用潜力，并且具有较低的时间复杂度。

通过本次实验，我们对数据结构的设计和实现有了更深入的理解，并为将来的研究和应用奠定了基础。

第二章习题1. 描述以下三个概念的区别：头指针，头结点，首元素结点。

2. 填空：（1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。

（2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。

在单链表中，逻辑上相邻的元素，其物理位置相邻。

（3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。

3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。

按要求从下列语句中选择合适的语句序列。

a. 在P结点后插入S结点的语句序列是：。

b. 在P结点前插入S结点的语句序列是：。

c. 在表首插入S结点的语句序列是：。

d. 在表尾插入S结点的语句序列是：。

供选择的语句有：（1）P->next=S;（2）P->next= P->next->next;（3）P->next= S->next;（4）S->next= P->next;（5）S->next= L;（6）S->next= NULL;（7）Q= P;（8）while(P->next!=Q) P=P->next;（9）while(P->next!=NULL) P=P->next;（10）P= Q;（11）P= L;（12）L= S;（13）L= P;4. 设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。

试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。

5. 写一算法，从顺序表中删除自第i个元素开始的k个元素。

6. 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。

试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。

《数据结构》课程设计报告书题目：约瑟夫环系别：计算机科学与应用学号：学生姓名：指导教师：完成日期：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。

一、算法设计题（每题15分，共60分）答题要求：①用自然语言说明所采用算法的思想；②给出每个算法所需的数据结构定义，并做必要说明；③写出对应的算法程序，并做必要的注释。

1、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指针域next。

假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留一个。

3、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此重复直到所有的人全部出列为止。

现要求采用循环链表结构设计一个算法，模拟此过程。

4、编程实现单链表的就地逆置。

23．在数组 A[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个.5、设计一个尽可能的高效算法输出单链表的倒数第K个元素。

3、假设以I和O分别表示入栈和出栈操作。

栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。

（15分）（1）下面所示的序列中哪些是合法的？A. IOIIOIOOB. IOOIOIIOC. IIIOIOIOD. IIIOOIOO（2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。

若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。

5、设从键盘输入一整数的序列：a1, a2, a3，…，an,试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。

算法应对异常情况（入栈满等）给出相应的信息。

设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1，W2，...，W n。