#include
#include
typedefstruct data{
//定义一个结构体“data”
intnum; //用于存放人的序号
intval; //用于存放密码
}typedata;
typedefstruct node{
//定义一个结构体（结点），其中包含一个数据域和一个指针域
typedata data; //结构体的嵌套
struct node *next;
}listnode;
typedeflistnode *linklist;
linklist head;
void main()// 进入主函数
{
intn,i,b,m,j;
linklist head=(listnode *)malloc(sizeof(listnode)); //申请一个空间（头结点head）
listnode *p,*q; //定义两个可以指向结点的指针
printf("输入总人数：");
scanf("%d",&n);
q=head; //用指针q指向头结点
for(j=1;j<=n;j++) //本次循环主要是将每一个人的数据（包括序号、密码）存入循环链表中
{
printf("请输入第%d号同学的密码:\n",j);
scanf("%d",&b);
printf("\n");
q->next=(listnode *)malloc(sizeof(listnode)); //将头结点的next域指向刚生成的一个结点
q=q->next;
q->data.val=b; //输入密码
q->data.num=j; //输入序号
q->next=head->next;
} //将尾结点的next域指向第一个结点，构成循环链表
printf("请任意输入一个数m：");
scanf("%d",&m);
if(m<=0) printf("输入错误");
do{
I=1;
while(I!=m)
{ //将q指针指向所要输出的结点的前一结点
q =q->next;
I++;
}
p=q->next; //p指向输出结点
q->next=p->next; //将输出结点的前结点的next域指向输出结点的后结点
printf("num:%d\tval:%d\n",p->data.num,p->data.val); //输出
m=p->data.val; //取得输出结点的密码
free(p);
}
while(q->next!=q); //只剩最后一个结点时结束
printf("num:%d\tval:%d\n",q->data.num,q->data.val); //输出最后一个结点
free(q); //释放最后一个结点
free(head); //释放头结点
}
《数据结构》 课程设计报告 课程名称：《数据结构》课程设计课程设计题目：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、测试结果：
课程实验报告 题目：2016.4.6 学生姓名：黄玲 学生学号：201408070105 专业班级：智能1401 指导老师：骆嘉伟 完成日期：2016.4.6
一．需求分析 1.本实验基本要求是用数组来实现线性表，再基于线性表的基本操作（插入、删除、修改等）来实现约瑟夫问题 2.由键盘输入总人数n和出列报数m 3.在DOS界面上显示依次出圈的人的编号和最后一个留下的人,在当前文件夹里生成一个文本文件，里面是相同的输出。 4.测试数据： 输入： 10，3 输出： 3 6 9 2 7 1 8 5 10 4//DOS 3 6 9 2 7 1 8 5 10 4//TXT 二．概要设计 §抽象数据类型 为实现上述程序的逻辑功能，应以整数存储用户的输入 用线性表实现，线性表定义如下： ADT LISt 数据对象：整数 基本操作： AList(100);//构建一个最大人数为100的顺序表（数组）来存储人 Next();//指向下一个人 moveStart();//回到第一个人继续数数 Length();//查看圈里还剩多少人 currPos();//查看当前数到人的编号 getValue();//查看当前编号的人是否还在圈内 §程序的流程 以书上的代码案例为参考，编写线性表的ADT在继承线性表的基础上编写顺序表（数组）的类文件编写主函数，创建类的对象，完成程序 三．详细设计 §物理数据类型 将大小为n的数组赋好值，其值为他本身的编号，即数组下标。 §程序思路的具体步骤实现 设一个标志点，在数组中移动，同时报数，当报到m时，当前人的值变为0，出圈，然后继续移动，重新数。当数到值为0的人时自动跳过（已出圈），当数
中南民族大学管理学院学生实验报告 实验项目: 约瑟夫问题 课程名称：数据结构 年级： 专业：信息管理与信息系统 指导教师： 实验地点：管理学院综合实验室 完成日期： 小组成员： 2012 学年至2013 学年度第1 学期
一、实验目的 （1）掌握线性表表示和实现； （2）学会定义抽象数据类型； （3）学会分析问题，设计适当的解决方案； 二、实验内容 【问题描述】：编号为1,2,…,n的n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自 1 开始顺序报数，报到m 时停止报数。报m 的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从1 报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 【基本要求】：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 【测试数据】：m 的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。 三、实验步骤 （一）需求分析 对于这个程序来说，首先要确定构造链表时所用的插入方法。当数到m 时一个人就出列，也即删除这个节点，同时建立这个节点的前节点与后节点的联系。由于是循环计数，所以才采用循环列表这个线性表方式。 程序存储结构利用单循环链表存储结构存储约瑟夫数据（即n个人的编码等），模拟约瑟夫的显示过程，按照出列的顺序显示个人的标号。编号为1,2,…,n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值 m，从第一个人开始按顺时针方向自1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。基本要求是利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 程序执行的命令（1）构造单向循环链表。 （2）按照出列的顺序引出各个人的标号。 测试数据 m 的初值为 20；密码：3，1，7，2，4，8，4（正确的结果应为 6，1，4，7，2，3，5） （1）、插入：在把元素插入到循环链表中时，由于是采用的头插法，所以我保留了front头结点。在每加入一个节点时，都会直接连接在front后面，从而保证一开始就赋值的rear尾节点不用修改。 伪代码阐释如下：
线性表的操作及其应用 一、问题描述 线性表、队列是一种常用的数据结构，有顺序和链式两种存储结构，在实际中应用十分广泛，而链表又分为单链表和循环链表，队列又分为链式队列和循环队列。这些数据结构都可用来解决约瑟夫环问题。约瑟夫环问题是算法设计中的一个经典问题，是顺序编号的一组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={
2009年02月24日星期二下午 05:03 问题描述:约瑟夫环问题；有N个人围成一个环，从第一个人开始报数，报到M 的人退出环，并且由他的M值来代替原有的M值，要求输出离开环的顺序。#include
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&&j
课程设计报告 课程名称：数据结构课程设计课程设计题目：约瑟夫环问题 姓名：余明旭 系：计算机科学与技术专业：计算机科学与技术年级：2010级 学号：100310236 指导教师：陈老师 职称：学生
一、需求分析 1、输入的形式和输入值的范围： 本程序中，输入报数上限值n，初始报数者s，初始报数者携带的密码m1，n-2个人携带的密码m（最后一人携带的密码没用），均限定为正整数，输入的形式为一个以“回车符”为结束标志的正整数。 2、输出的形式： 从屏幕显示出列顺序。 3、程序所能够达到的功能： 提供用户从键盘输入，Joseph约瑟夫环的必要数据，并显示出列顺序。4、测试数据： 输入 8 1 4 4 4 4 4 4 4 输出 4 8 5 2 1 3 7 6 一、详细设计 以单向循环链表实现该结构： 1、抽象数据类型的定义为： struct LNode { ElemType data; LNode* next; }; 2、本程序包含以下模块： 主程序模块： Void main() { 初始化； 输入数据； 执行功能； 显示结果； } 各功能模块：实现单链表的各项功能。 Void fun() { } 3、各模块的调用关系：
三、调试分析 程序的编写和调试基本正常，遇到的问题主要是：指针的指向的边界问题，如何每次正确找到出列的人的位置。 解决方法： for(int j=1;j
约瑟夫问题(数学解法及数组模拟) 约瑟夫问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.）据说著名犹太历史学家 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开始报数，不断重复，求最后幸存的人最
#include
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; }
4：课程设计报告书附件 《数据结构》课程设计报告 环Joseph）约瑟夫（ 第七组别组组长成组员成绩教师指导 计算机科学与技术系 日11月6年2014． 摘要 约瑟夫环问题是典型的线性表的应用实例，其开发主要包括后台数据库的建立和维护以及前端应用程序的开发两个方面。对于前者要求建立起数据一致性和完整性强、数据安全性好的库。而对于后者则要求应用程序功能完备，易使用等特点。经过分析，我们使用MICROSOFT公司的Microsoft Visual C++6.0开发工具，利用其提供的各种面向对象的开发工具，尤其是数据窗口这一能方便而简洁操作数据库的智能化对象，首先在短时间内建立系统原型，然后，对初始原型系统进行需求迭代，不断修正和改进，直到形成用户满意的可行系统。 关键词：单循环链表；c 语言；约瑟夫环；
序言 数据结构是研究数据元素之间的逻辑关系的一门课程，以及数据元素及其关系在计算机中的存储表示和对这些数据所施加的运算。该课程设计的目的是通过课程设计的综合训练，培养分析和编程等实际动手能力，系统掌握数据结构这门课程的主要内容。 本次课程设计的内容是用单循环链表模拟约瑟夫环问题，循环链表是一种首尾相接链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理更加灵活，约瑟夫环问题就是用单循环链表处理的一个实际应用。通过这个设计实例，了解单链表和单循环链表的相同与不同之处，进一步加深对链表结构类型及链表操作的理解。 通过该课程设计，能运用所学知识，能上机解决一些实际问题，了解并初步掌握设计、实现较大程序的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。 章节安排 1........................... 摘要、序言.... 一、问题描述 1、课程设计目的.................. (4) 2、课程设计任务.................. (4) 二、设计过程 1、设计思想（数据结构）.................. . (4) 2、设计表示（函数说明）.................. . (5) 3、详细设计（主要算法）.................. . (6) 4、用户手册（使用说明）.................. . (6) 三、测试报告
基础成绩：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(j
约瑟夫环问题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__':
合肥学院 计算机科学与技术系 课程设计报告 2009～2010学年第二学期 课程数据结构与算法 课程设计名称joseph环 学生姓名朱玉庭 学号0804012029 专业班级08计本(2) 指导教师王昆仑、张贯虹 2010 年06月08号
一、问题分析和任务定义： 约瑟夫环是一个数学游戏，根据游戏内容的描述，能够很容易的看出，游戏中的玩家顺时针围坐一圈，能够很容易的发现，这跟本课上的单循环链表非常相似，所以可以通过单循环链表存储结构模拟此过程，当游戏中的玩家出列时，可以通过删除单循环链表中的结点来实现。 二、数据结构的选择和概要设计： 选择带为指针的单循环链表来解决这个问题，先建立一个空链表，然后根据人数生成具有相应结点的单循环链表，知道密码后，通过循环来找到对应的结点，然后将该结点的编号输出，改变密码，最后删除结点，以此类推，知道编码全部输完，即可得到结果序列。 三、详细设计和编码： 本题目是通过单循环链表存储结构来模拟此过程的，首先要先明确该单循环链表中结点的结构类型，定义如下： typedef struct Node { int key; //每个人持有的密码 int num; //这个人的编号 struct Node *next; //指向下一个结点 }Link; 当生成单循环链表时，就需要用到课本上创建单循环链表的有关内容了，可以先通过子函数Link *InitList()建立一个空链表，返回指针L，然后将返回的指针代入子函数Link *Creater(Link *L,int n)的形参中，对循环链表进行初始化，并且也返回一个指针，然后再将这个返回的指针代入到输出函数void Output(Link *L,int n,int m)的形参中，要想根据题目要求完成序列的输出，需要通过两个for循环来实现，第一个循环for(i=1;i<=n;i++) ，因为一个用n个人，所以结果要输出n个编号，这个循环每循环一次输出一个编号即printf("%d ",q->num)，并将该编号下的密码赋值给m 即m=q->key，当循环完毕时正好将编号全部输出，第二个循环for(j=1;j
《数据结构与算法设计》约瑟夫环实验报告 ——实验一 专业:物联网工程 班级:物联网1班 学号: 姓名:刘沛航
一、实验目的 1、熟悉VC环境,学习使用C语言利用链表的存储结构解决实际的问题。 2、在编程、上机调试的过程中,加深对线性链表这种数据结构的基本概念理解。 3、锻炼较强的思维与动手能力与更加了解编程思想与编程技巧。 二、实验内容 1、采用单向环表实现约瑟夫环。 请按以下要求编程实现: ①从键盘输入整数m,通过create函数生成一个具有m个结点的 单向环表。环表中的结点编号依次为1,2,……,m。 ②从键盘输入整数s(1<=s<=m)与n,从环表的第s个结点开始计 数为1,当计数到第n个结点时,输出该第n结点对应的编号, 将该结点从环表中消除,从输出结点的下一个结点开始重新计 数到n,这样,不断进行计数,不断进行输出,直到输出了这个环 表的全部结点为止。 例如,m=10,s=3,n=4。则输出序列为:6,10,4,9,5,2,1,3,8,7。 三、程序设计 1、概要设计 为了解决约瑟夫环的问题,我们可以建立单向环表来存储每个人的信息(该人的编号以及其下一个人的编号),及结点,人后通
过查找每个结点,完成相应的操作来解决约瑟夫问题。 （1） 抽象数据类型定义 ADT Joh{ 数据对象:D={|,1,2,,,0}i i a a ElemSet i n n ∈=≥ 数据关系:R1=11{,|,,1,2,,}i i i i a a a a D i n --<>∈= 基本操作: create(&J, n) 操作结果:构造一个有n 个结点的单向环表J 。 show(J) 初始条件:单向环表J 已存在。 操作结果:按顺序在屏幕上输出J 的数据元素。 calculate( J,s,n) 初始条件:单向环表J 已存在,s>0,n>0,s<环表结点 数。 操作结果:返回约瑟夫环的计算结果。 }ADT Joh (2)宏定义 #define NULL 0 #define OK 1 #define ERROR -1 (3)主程序流程
约瑟夫环问题 问题描述： 有n个人围成一个环，然后给从某个人开始顺时针从1开始报数，每报到m时，将此人出环杀死(当然不杀死也可以啊)，然后从下一个人继续从1报数，直到最后只剩下一个人，求这个唯一剩下的存活的人是谁？ 分析： 首先，我们要标示这n个人，别小看这一步，其实蛮重要的。第一种标示方法是从0开始，将n个人标示为0~n-1，第二种方法是从1开始标示，将这n个人标示为1~n。当然会有人说了，那我从x(x>=2)开始，将此n个数标示为x~x+n-1，其实我们可以把这种情况都归到第二种从1开始标示的情况，为什么可以，我们稍后分析。 第一种情况从0开始编号： 编号为k的人拖出去杀死之后，下一个要拖出去受死的人的编号为：(k+m)%n (假设当前有n个人还活在环中)。 第二种情况从1开始编号： 编号为k的人拖出去杀死之后，下一个要拖出去受死的人的编号为：(k+m-1)%n+1，于是我们就可以回答上面的问题了，如果从x开始编号的话，下一个拖出去受死的人的编号就应该是：(k+m-x)%n+x了。 其实，上面的这两种情况是完全可以在合并的，编号只是一个识别，就像名字一样，叫什么都没关系，从某个人开始出环，不管他们怎么编号，n个人出环的先后顺序都是一样的，最后该哪个人活下来是确定的，不会因为编号而改变，所以不管从几开始编号，都可以归纳为从0开始编号，其他的编号就是一个从0编号情况的一个偏移而已，从x编号的情况就相当于从0开始编号的情况下每个人的编号都+x，大小先后顺序不变~ 于是，下面的讨论都是从0开始编号的~ 怎么解决这个问题呢？ 最简单的方法是模拟，模拟这个出环过程，可以使用链表也可以使用数组，时间复杂度都是O(n*m).当然，这种解法时间复杂度太高，不可取~ 我们有O(n)的算法~ 假设从编号为0的人开始报数，当然从编号为k的人开始报数的情况也是也可以解决的，只要稍微转化就可以，至于怎么解决？我们讲完从编号为0的人开始报数的情况就明白啦~ 我们从0编号开始报数，第一个出环的人m%n-1，剩下的n-1个人组成一个新的约瑟夫环，接下来从m%n开始报数，令k=m%n，新环表示为： k, k+1, k+2, ……n-1, 0, 1, 2, …..., k-2 我们对此环重新编号，根据上面的分析，编号并不会影响实际结果。 k → 0 k+1 → 1 k+2 → 2 ... k-2 → n-2 对应关系为：x’ = (x+k)%n (其中，x’是左侧的，x是右侧重新编号的)
******************* 实践教学 ******************* 兰州理工大学 软件职业技术学院 2011年春季学期 算法与数据结构课程设计 题目：约瑟夫环 专业班级： 姓名： 学号： 指导教师： 成绩：
摘要 约瑟夫环问题是典型的线性表的应用实例，其开发主要包括后台数据库的建立和维护以及前端应用程序的开发两个方面。对于前者要求建立起数据一致性和完整性强、数据安全性好的库。而对于后者则要求应用程序功能完备，易使用等特点。 经过分析，我们使用MICROSOFT公司的Microsoft Visual C++6.0开发工具，利用其提供的各种面向对象的开发工具，尤其是数据窗口这一能方便而简洁操纵数据库的智能化对象，首先在短时间内建立系统应用原型，然后，对初始原型系统进行需求迭代，不断修正和改进，直到形成用户满意的可行系统。 关键词：单循环链表；c语言；约瑟夫环；
序言 数据结构是研究数据元素之间的逻辑关系的一门课程，以及数据元素及其关系在计算机中的存储表示和对这些数据所施加的运算。该课程设计的目的是通过课程设计的综合训练，培养分析和编程等实际动手能力，系统掌握数据结构这门课程的主要内容。 本次课程设计的内容是用单循环链表模拟约瑟夫环问题，循环链表是一种首尾相接链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理更加灵活，约瑟夫环问题就是用单循环链表处理的一个实际应用。通过这个设计实例，了解单链表和单循环链表的相同与不同之处，进一步加深对链表结构类型及链表操作的理解。 通过该课程设计，能运用所学知识，能上机解决一些实际问题，了解并初步掌握设计、实现较大程序的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。
数据结构实验报告 题目：约瑟夫环 姓名： 学号： 专业班级： 指导教师： 课题工作时间：
一．需求分析 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
《数据结构》课程实验 实验报告 题目：Joseph问题求解算法的设计与实现专业：计算机科学与技术 班级： 姓名： 学号： 完成日期：
一、试验内容 约瑟夫（Joseph）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 二、试验目的 掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。 三、流程图 输入总人数n 创建并初始化 n个结点 输入第一个报 的数key n==0 报数过程 输出出列者 的编号及密 码 结束 n--
四、源程序代码 //Joseph问题求解算法的设计与实现 #include