约瑟夫环数据结构实验.doc

实验1约瑟夫环问题背景约瑟夫问题(JosephusProblem)据说著名犹太历史学家Josephus有过以下的故事:在罗马人占领乔塔帕特后,39个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。 原题: 用户输入M,N值,N个人围成一个环,从0号人开始数,数到M,那个人就退出游戏,直到最后一个人求最后一个剩下的人是几号?问题描述设编号为1-n的n(n>0)(m为正整数).令其出列。然后再从他的下一个人开始,重新从1顺时针报数,报m的人,再令其出列。如此下去,直到圈中所有人出列为止。求出列编号序列。基本要求需要基于线性表的基本操作来实现约瑟夫问题需要利用顺序表来实现线性表输入输出格式输入格式:n,m输出格式1:在字符界面上输出这n个数的输出序列输出格式2:将这n个数的输出序列写入到文件中测试用例(举例)输入:10,3输出:36927185104课后选做内容使用单链表来实现之使用循环链表来实现之课后习题请以O(n)的时间复杂度来实现约瑟夫问题。HUNANUNIVERSITY实验报告题目:约瑟夫环问题 学生姓名**学生学号*********** 专业班级******* 指导老师**** 完成日期****/**/**一、需求分析编号为1-(m为正整数).令其出列。然后再从他的下一个人开始,重新从1顺时针报数,报m的人,再令其出列。如此下去,直到圈中所有人出列为止。程序依次输出出列人的编号到文件。输入格式:n,mn为约瑟夫环的大小,m为退出游戏人编号的报数。n和m都为大于0的整数。输出格式在文件中输出这n个数的输出序列将这n个数的输出序列写入到文件中测试数据:输入:10,3输出:36927185104二、概要设计 抽象数据类型游戏中人的编号为正整数,所以用整数来存储编号。约瑟夫环中人的编号为连续的正整数,可以看做是一个数列,用线性表来存储这个数列。基本操作包括线性表的初始化,和删除环中元素,以及判断表是否为空等。ADTList{数据对象:D={a[i]|a[i]∈整数,i=1,2,……,n,n>=0}数据关系:R1={<a[i-1],a[i]>|[ai-1],a[i]∈D,i=2,……,n}基本操作:InitList(&L)操作结果:构造一个空的线性表ListLength(L)初始条件:线性表L已经存在操作结果:返回L中元素个数ListEmpty(L)初始条件:线性表L已经存在操作结果:若L为空表,返回TRUE,否则返回FALSEListAppend(&L,e)初始条件:线性表L已经存在操作结果:将元素e插入到L的表尾ListDelete(&L,i,&e)初始条件:线性表L已经存在操作结果:删除L的第i个数据元素,返回e}ADTList算法的基本思想将约瑟夫环中人的编号依次放进线性表中,当前位置从