约瑟夫环问题-数据结构实现代码

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

基础成绩：82分《数据结构》课程实验 实验报告 题目：Joseph问题求解算法的设计与实现 专业：网络工程 班级：网络102 姓名：张晨曦 学号： 102534 完成日期：2012/6/20 一、试验内容

- 约瑟夫（Joseph）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 二、试验目的 掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。 三、流程图 struct list {

- int num,code; struct list *next; }; void main() { printf("Joseph问题求解算法的设计与实现\n \n"); int i,j,m=1; int key; // 密码. int n; //人数. list *p,*s,*head; head=(list *)malloc(sizeof(list)); //为头结点分配空间. p=head; //使指针指向头节点 printf("输入人的总个数:"); scanf("%d",&n); for(i=1;i<=n;i++) { printf("第%d个人的密码:\n",i); scanf("%d",&key); s=p; p=(list *)malloc(sizeof(list)); //创建新的结点. s->next=p; p->num=i; p->code=key; } p->next=head->next; p=head; head=head->next; free(p); //释放头结点. p=head; printf("\n\n输入初始值:\n"); scanf("%d",&key); printf("\n出列顺序为:\n"); do { j=1; p=head; while(jnext;//使P指向下一结点 j++; } //报数过程. i=p->num; key=p->code; printf("%d\n",i); s->next=p->next;

c语言实现约瑟夫环问题

(一)基本问题 1?问题描述 设有编号为1,2,…小的n (n> 0)个人围成一个圈，每个人持有一个密码m。从第一个 人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m 时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。建立模型，确定存储结构。对任意n个人，密码为m, 实现约瑟夫环问题。 2.数据结构设计 首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点 定义为如下结构类型： struct Node { int data; Node *n ext; }； 其次，建立一个不带头结点的循环链表并由头指针first指示 3.算法设计 1、工作指针first, r, s, p, q初始化 2、输入人数（n）和报数（m） 3、循环n次，用尾插法创建链表 Node *q; for（i nt i=1;i<=n ;i++） { Node *p; p=new Node; p-> data =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 个) inext; 删除p 结点的后一结点q q=p->next; p->next=q->next; *L = p->next; 报出位置后Delete q; 计数器i++; 运行流程图

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

信息学院 数据结构实验报告 学号：姓名：班级 课程名称：数据结构实验名称：约瑟夫环 实验性质：①综合性实验√②设计性实验③验证性实验实验时间：2017.10 试验地点： 本实验所用设备：PC及VS2010 【数据结构】： typedef struct _RingNode { int pos; // 位置 struct _RingNode *next; }RingNode, *RingNodePtr; 【算法思想】： 以单链表实现约瑟夫环 用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值，直至全部输出。（约瑟夫环问题Josephus）。以环状链表实现 【算法描述】： void CreateRing(RingNodePtr pHead, int count) { RingNodePtr pCurr = NULL, pPrev = NULL; int i = 1; pPrev = pHead; while(--count > 0) { pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead; // 构成环状链表 }

void PrintRing(RingNodePtr pHead) { RingNodePtr pCurr; printf("%d", pHead->pos); pCurr = pHead->next; while(pCurr != NULL) { if(pCurr->pos == 1) break; printf("\n%d", pCurr->pos); pCurr = pCurr->next; } } void KickFromRing(RingNodePtr pHead, int m) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == m) { // 踢出环 printf("\n%d", pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr; pCurr = pCurr->next; if (pPrev == pCurr) { // 最后一个 printf("\n%d", pCurr->pos); // 显示出圈循序 free(pCurr); break; } i++; } } int main()

约瑟夫问题算法及数据结构课程设计报告

线性表的操作及其应用 一、问题描述 线性表、队列是一种常用的数据结构，有顺序和链式两种存储结构，在实际中应用十分广泛，而链表又分为单链表和循环链表，队列又分为链式队列和循环队列。这些数据结构都可用来解决约瑟夫环问题。约瑟夫环问题是算法设计中的一个经典问题，是顺序编号的一组n个人围坐一圈，从第1个人按一定方向顺序报数，在报到m时该人出列，然后按相同方法继续报数，直到所有人出列。设计算法求约瑟夫环中人员的出列顺序。 二、基本要求 1、选择合适的存储结构，建立线性表； 2、利用顺序存储结构求解约瑟夫环问题； 3、利用单链表和循环链表分别求解约瑟夫环问题； 4、利用队列求解约瑟夫环问题。 三、测试数据 约瑟夫环的测试数据为7，报数为1至3。 四、算法思想 由于用到四种不同的存储结构，它们的算法思想依次是： 1、首先建立一个顺序表模拟整个约瑟夫环，手动输入顺序表长（即参加约瑟夫循环的人数）和循环的次数和表元素。用已经输出总人数和顺序表长作比较，作为外层循环条件。并对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查顺序表此次是不是我们设立的标记，如果不是则循环次数加1，当达到要求的循环次数时就将循环次数设置为0，输出该元素到屏幕并将总输出元素加1。每次外循环我们都会移到表的下一个位置，作为新的判断条件，每次报到表尾的时候，我们都将重新设置到表尾，作为下次循环的表元素。 2、首先采用链式循环链表建立整个约瑟夫环，手动输入第一次的循环次数和每个人所持下一个循环次数。设立判断指针指向表头，并将该指针是否为空作为外层循环条件。做一个内层循环，将判断指针移动到循环要输出的数，并设立一个前指针指向该指针的前一个位置，输出该元素后，将循环次数重新赋值成该元素。接着判断前指针和判断指针比较，如果相等说明整个表已经输出完毕，否则将删除该位置的元素。 3、用链式队列建立循环约瑟夫环，手动输入人数，第一次的循环次数和每个人所持下一个循环次数。并将每一个元素依次入队列，根据第一次循环次数，建立一个for循环，每一次循环都出队列，如果达到要求的循环次数就输出，否则进队列，这样这个数字就出现在队尾。第一个数输出后，以队列的非空作为循环条件，判断方式如上。 4、用循环队列建立约瑟夫环，将1-7个元素依次进入循环队列，以队列的长度作为与已输出的元素作为判断条件，对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查该该位置的元素是不是我们设立的标记-1，如果不是则循环次数加1，将队首指针移

约瑟夫环实验报告

一．需求分析 1.约瑟夫环（Joseph）问题的一种描述是：编号为1，2……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。 2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，有用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在其后。 3.程序执行的命令包括： 1）输入初始密码和人数2）输入所有人的密码3）显示输入的所有人的编号及相应的密码4）输出出列密码及编号5）结束 4.测试数据 (1)m=20, n=7, 7个人的密码依次为3，1，7，2，4，8，4 (2)m=20,n=1 (3)m=20,n=0 前面一组为常规数据，后面两组为边缘数据 二、概要设计 为实现上述功能，应以有序单向循环链表表示约瑟夫环。为此，需要有一个抽象数据类型。该抽象数据类型的定义为： ADT LinkList { 数据对象：D={ ai | ai ∈termset,i=1,2,……n,n>=0}， termset中每个元素包含编号，密码，和一个指向下一节点的指针数据关系：R1={ | ai-1, ai ∈D , i=2,……n} 基本操作： LinkList EvaluList(int n);//对单向循环链表进行尾插入赋值 int size(LinkList L);//求链表的节点个数 Status ScanList(LinkList L);//遍历单向循环链表 Status Joseph(LinkList &L,int m);//约瑟夫环的实现 } 此抽象数据类型中的一些常量如下：#define TRUE 1 #define FALSE 0 #define OK 1

约瑟夫环(内含源代码)

数据结构课程设计实验 学校：江西农业大学 班级：软件1115班 姓名：朱利斌 学号：20111976 课程：数据结构课程设计 指导教师：彭玉莹 实验一：约瑟夫问题

问题简述： 约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。 约瑟夫问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。改进约瑟夫问题的描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈, 每人有一个密码Ki（整数），留作其出圈后应报到Ki 后出圈。报数方法采用顺时针报数和逆时针报数交替进行，初始密码可任意确定。求最后剩下的人的编号。这个就是约瑟夫环问题的实际场景，后来老师要求我们对要求中的每人所持有的密码以及第一次的报数上限值要用随机数产生。因此约瑟夫环问题如果采用双向循环链表则能很好的解决。循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。p->link=head解决问题的核心步骤：先建立一个具有n个链结点，无头结点的循环链表，然后确定第一个报数人的位置，并不断地从链表中删除链结点，直到链表为空。 一、题目内容及要求 【问题描述】 编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 【要求】 利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。 2）掌握线性表的基本操作，如插入、删除、检索等在链式存储结构上的运算。

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

《数据结构》课程实验 实验报告 题目：Joseph问题求解算法的设计与实现专业：计算机科学与技术 班级： 姓名： 学号： 完成日期：

一、试验内容 约瑟夫（Joseph）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 二、试验目的 掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。 三、流程图 输入总人数n 创建并初始化 n个结点 输入第一个报 的数key n==0 报数过程 输出出列者 的编号及密 码 结束 n--

四、源程序代码 //Joseph问题求解算法的设计与实现 #include #include struct list { int num,code; struct list *next; }; void main() { printf("Joseph问题求解算法的设计与实现\n \n"); int i,j,m=1; int key; // 密码. int n; //人数 . list *p,*s,*head; head=(list *)malloc(sizeof(list)); //为头结点分配空间. p=head; printf("输入人的总个数:"); scanf("%d",&n); for(i=1;i<=n;i++) { key=rand() % 100; printf("第%d个人的密码:%d\n",i,key); s=p; p=(list *)malloc(sizeof(list)); //创建新的结点. s->next=p; p->num=i; p->code=key; } p->next=head->next; p=head; head=head->next; free(p); //释放头结点. p=head; do{ printf("\n第%d号成员的密码为:%d",p->num,p->code); //输出链表. p=p->next; }while(p!=head); printf("\n\n输入第一个报的数:\n"); scanf("%d",&key); printf("\n出列顺序为:\n"); do

约瑟夫环课程设计实验报告

《数据结构》 课程设计报告 课程名称：《数据结构》课程设计课程设计题目：joseph环 姓名： 院系：计算机学院 专业： 年级： 学号： 指导教师： 2011年12月18日

目录 1 课程设计的目的 (2) 2 需求分析 (2) 3 课程设计报告内容 (3) 1、概要设计 (3) 2、详细设计 (3) 3、调试分析 (x) 4、用户手册 (x) 5、测试结果 (6) 6、程序清单 (7) 4 小结 (10) 1、课程设计的目的 （1）熟练使用C++编写程序，解决实际问题； （2）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； （3）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； （4）提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 2、需求分析 1、问题描述： 编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 2、要求： 利用不带表头结点的单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。 3、测试数据： m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？ 输出形式：建立一个输出函数，将正确的输出序列

3、课程设计报告内容 概要设计： 在理解了题目后，我先想到的是我们所学的单链表，利用单链表先建立循环链表进行存贮，建立完循环链表后，我将所要编写的函数分为了两块，一块是经过学过的单链表改编的循环链表的基本操作函数，还有一块是运行约瑟夫环的函数。 详细设计： 我先建立一个结构体，与单链表一样，只是多了一个存密码的code域 struct LinkNode { int data; /删除的是尾结点时（不知道为什么我写程序里总是编译出现错误）{ q->next=head; //重新链接 delete a; len--; return out; } else { q->next=a->next; delete a; len--; return out; } } } } 5、测试结果：

数据结构课程设计——约瑟夫环报告(含代码)

#include #include typedef struct LNode { //数据域 int cipher; //密码 int number; //编号 struct LNode *next; //指针域 }LNode,*LinkList; void InitList(LinkList &L) //创建一个只有头结点链表{ L = (LinkList)malloc(sizeof(LNode)); if(!L) { exit(1); printf("/n/nError!/n/n"); } L->next = L; } void CreateList(int n,LinkList &L) //初始化循环单链表 { LinkList p,q; q = L; printf("分别输入每个人的密码："); for(int i = 1;i <= n;i++) { int k; scanf("%d",&k); if(k <= 0) { printf("\n\n密码有误!\n\n"); exit(1); } p = (LinkList)malloc(sizeof(LNode)); if(!p) { exit(1); printf("/n/nError!/n/n"); } p->cipher = k; p->number = i;

L->next = p; L = p; } L->next = q->next; free(q); } void PrintList(int x,int n,LinkList L) //输出出列顺序 { LinkList p,q; p = L; for(int i = 1;i <= n;i++) { for(int j = 1;j < x;j++) p = p->next; q = p->next; x = q->cipher; printf("%d ",q->number); p->next = q->next; free(q); } } int main() { printf("=============约瑟夫环==============\n\n\n"); int n,x; LinkList L; L = NULL; InitList(L); //构造空链表 printf("输入初始密码："); scanf("%d",&x); //初始密码为x printf("\n"); printf("输入参与总人数："); scanf("%d",&n); //总共的人数n printf("\n"); CreateList(n,L); //建立好一个约瑟夫环printf("\n\n\n===================================\n\n"); printf("出列编号为："); PrintList(x,n,L); //输出出列顺序 printf("\n\n"); return 0; }

约瑟夫环问题讲解

2009年02月24日星期二下午 05:03 问题描述:约瑟夫环问题；有N个人围成一个环，从第一个人开始报数，报到M 的人退出环，并且由他的M值来代替原有的M值，要求输出离开环的顺序。#include #include using namespace std; //结点中数据域的类型定义 typedef struct { int number;//标号 int chipher;//手中的值 }DataType; //带头结点的单循环链表 typedef struct node { DataType data; struct node *next; }Scnode; //初始化 void MyInit(Scnode **head)//指向指针的指针。 { if((*head=(Scnode *)malloc(sizeof(Scnode)))==NULL) exit(1);//动态分配 (*head)->next=*head; } //插入 int MyInsert(Scnode *head,int i,DataType x) { Scnode *p,*q; int j; p=head->next;j=1; while(p->next!=head&&jnext; j++; }

if(j!=i-1&&i!=1) {cout<<"erro!!!!!!!!!"; return 0;} if((q=(Scnode *)malloc(sizeof(Scnode)))==NULL) exit(1); q->data=x; q->next=p->next; p->next=q; return 1; } //删除 int MyDelete(Scnode *head,int i,DataType *x) { Scnode *p,*q; int j; p=head;j=1; while(p->next!=head&&jnext; j++; } if(j!=i-1) {cout<<"erro!!!!!!!!!"; return 0;} q=p->next; *x=q->data; p->next=p->next->next; free(q); return 1; } //取数据元素 int MyGet(Scnode *head,int i,DataType *x) { Scnode *p; int j; p=head;j=0;

约 瑟 夫 环 问 题 的 三 种 解 法 ( 2 0 2 0 )

约瑟夫问题(数学解法及数组模拟) 约瑟夫问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.）据说著名犹太历史学家 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*【9】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++; --如果这里有人,计数器+1 if(cnt == m) --如果此时已经等于m,这这个人死去 cnt = 0; --计数器清零 s++; --死亡人数+1 vis[t] = 1 --标记这个位置的人已经死去 coutt" "; --输出这个位置的编号 }while(s != n); 接下来我们来看另一种更为高效快速的解法数学解法 我们将这n个人按顺时针编号为0~n-1，则每次报数到m-1的人死去，剩下的人又继续从0开始报数，不断重复，求最后幸存的人最

数据结构课程设计报告约瑟夫环完整版

******************* 实践教学 ******************* 兰州理工大学 软件职业技术学院 2011年春季学期 算法与数据结构课程设计 题目：约瑟夫环 专业班级： 姓名： 学号： 指导教师： 成绩：

摘要 约瑟夫环问题是典型的线性表的应用实例，其开发主要包括后台数据库的建立和维护以及前端应用程序的开发两个方面。对于前者要求建立起数据一致性和完整性强、数据安全性好的库。而对于后者则要求应用程序功能完备，易使用等特点。 经过分析，我们使用MICROSOFT公司的Microsoft Visual C++6.0开发工具，利用其提供的各种面向对象的开发工具，尤其是数据窗口这一能方便而简洁操纵数据库的智能化对象，首先在短时间内建立系统应用原型，然后，对初始原型系统进行需求迭代，不断修正和改进，直到形成用户满意的可行系统。 关键词：单循环链表；c语言；约瑟夫环；

序言 数据结构是研究数据元素之间的逻辑关系的一门课程，以及数据元素及其关系在计算机中的存储表示和对这些数据所施加的运算。该课程设计的目的是通过课程设计的综合训练，培养分析和编程等实际动手能力，系统掌握数据结构这门课程的主要内容。 本次课程设计的内容是用单循环链表模拟约瑟夫环问题，循环链表是一种首尾相接链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理更加灵活，约瑟夫环问题就是用单循环链表处理的一个实际应用。通过这个设计实例，了解单链表和单循环链表的相同与不同之处，进一步加深对链表结构类型及链表操作的理解。 通过该课程设计，能运用所学知识，能上机解决一些实际问题，了解并初步掌握设计、实现较大程序的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。

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

《计算机软件技术基础》实验报告 I —数据结构 实验一、约瑟夫斯问题求解 一、问题描述 1.实验题目：编号 1,2,....,n的n个人顺时针围坐一圈，每人持有一个密码（正整数）。 开始选择一个正整数作为报数上限m，从第一个人开始顺时针自 1 报数，报到m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从 1 报数，直至所有人全部出列。 2. 基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号。 3. 测试数据： n=7,7 个人的密码依次为：3,1,7,2,4,8, 4.m初值为6（正确的出列顺序 应为 6,1,4,77,2,3）。 二、需求分析 1. 本程序所能达到的基本可能： 该程序基于循环链表来解决约瑟夫问题。用循环链表来模拟n 个人围坐一圈，用链表 中的每一个结点代表一个人和他所代表的密码。在输入初始密码后m，对该链表进行遍历，直到第 m个结点，令该结点的密码值作为新的密码值，后删除该结点。重复上述过程，直至所有的结点被释放空间出列。 2. 输入输出形式及输入值范围： 程序运行后提示用户输入总人数。输入人数 n 后，程序显示提示信息，提示用户输入第 i个人的密码，在输入达到预定次数后自动跳出该循环。程序显示提示信息，提示用户输入 初始密码，密码须为正整数且不大于总人数。 3．输出形式 提示用户输入初始密码，程序执行结束后会输出相应的出列结点的顺序，亦即其编号。 用户输入完毕后，程序自动运行输出运行结果。 4.测试数据要求： 测试数据 n=7，7 个人的密码依次为：3， 1， 7， 2， 4， 8， 4。 m初值为 6（正确的出列 顺序应为6， 1， 4，7， 2， 3， 5）。 三、概要设计 为了实现上述功能，应用循环链表来模拟该过程，用结构体来存放其相应的编号和密码

约 瑟 夫 环 问 题 的 三 种 解 法

约瑟夫环问题python解法 约瑟夫环问题：已知n个人（以编号1，2，3.n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到k的那个人被杀掉；他的下一个人又从1开始报数，数到k的那个人又被杀掉；依此规律重复下去，直到圆桌周围的人只剩最后一个。 思路是：当k是1的时候，存活的是最后一个人，当k=2的时候，构造一个n个元素的循环链表，然后依次杀掉第k个人，留下的最后一个是可以存活的人。代码如下： class Node(): def __init__(self,value,next=None): self.value=value self.next=next def createLink(n): return False if n==1: return Node(1) root=Node(1) tmp=root for i in range(2,n+1): tmp.next=Node(i) tmp=tmp.next

tmp.next=root return root def showLink(root): tmp=root while True: print(tmp.value) tmp=tmp.next if tmp==None or tmp==root: def josephus(n,k): if k==1: print('survive:',n) root=createLink(n) tmp=root while True: for i in range(k-2): tmp=tmp.next print('kill:',tmp.next.value) tmp.next=tmp.next.next tmp=tmp.next if tmp.next==tmp: print('survive:',tmp.value) if __name__=='__main__':

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

数据结构实验报告 题目：约瑟夫环 姓名： 学号： 专业班级： 指导教师： 课题工作时间：

一．需求分析 1.约瑟夫环（Joseph）问题的一种描述是：设有编号1,2,3。。。n(n>0)的N个人围成一个圈，每个人持有一个密码（正整数）。开始时从第k（1<=k<=n）个人按顺时针方向自1开始顺序报数，报到m（m为第K个人的密码）的人出圈，再以这个人顺时针方向上的下一个人的密码为m，并开始重新从1报数。如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，有用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在其后。 3.测试数据 (1)m=20, n=7, 结果依次为为3，1，7，2，4，8，4 (2)m=20,n=1 (3)m=20,n=0 前面一组为常规数据，后面两组为边缘数据 二、概要设计 本程序是多文件程序，构成的函数有 int main() 主函数，输出出队序列 int initsuiji() 随机数产生初始化 int suiji(int x,int y) 随机数产生函数 int InitList(SqList &L) 初始化顺序表 int ListInsert(SqList &L,int i,ElemType e) 在顺序表中插入元素 int ListDelete(SqList &L,int i,ElemType &e) 删除顺序表中的元素 int shunxu(int number) 顺序存储算法 JosephuNode *Creat_Node(int numbers) 创建单循环链表 void Josephu(JosephuNode *head,int Password) 添加元素信息 int lianbiao(int number) 链表算法 其中，void main()是最主要的函数，分别执行两种算法，并在执行的同时按照出列顺序输出元素信息（编号，密码），并在结尾输出两种算法执行所用的时间长短。 三、详细设计 头文件 #include #include #include

数据结构约瑟夫环的课程设计报告

武汉工业学院数学与计算机学院 数据结构课程设计 设计题目：约瑟夫环 专业大类计算机 班级计算机6班 学号 100702129 姓名王元 指导教师李禹生 2011年9月3 日

一．选题背景： 题目：约瑟夫环 问题描述： 编号为1,2，…..，n的n个人按顺时针方向围坐圈，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新重新从1报数，如此下去，直至所有人全部出列为止。 基本要求： ⑴建立模型，确定存储结构； ⑵对任意 n个人，密码为 m，实现约瑟夫环问题； ⑶出圈的顺序可以依次输出，也可以用一个数组存储。 设计指导思想： 首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。其次，建立一个不带头结点的循环链表并由头指针 first 指示。最后，设计约瑟夫环问题的算法。下面给出伪代码描述，操作示意图如图 2-1 所示。

二．方案论证： 本方案通过建立单循环链表模拟了约瑟夫问题；首先，建立一个结构体node，然后给他开辟一个储存空间；利用头指针head标记链表，利用尾指针向后移将建立的结点连接成我们需要的单循环链表， 过程如下： 约瑟夫问题中的人数个数即为链表的长度，链表中node->num 编号n，node->data为每个人的密码。建立单循环链表后，通过初始报数上限找到出列的结点，输出该结点的node->num值，将该结点中的data中数作为新密码开始下一个步的开始，将该结点从链表中删除，并释放该结点的空间。重复此过程，直到剩下最后一个结点，就直接将该结点中的num值输出，删除该结点，并释放该结点的空间。输出的num值即为约瑟夫中人的编号。 三．过程论述： typedef struct node { int data; int num; struct node *next; }listnode; 定义一个结构体用来储存学生的编号和所携带的密码 for(i=1;i<=n;i++) { printf("输入第%d号同学的密码:",i); scanf("%d",&j);//输入学生所带密码 p1->next=(listnode*)malloc(sizeof(listnode));//建立一个新的空间，并将它的地址赋给p1->next p1=p1->next; p1->data=j; p1->num=i;//对结点的num和data成员赋值 p1->next=head->next;//构成单循环链表 } 定义指针p1，然后建立一个新结点并将p1->next指向它的地址，然后将这个地址赋给p1，最后将head->next赋给p1->next,构成一个单循环链表，并不断在尾部插入新的结点，直至所有人都进入循环链表中，而且在循环的过程中给结点的num和data成员赋值

c语言实现约瑟夫环问题

（一）基本问题 1.问题描述 设有编号为1,2,…,n的n（n＞0）个人围成一个圈，每个人持有一个密码m。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m 时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。建立模型，确定存储结构。对任意n个人，密码为m，实现约瑟夫环问题。 2.数据结构设计 首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型： struct Node { int data; Node *next; }; 其次，建立一个不带头结点的循环链表并由头指针first指示 3.算法设计 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-> data =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个） 当inext; 删除p结点的后一结点q q=p->next; p->next=q->next; *L = p->next; 报出位置后Delete q; 计数器i++; 运行流程图

数据结构约瑟夫环课程设计报告书

《数据结构》课程设计报告书 设计题目：约瑟夫环 专业： 班级： 姓名： 指导教师： 完成日期：

目录 一、问题描述 (1) 二、基本要求 (1) 三、测试数据 (1) 四、算法思想 (2) 五、模块划分 (3) 六、数据结构 (4) 七、源程序 (4) 八、界面设计 (6) 九、运行与测试 (6) 十、总结 (8) 十一、思考与感悟 (9)

课程设计设计报告书 一、问题描述 约瑟夫问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。改进约瑟夫问题的描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈, 每人有一个密码（整数），留作其出圈后应报到后出圈。报数方法采用顺时针报数和逆时针报数交替进行，初始密码可任意确定。求最后剩下的人的编号。这个就是约瑟夫环问题的实际场景，后来老师要求我们对要求中的每人所持有的密码以及第一次的报数上限值要用随机数产生。因此约瑟夫环问题如果采用双向循环链表则能很好的解决。循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。p->link=head解决问题的核心步骤：先建立一个具有n个链结点，无头结点的循环链表，然后确定第一个报数人的位置，并不断地从链表中删除链结点，直到链表为空。 二、基本要求 (1)输入的形式和输入值的范围：输入的形式是以数字的形式输入，输入范围为-2147483648～2147483648 (2)输出的形式：字符串形式输出 (3)程序所能达到的功能：达到符合约瑟夫环要求的响应功能。 三、测试数据 进入程序，显示“1.开始游戏0.退出游戏”输入非0数进入游戏，输入0退出游戏。 进入游戏后显示“输入总人数”，输入大于0的整数；若输入错误，则光标处清空，重新输入。 后提示“输入开始人的序号”；范围是大于零，小于总人数的整数，若输入错误，则光标处清空，重新输入。 后提示“输入间隔数字”，范围是任意正整数；若输入错误，则光标处清空，重新输入。 按回车键，显示结果，并重新询问“1.开始游戏0.退出游戏”。

约瑟夫环问题源代码(C语言)

约瑟夫环问题如下：已知n 个人(n>=1)围桌一园桌周围，从1开始顺序编号。从序号为1的人开始报数，顺时针数到m 的那个人出列。他的下一个人又从1开始报数，数到m 的那个人又出列。依此规则重复下去，直到所有人全部出列。求解最后一个出列的人的编号。 本次实验是以顺序表求解约瑟夫环问题，程序流程图及程序运行结果如下： 程序代码如下： #include #include #include 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() //主函数 { system("color 75"); //设置颜色以美观 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<<"尾指针异常!"<>k; if(k<1||k>n){cout<<"请输入1-"<