《数据结构》上机实验报告—约瑟夫环问题

福州大学数计学院《数据结构》上机实验报告

内容名称

约瑟夫环问题实验报告

约瑟夫问题实验报告 背景 约瑟夫问题（Josephus Problem）据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。原题：用户输入M,N值，N个人围成一个环，从0号人开始数,数到M,那个人就退出游戏，直到最后一个人求最后一个剩下的人是几号？ 问题描述 设编号为1-n的n(n>0)个人按顺时针方向围成一圈．首先第1个人从1开始顺时针报数．报m的人(m 为正整数)．令其出列。然后再从他的下一个人开始，重新从1顺时针报数，报m的人，再令其出列。如此下去，直到圈中所有人出列为止。求出列编号序列。 一.需求分析： (1)基本要求 需要基于线性表的基本操作来实现约瑟夫问题 需要利用循环链表来实现线性表 （2）输入输出格式 输入格式：n，m(n,m均为正整数，) 输出格式1：在字符界面上输出这n个数的输出序列 (3)测试用例（举例） 输入：8，4 输出：4 8 5 2 1 3 7 6 二．概要设计 （1）抽象数据类型： 数据对象：n个整数 数据关系：除第一个和最后一个n外，其余每个整数都有两个元素与该元素相邻。 基本操作：查找，初始化，删除，创建链表 循环链表的存储结构: （2）.算法的基本思想 循环链表基本思想： 先把n个整数存入循环链表中，设置第m个数出列，从第一个开始查找，找到第m个时，输

数据结构实验报告——约瑟夫环问题

一、需求分析 1．本程序要求采用数组的方法，计算并输出约瑟夫环的问题。 2．环中总人数n和数到的数字m由用户输入，m和n为正整数。 3．在Dos 界面输出环中依次被淘汰的人的编号。 4．测试数据 输入10 3 输出 3 6 9 2 7 1 8 5 10 4 二、概要设计 抽象数据类型 为实现上述程序的功能，应以整数存储用户的输入，以及计算出的结果。算法的基本思想 根据题目要求，采用线性表的基本操作来实现约瑟夫环问题。 定义一个数组，用于计算约瑟夫环的位置。先给数组赋值，让数组的每个值就是这个元素的编号，然后定义一个标志k，当K等于N的时 候，表示到达约瑟夫环的最后位置。不停的取数组的下一个元素，如果 这个元素没有被标记为0，说明这个位置还没有被排除，j加1，进入下 一个循环；如果标志K等于n，说明约瑟夫环的循环到达最后一个位置，跳出While死循环。否则，把这个位置的元素设为零，标志它被排除。 最后输出约瑟夫环到达的最后一个位置。 程序的流程 程序由三个模块组成： （1）输入模块：完成两个正整数的输入，存入变量n 和m 中。

（2）计算模块：用循环的方式设计算法计算出依次被淘汰的序列数。 （3）输出模块：屏幕上显示依次被淘汰的人的编号。 三、详细设计 物理数据类型 题目要求输入的正整数的取值范围为正整数，在这里定义为整型即可。 int m，n； 算法的时空分析： 时间复杂度：O（n2）； 空间复杂度：O（n2）； 四、源程序： #include using namespace std; main() { int a[100]; int n; cout<<"请输入环中总人数n："; cin>>n; int m; cout<<"请输入所报数m："; cin>>m; for(int j=0;j

约瑟夫环实验报告

实验一线性表的基本操作及其应用 一、实验目的 1、帮助读者复习C++语言程序设计中的知识。 2、熟悉线性表的逻辑结构。 3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。 二、实验内容和要求 [问题描述] 约瑟夫（Joseph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 [基本要求] 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。[测试数据] 由学生任意指定。 如：m的初值为20；n的值为7；密码：3，1，7，2，4，8，4； （正确的输出结果应为6，1，4，7，2，3，5）。 (报告上要求写出多批数据测试结果) [实现提示] 程序运行后首先要求用户输入初始报数上限值m，人数n,(设n≤30)。然后输入各人的密码。 [选作内容] 向上述程序中添加在顺序结构上实现的部分。 三、算法设计 1、主要思想： 首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环本身具有循环性质，考虑采用循环链表，为了统一对表中任意节点的操作，循环链表不带头结点。循环链表的结点定义为如下结构类型：

