数学与计算机学院约瑟夫环问题实验报告

年级 10级学号 2010434062 姓名       成绩          

专业电气信息（计算机类）实验地点主楼402  指导教师史青宣         

实验项目       约瑟夫环问题       实验日期2011年12月26日             

一、实验目的

本实验的目的是进一步理解线性表的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。

二、实验问题描述

设编号为1，2，···，n的n个人围坐一圈，约定编号为k（1≤k≤n）的人从1开始报数，数到m的那个人出列，他的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

三、实验步骤

1、实验问题分析

①由于当某个人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍要是围成一个圆圈，可以使用循环表；由于退出圆圈的工作对应着表中结点的删除操作，对于这种删除操作频繁的情况，应该选用效率较高的链表结构；为了程序指针每一次都指向一个具体的代表一个人的结点而不需要进行判断，链表不带表头结点。所以，对于所有人围成的圆圈所对对应的数据结构采用一个不带头结点的循环链表来描述。设头指针为p，并根据具体情况移动

…… …… 余下全文

《数据结构》

课程设计报告

20##年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报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。

…… …… 余下全文

           

  

*******学院

课 程 设 计 报 告

 

课 程 名 称  数据结构课程设计报告

专       业                       

班       级                       

学 生 姓 名                       

学       号                       

…… …… 余下全文

《数据结构》实验报告

一、      上机实验的问题和要求：

问题描述：

编号为1到n的n个人围成一圈，每人带一个密码c，以m为报数上限。然后从第一个人开始顺时针自1开始报数，报到m的人出列，将其密码作为新的m值，从他的下一个人开始，同样顺时针自1开始报数，依次循环下去，直到所有的人都出列！要求得到依次出列的那些人的编号序列！

基本要求：

用C代码实现此活动，要求使用一定的算法进行操作，并最终通过程序运算出最后的结果！

二、程序设计的基本思想，原理和算法描述：

（包括程序的模块结构，数据结构，输入/输出设计，符号名说明等）

基本思想：

 利用不带头结点单向循环链表模拟该活动，在实现了一切动作之后，运用一定的算法得到最终的结果。

程序的模块结构：

     定义了相关的结构体之后，主要有以下几大模块：

1.       建立由头指针指示的有n个结点的不带头结点的单向循环链表crt_CLinkList(H,n);

2.       寻找、输出、删除H单循环链表的第m个结点locfor(H,m);

3.       最后通过main函数体处理参数的输入与显示，并调用以上两函数，最终解决问题。

主要数据结构：

单链的循环链表，即线性表的链式存储结构。

算法的伪码描述：

结构体定义如下：

typedef struct Lnode        /*定义单链表*/

{

    int number;             /*编号*/

…… …… 余下全文

实验1约瑟夫环问题

1．  需求分析

（1）   输入的形式和输入值的范围：

每一次输入的值为两个正整数，中间用逗号隔开。

若分别设为n,m，则输入格式为：“n,m”。

不对非法输入做处理，即假设输入都是合法的。

（2）   输出的形式：

输出格式1：在字符界面上输出这n个数的输出序列

输出格式2：将这n个数的输出序列写入到文件中

（3）   程序所能达到的功能：

对于输入的约瑟夫环长度n和间隔m，输出约瑟夫环的出列顺序。

（4）   测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。

正确：

输入：10,3                        

输出：3 6 9 2 7 1 8 5 10 4       

输入：41,3

输出：3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 16 31

错误：

输入：10 3

输出：6 8 7 1 3 4 2 9 5 10

2．  概要设计

（1）抽象数据类型的定义：

为实现上述程序的功能，可以用整数存储用户的输入。并将用户输入的值存储于线性表中。线性表ADT定义如下：

…… …… 余下全文

20##级数据结构实验报告

实验名称： 实验线性表实现约瑟夫问题求解

学生姓名： 

班 级： 

班内序号： 07

学 号： 

日 期： 20xx年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;

…… …… 余下全文

《数据结构》

实 验 报 告

实 验 课 程：   线性表的应用   

专       业：  **********      

 年级（班级）：  ******          

姓       名：  ***            

学       号：  ******          

实验报告

…… …… 余下全文