typedef struct LNode { int num,pwd; //num存储人的序号，pwd存储人的密码 struct LNode *next; }; 其次，建立一个不带头结点的循环链表并由头指针Head指示。 最后，设计约瑟夫环问题的算法。 2、本程序包含四个模块 1）主函数 void main() { int m,n;//分别为报数上限和人数 printf("\n参数m,n传递报数上限和人数.\n\n请输入m和n：\n"); scanf("%d %d",&m,&n); creatLinkList(n);//带哦用创建链表函数 enterPwd(n);//调用输入密码函数 printf("\n出列的人依次是：\n"); outList(m,n); } 2）创建链表函数creatLinkList()——根据用户输入的人数创建人数相等数量结点的循环链表。 3）输入密码函数enterPwd()——根据用户输入的密码，存入相应结点的数据域pwd； 4）输出出列人的序号函数outList(m,n) 3、核心算法 根据用户输入的报数上限以及人数，在一个循环里面循环和人数相等的次数。这个循环里面还有一个小的循环用于找到每次出列的结点，小循环找到了出列结点的上一个结点。然后记下这个结点，接着去除要出列结点的数据域里的pwd，然后free （）这个结点。开始找下一个出列的结点。 for(i=1;i<=n;i++) //搜索循环链表 { for(a=1;anext; } p=pt->next; m=p->pwd; printf("%d",p->num); //输出人的序号 pt->next=p->next; free(p); //释放动态申请的结点空间 四、调试分析 1、在编译时发现没有导入#include

数据结构-约瑟夫环

约瑟夫环 一.实验目的： 理解线性表的基本逻辑结构，完成链表及循环链表的实现 通过实验进一步理解线性表的逻辑结构和存储结构，提高使用理论知识指导解决实际问题的能力，熟练掌握链表的实际应用。 二.实验内容： 题目：Josephus环问题 问题描述： 约瑟夫(Joseph)问题的一种描述是：编号为1,2,…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。 基本要求： 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 测试数据： m的初值为20;n=7,7个人的密码依次为：3,1,7,2,4,8,4，首先m值为6（正确的出列顺序应为6,1,4,7,2,3,5）。 三. 实验方案（程序设计说明） （一）算法设计思路：

1.利用单循环链表实现该程序的目的； 2.实现过程：创建单循环链表--信息从尾部插入--遍历链表找出目标—删除操作杀害; （二）算法流程图：

（三）界面设计说明：请输入第一个密码m：

请输入人数n： 请输入n个数： 被杀害的顺序为： （四）使用模块及变量的说明 实验：m→密码；n→人数； 四. 实验步骤或程序（经调试后正确的源程序） 实验：（约瑟夫环） #include "stdafx.h" #include using namespace std; typedef struct lnode { int data; int in; struct lnode*next; } LNode, *LinkList; LinkList Creat(LinkList L, int n); //创建单循环链表void Del(LinkList L, int M, int k); void main() { int M, n; printf("\n请输入第一次M的值:");

约瑟夫环数据结构实验报告

数据结构实验报告----约瑟夫环 一、需求分析： 约瑟夫环是程序的一道经典例题，可以使用数据结构的单链表进行编写。 二、概要设计： 大体上可以使用单链表通过节点的创建和删除来达到人数出列的效果，可以大大缩短程序量。 三、详细设计： 1、首先定义一个单链表，然后分别做创建链表、以及对应的输入数据，删除节点对应的删除数据，以及输出功能。最后用主函数实现上述功能。 下为程序源代码： #include #include typedef struct Lnode //创建一个单链表 { int num; int key; struct Lnode *next; }Joseph; struct Lnode *head,*p,*p1; int creatlinklist(int n) //为节点分配内存，创建节点 { int i=0; head = (struct Lnode*)malloc(sizeof(struct Lnode)); if(!head) { return 0; } p=head; for(i = 0;inext=p1; p=p1; } p->next=head; p1=head; return 0; }

int input(int n) //在分配的节点上输入数据 { int i=0; int j=0; printf("please input the keys:\n"); for(i =1;inum=i; p1->key=j; p1=p1->next; } p1=p; return j; } int output(int m,int n) \\在约瑟夫环的规定上输出数据删除节点{ int i=0; int a=0; for(i =0;i next; } p=p1->next; m=p->key; printf("%d\n",p->num); p1->next=p->next; free(p); } return 0; } void main() { int m=0; int n=0; printf("请输入上限值和人数值：\n"); scanf("%d%d",&m,&n); creatlinklist(n); input(n);

约瑟夫环 实验报告

约瑟夫环实验报告 约瑟夫环实验报告 引言： 约瑟夫环是一个经典的数学问题，它源自于古代传说。根据传说，古代犹太人 被罗马人围困在一个洞穴中，他们决定用一种特殊的方式来决定谁将成为首领。他们站成一个圆圈，从一个人开始，每隔一个人杀掉一个，直到只剩下一个人。这个问题被称为约瑟夫环问题，它在数学领域引起了广泛的研究和探讨。 实验目的： 本实验旨在通过模拟约瑟夫环问题，探讨其数学规律和解法，并分析实验结果 的意义和应用。 实验步骤： 1. 首先，我们需要确定参与约瑟夫环的人数n和每次报数的间隔m。在本次实 验中，我们选择了n=10和m=3。 2. 接下来，我们将10个人按顺序排成一个圆圈，并给每个人编号，编号从1到10。 3. 实验开始时，从第一个人开始报数，每次报数到m的人将被淘汰出局。 4. 淘汰的人将离开圆圈，下一个人将从淘汰者的下一个人开始报数，继续进行 报数和淘汰的过程，直到只剩下一个人为止。 实验结果： 通过模拟实验，我们得到了以下结果： - 第一轮淘汰的人依次为：3、6、9、2、7、1、8、5、10。 - 第二轮淘汰的人依次为：4、9、2、8、5、1、7、6。

- 第三轮淘汰的人依次为：9、8、5、1、7、4、6。 - 第四轮淘汰的人依次为：1、7、4、6、9、5。 - 第五轮淘汰的人依次为：7、4、6、9、5。 - 第六轮淘汰的人依次为：4、6、9、5。 - 第七轮淘汰的人依次为：6、9、5。 - 第八轮淘汰的人依次为：9、5。 - 第九轮淘汰的人依次为：5。 结论： 通过实验结果的分析，我们可以得出以下结论： 1. 在本次实验中，最后幸存的人是编号为5的人。 2. 根据实验结果，我们可以总结出约瑟夫环问题的一般解法。假设总人数为n，每次报数的间隔为m，最后幸存的人的编号可以通过递归公式f(n,m)=[f(n- 1,m)+m]%n得到。 3. 约瑟夫环问题在数学中具有一定的研究价值和应用意义。它涉及到递归、数 论等数学概念和方法，可以帮助我们更好地理解和应用这些数学知识。 进一步探讨： 除了基本的约瑟夫环问题，还有一些相关的变体问题值得进一步探讨和研究。 例如，可以考虑不同的报数规则、不同的初始位置等条件下的约瑟夫环问题。 此外，还可以研究约瑟夫环问题在实际生活中的应用，例如在计算机科学、密 码学等领域的应用。 总结： 通过本次约瑟夫环实验，我们深入了解了这个经典数学问题的规律和解法。实

数据结构实验报告约瑟夫环

数据结构实验报告约瑟夫环 约瑟夫环是一种经典的数学问题，它源于古代传说中的故事。根据传说，约瑟 夫是一位犹太历史学家，他和他的朋友们被罗马军队包围在一个洞穴里。为了 避免被俘虏，他们决定自杀，但是他们决定以一个特殊的方式来做。他们围成 一个环，从一个人开始，每隔一个人就杀死一个，直到只剩下一个人。约瑟夫 是最后一个幸存者。 这个问题可以用数据结构来解决，其中最常用的方法是使用循环链表。循环链 表是一种特殊的链表，它的最后一个节点指向第一个节点，形成一个环。 在解决约瑟夫环问题时，我们可以使用循环链表来模拟这个环。首先，我们需 要创建一个循环链表，并将所有的人依次添加到链表中。然后，我们需要设置 一个计数器，用来记录当前的位置。接下来，我们需要遍历链表，每次遍历到 计数器所指向的位置时，将该节点从链表中删除，并将计数器加一。当计数器 的值等于要删除的位置时，我们就将该节点删除，并将计数器重置为1。重复 这个过程，直到链表中只剩下一个节点为止。 通过使用循环链表，我们可以很方便地解决约瑟夫环问题。这种方法的时间复 杂度为O(n*m)，其中n表示初始链表的长度，m表示要删除的位置。由于每次删除一个节点后，链表的长度会减少，所以实际上的时间复杂度会小于O(n*m)。除了使用循环链表，还可以使用数组来解决约瑟夫环问题。我们可以创建一个 长度为n的数组，然后将所有的人依次添加到数组中。接下来，我们需要设置 一个计数器，用来记录当前的位置。然后，我们需要遍历数组，每次遍历到计 数器所指向的位置时，将该人从数组中删除，并将计数器加一。当计数器的值 等于要删除的位置时，我们就将该人删除，并将计数器重置为1。重复这个过

数据结构实验报告约瑟夫环

数据结构实验报告约瑟夫环 约瑟夫环是一个经典的问题，涉及到数据结构中的循环链表。在本次数据结构 实验中，我们将学习如何使用循环链表来解决约瑟夫环问题。 约瑟夫环问题最早出现在古代，传说中的犹太历史学家约瑟夫斯·弗拉维奥（Josephus Flavius）在围攻耶路撒冷时，为了避免被罗马人俘虏，与其他39名犹太人躲进一个洞穴中。他们决定宁愿自杀，也不愿被敌人俘虏。于是，他们 排成一个圆圈，从第一个人开始，每次数到第七个人，就将他杀死。最后剩下 的人将获得自由。 在这个问题中，我们需要实现一个循环链表，其中每个节点表示一个人。我们 可以使用一个整数来表示每个人的编号。首先，我们需要创建一个循环链表， 并将所有人的编号依次添加到链表中。 接下来，我们需要使用一个循环来模拟每次数到第七个人的过程。我们可以使 用一个指针来指向当前节点，然后将指针移动到下一个节点，直到数到第七个 人为止。一旦数到第七个人，我们就将该节点从链表中删除，并记录下该节点 的编号。然后，我们继续从下一个节点开始数数，直到只剩下一个节点为止。 在实现这个算法时，我们可以使用一个循环链表的数据结构来表示约瑟夫环。 循环链表是一种特殊的链表，其中最后一个节点的指针指向第一个节点。这样，我们就可以实现循环遍历链表的功能。 在实验中，我们可以使用C语言来实现循环链表和约瑟夫环算法。首先，我们 需要定义一个节点结构体，其中包含一个整数字段用于存储编号，以及一个指 针字段用于指向下一个节点。然后，我们可以实现创建链表、添加节点、删除 节点等基本操作。

接下来，我们可以编写一个函数来实现约瑟夫环算法。该函数接受两个参数，分别是参与游戏的人数和每次数到第几个人。在函数内部，我们可以创建一个循环链表，并将所有人的编号添加到链表中。然后，我们可以使用一个循环来模拟每次数到第几个人的过程，直到只剩下一个节点为止。在每次数到第几个人时，我们可以删除该节点，并记录下其编号。最后，我们可以返回最后剩下的节点的编号。 通过实验，我们可以学习到循环链表在解决约瑟夫环问题中的应用。循环链表是一种非常灵活的数据结构，可以用于解决各种循环相关的问题。同时，通过实际编程实践，我们可以加深对数据结构的理解和应用能力。 总之，约瑟夫环是一个有趣而经典的问题，通过使用循环链表来解决，我们可以学习到循环链表的基本操作和应用。通过实验，我们可以加深对数据结构的理解，并提高我们的编程能力。希望本次实验能够帮助大家更好地掌握数据结构的知识。

数据结构约瑟夫环实验报告

数据结构约瑟夫环实验报告 数据结构约瑟夫环实验报告 引言： 数据结构是计算机科学中的重要概念，它涉及如何组织和存储数据以便有效地 使用。约瑟夫环是一种经典的数据结构问题，它涉及到一个有序的列表，以及 在列表中进行操作的规则。在本次实验中，我们将探索约瑟夫环的概念，并通 过编写程序来模拟和解决约瑟夫环问题。 背景： 约瑟夫环问题源于一个古老的传说，故事中有一群囚犯被困在一个圆形的牢房中。为了避免被敌人发现，囚犯们决定采取一种特殊的方式来决定谁将被处决。开始时，他们围成一个圆圈，从一个固定的位置开始数，每次数到一个固定的 数字，该数字的人将被处决。然后，从被处决的人开始重新数数，直到只剩下 一个人。 实验过程： 为了模拟约瑟夫环问题，我们首先需要创建一个循环链表。循环链表是一种特 殊的链表，其最后一个节点指向第一个节点，形成一个环形结构。在这个环形 链表中，我们将存储囚犯的信息，包括编号和姓名。 在编写程序之前，我们需要定义一些参数。首先，我们需要确定囚犯的总人数 和每次数数的数字。这些参数可以根据实际情况进行调整。接下来，我们需要 定义一个起始位置，即从哪个囚犯开始数数。 在创建循环链表后，我们将开始模拟约瑟夫环问题。我们将从起始位置开始数数，每当数到指定的数字时，我们将删除当前节点，并将数数的位置移动到下

一个节点。这个过程将一直进行，直到只剩下一个节点为止。 结果与分析： 通过运行程序，我们可以得到约瑟夫环问题的解。最后一个幸存的囚犯的编号 将被输出。通过不同的参数设置，我们可以观察到不同的结果。 在实验过程中，我们还可以观察到一些有趣的现象。例如，当囚犯的总人数和 每次数数的数字相等时，最后一个幸存的囚犯将是初始位置的囚犯。这是因为 每次数数后，数数的位置都会移动到下一个节点，因此初始位置的囚犯将是最 后一个被删除的节点。 此外，我们还可以观察到约瑟夫环问题的时间复杂度。在每次删除节点时，我 们需要遍历整个链表以找到要删除的节点。因此，如果囚犯的总人数很大，这 个过程可能会非常耗时。为了提高效率，我们可以使用其他数据结构，如数组 或矩阵来解决约瑟夫环问题。 结论： 通过本次实验，我们深入了解了约瑟夫环问题以及相关的数据结构概念。我们 通过编写程序模拟了约瑟夫环问题，并观察到了不同参数设置下的结果。我们 还讨论了约瑟夫环问题的时间复杂度，并提出了一些优化的思路。 数据结构是计算机科学中的重要概念，它在解决实际问题中起着关键的作用。 通过学习和应用数据结构，我们可以更好地组织和管理数据，提高算法的效率。在今后的学习和工作中，我们将继续深入研究数据结构，并将其应用于实际问 题的解决中。

约瑟夫环数据结构实验报告

约瑟夫环数据结构实验报告 约瑟夫环数据结构实验报告 引言 约瑟夫环是一种经典的数学问题，它涉及到一个有趣的数据结构。本次实验旨 在通过实现约瑟夫环数据结构，深入理解该问题，并探索其在实际应用中的潜力。本报告将介绍实验的设计和实现过程，并分析实验结果。 实验设计 在本次实验中，我们选择使用链表来实现约瑟夫环数据结构。链表是一种非常 灵活的数据结构，适合用于解决约瑟夫环问题。我们设计了一个Josephus类，其中包含了创建环、添加元素、删除元素等操作。 实验实现 1. 创建环 在Josephus类中，我们首先需要创建一个循环链表。我们使用一个头节点来表示环的起始位置。在创建环的过程中，我们可以选择指定环的长度和起始位置。 2. 添加元素 在创建环之后，我们可以通过添加元素来向约瑟夫环中插入数据。我们可以选 择在环的任意位置插入元素，并且可以动态地调整环的长度。 3. 删除元素 根据约瑟夫环的规则，每次删除一个元素后，下一个元素将成为新的起始位置。我们可以通过删除元素的操作来模拟约瑟夫环的运行过程。在删除元素时，我 们需要考虑环的长度和当前位置。 实验结果

通过实验，我们得出了以下结论： 1. 约瑟夫环数据结构可以有效地模拟约瑟夫环问题。通过创建环、添加元素和删除元素的操作，我们可以模拟出约瑟夫环的运行过程，并得到最后剩下的元素。 2. 约瑟夫环数据结构具有一定的应用潜力。除了解决约瑟夫环问题，该数据结构还可以用于其他类似的问题，如任务调度、进程管理等。 3. 约瑟夫环数据结构的时间复杂度较低。由于约瑟夫环的特殊性质，我们可以通过简单的链表操作来实现该数据结构，使得其时间复杂度较低。 结论 本次实验通过实现约瑟夫环数据结构，深入理解了该问题，并探索了其在实际应用中的潜力。通过创建环、添加元素和删除元素的操作，我们可以模拟出约瑟夫环的运行过程，并得到最后剩下的元素。约瑟夫环数据结构具有一定的应用潜力，并且具有较低的时间复杂度。通过本次实验，我们对数据结构的设计和实现有了更深入的理解，并为将来的研究和应用奠定了基础。

约瑟夫问题数据结构实验报告

约瑟夫问题数据结构实验报告 [正文] 1.实验目的 本实验的目的是分析约瑟夫问题，并设计合适的数据结构解决 该问题。 2.实验背景 约瑟夫问题，又称为约瑟夫环，是一个经典的数学问题。问题 描述如下： 有n个人围成一圈，从第一个人开始报数，数到第m个人时将 其杀死，然后从下一个人开始重新报数，数到第m个人又将其杀死，如此循环进行，直到所有人都被杀死为止。求出最后一个被杀的人 在初始序列中的编号。 3.实验设计 为了解决约瑟夫问题，我们需要设计合适的数据结构来表示这 个过程。以下为实验所采用的数据结构： 3.1 线性表

由于约瑟夫问题是围成一圈的，因此我们选择使用循环链表来表示人围成的圈。每个节点代表一个人，包含一个成员变量用于存储人的编号。 3.2 算法 采用如下算法来解决约瑟夫问题： 1.创建一个循环链表，将n个人的编号分别存入节点中。 2.初始化一个指针p指向链表的第一个节点。 3.从第一个人开始报数，每报到第m个人，将该节点从链表中删除。 4.如果链表中只剩下一个节点，此时的节点即为最后一个被杀的人，输出其编号。 4.实验步骤 4.1 数据结构设计 根据实验设计中的描述，我们编写了一个含有循环链表和节点的数据结构。 ```cpp struct ListNode { int number;

ListNode next; }; ``` 4.2 实现约瑟夫问题算法 根据实验设计中的算法描述，我们编写了解决约瑟夫问题的函数。 ```cpp int josephusProblem(int n, int m) { // 创建循环链表 // 初始化指针p // 开始报数并删除节点 // 返回最后被杀的人的编号 } ``` 4.3 测试与分析 我们通过输入不同的n和m值，测试了约瑟夫问题的解决函数，并对实验结果进行了分析。

数据结构实验报告约瑟夫环

数据结构实验报告约瑟夫环 约瑟夫环是一个古老而有趣的问题，也是数据结构中一个经典的应用。它的故 事发生在公元前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为报数的次数。

顺序表实现约瑟夫环的问题,C语言

顺序表实现约瑟夫环的问题,C语言 计算机科学与工程学院 《算法与数据结构》试验报告[一] 专业班级 10级计算机工程02 试验地点 计算机大楼计工教研室学生学号 1005080222 指导教师蔡琼学生姓名肖宇博试验时间 2012-2-29 试验项目算法与数据结构 试验类别基础性() 设计性() 综合性(?) 其它( ) (1)掌握用VC++上机调试线性表的基本方法; 试(2)掌握顺序表的存储结构以及基本运算的实现。验 目 的 及 要 求 成绩评定表 类别评分标准分值得分合计 积极出勤、遵守纪律 上机表现 30分 主动完成设计任务 程序代码规范、功能正确 程序与报告 70分 报告详实完整、体现收获

备注: 评阅教师: 日期: 年月日 计算机科学与工程学院 试验内容 一、实验目的和要求 1、实验目的: (1)掌握用VC++上机调试线性表的基本方法; (2)掌握顺序表的存储结构以及基本运算的实现。 2、实验内容 约瑟夫环问题:设编号为1，2，3，……，n的n(n>0)个人按顺 时针方向围坐一圈，m为任意一个正整数。从第一个人开始顺时针 方向自1起顺序报数，报到m时停止并且报m的人出列，再从他的 下一个人开始重新从1报数，报到m时停止并且报m的人出列。如 此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程， 对任意给定的m和n，求出出列编号序列。 3、实验要求:用顺序表实现。 二、设计分析 根据实验要求，采用顺序表来完成本次实验。 实验中定义了两个顺序表，一个用来存储n个人的序号，另一个用来存储n个人的出队顺序及序号。 程序中充分考虑了如果出队的元素大于队列的元素个数时应该有的情况，如果出现这样的错误就提示～否则继续出队～ 三、源程序代码

数据结构实验报告1约瑟夫环

一、上机实验的问题和要求： 约瑟夫环 问题描述：编号是1,2,…,n(n>0)的n个人按照顺时针方向围坐一圈，每人持有一正整数密码。开始时任选一个正整数作为报数上限值m，从某个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。令n最大值取30。设计一个程序来求出出列顺序，并输出结果。 基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各人的编号。 二、程序设计的基本思想，原理和算法描述： （包括程序的结构，数据结构，输入/输出设计，符号名说明等） （1）算法的基本思想： 约瑟夫环问题中的数据是人所在的位置，而这种数据是存在“第一元素、最后元素”，并且存在“唯一的前驱和后继的”，符合线性表的特点。由于需要模拟约瑟夫环的出列问题，可以采用顺序表来实现线性表，完成出列顺序的输出。 核心算法主要分为两步： 1、确定需要删除的位置， 2、设置并删除该位置。 已知报数间隔m，我们可以把当前位置加上m获得需要删除的位置，如果获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际长度来修正（即模拟环状计数）。然后把顺序表中的当前指向位置设置为该位置，继而删掉该位置。 反复进行上述确定位置和删除位置的操作，直到顺序表为空。 （2）主程序的流程： 程序由三个模块组成： 1、输入模块：无提示语句，直接输入总人数n和报数次数m，中间用逗 号隔开。 2、处理模块：将元素储存于顺序表中。在主函数中根据报数间隔确定需 要删除的元素的位置，在顺序表中设置该位置并删除该位置，同时输出该位置的值。反复设置并删除直到表空。 3、输出模块：分别在DOS下和文件中，按移除元素的顺序依次显示其 位置。 （3）各程序模块之间的层次（调用）关系： 主函数会按设计的方法调用顺序表中“获取实际长度”、“设置需要删除元素的位置”、“移除该位置元素”和“判断是否为空表”四种方法方法，使元素依次出列，并正确结束程序。

数据结构上机实验报告—约瑟夫环问题

福州大学数计学院 《数据结构》上机实验报告 学号姓名成绩 实验名称线性表结构及其 应用 实验内容约瑟夫环问题 实验目的和要求【实验目的】 利用单向循环链表解决约瑟夫环问题，提高综合设计能力。 【基本要求】 利用单向循环链表存储结构模拟此过程，按归口炪列的顺序印出各人的编号。 问题描述和主要步骤【问题描述】 约瑟夫问题：编号为1，2，..n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 【主要程序】 #include #include typedef struct node { int number; int pwd; struct node * next; }Node, *Link; Link Init(void) { Link L; L = (Link)malloc(sizeof(Node)); L->next = L; return L; } void Insert(Link L, int e_pwd, int e_number) { Link p,q; p = (Link)malloc(sizeof(Node)); p->pwd = e_pwd; p->number = e_number;

q = L; while(q->next != L)q = q->next; p->next = q->next; q->next = p; } void Delete(Link L, int i) { Link p,q; q = L; while(q->next != q && q->next->number != i) q = q->next; if(q->next->number == i) {p = q->next; q->next = p->next; free(p); } } void main() { Link p,q,L; int i,m,n,pwd; printf("请输入参与人数与初始值："); scanf("%d%d",&n,&m); if(n<=0 || m<=0) return; L = Init(); i=1; while(i<=n) { printf("请输入第%d个人的密码：",i); scanf("%d",&pwd); if(pwd <= 0)continue; Insert(L, pwd, i); i++; } i = 1; p = L->next; while(L->next != L) { q = p; p = p->next; if(p ==L) { q = p; p = p->next; } i++; if(i == m) {

工作报告之约瑟夫环实验报告总结

约瑟夫环实验报告总结 【篇一：约瑟夫环实验报告】 实验报告 课程名称：数据结构 实验名称：顺序表和链表的应用 实验编号：实验一 指导教师： 一、实验目的 （1）掌握线性表的基本操作（插入、删除、查找）以及线性表合 并等运算在顺序存储结 构、链式存储结构上的实现。重点掌握链式存储结构实现的各种操作。 （2）掌握线性表的链式存储结构的应用。 二、实验内容与实验步骤 （1）实验内容： 实现约瑟夫环，约瑟夫环（joseph）问题的一种描述是：编号为1、2、3……n的n个人按照顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一 个人开始按照顺时针的方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的 下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。设计一个程序求出出列顺序。 （2）抽象数据类型和设计的函数描述，说明解决设想。 首先定义一个链表，用其中的data项存储每个人的编号，用password项存储每个人所持有的密码，并且声明一个指针。之后使用creatlist_cl函数来创建一个循环链表，在其中的data和password中存入编号和密码，最后使最后一个节点的next指向l，使其能够形成循环队列。定义了函数display来显示链表当中的内容，以确定存储的数据没有错误。定义了函数delete_l来实现约瑟夫环 中依次删除的功能，依次比较，如果某个人所持的密码和m值相等，则删除这个结点，并且输出此时该结点的编号和密码，实现出列的 功能。 （3）简短明确地写出实验所采用的存储结构，并加以说明。