爱玩科技网

全部频道

您的当前位置：首页约瑟夫环

约瑟夫环

来源：爱玩科技网


仲 恺 农 业 工 程 学 院

课 程 设 计 报 告

课程名称：院 （系）：专业班级：学 号 姓 名

指导老师：数据结构 1

承诺书

郑重声明：本人所呈交的课程设计是本人在导师指导下撰写并完成的，课程设计没有剽窃、抄袭、造假等违反学术道德、学术规范和侵权行为。本课程设计不包含任何其他个人或集体已经发表或撰写过的研究成果，如果引用则标识出了出处。对本课程设计的研究做出贡献的个人和集体，均已在文中以明确方式标明。

课程设计与资料若有不实之处，本人承担一切相关责任。特此声明。

签名：

年 月 日

2

目录

一、数据结构设计 ...................................................................................................................... 4 二、算法设计 .............................................................................................................................. 5 三、详细设计（关键代码） ...................................................................................................... 8 四、调试分析 ............................................................................................................................ 19 五、课程设计总结 .................................................................................................................... 20 参 考 文 献 ........................................................................................................................ 21

3

一、数据结构设计 1、问题描述

编号为1，2… n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。

2.功能要求

A利用单循环链表作为存储结构模拟此过程； B键盘输入总人数、初始报数上限值m及各人密码； C按照出列顺序输出各人的编号。

3.分析

通过题目的功能要求，我知道要解决约瑟夫环问题，就需要用到单向循环链表的知识。首先我应该清楚了解单循环链表的定义，对循环链表的插入赋值以及遍历循环链表，当然最重要的还是单循环链表结点的删除—也就对应着约瑟夫环中人数编号的出列。

除此之外，我觉得既然将这么一个报数问题编程，那不如编成一个游戏吧，这个游戏很简单，当游戏操作者在键盘中输入总人数以及个人密码时，程序紧跟着本应直接输出出列编号，但是我若将正确结果放进一个数组，然后等游戏者推理再输入他认为的出列编号放进另一个数组，最后将2个数组进行对比，若相同则参加游戏的人成功了，这也算是一种小小的益智游戏

4

二、算法设计

（一）程序设计概述： 为实现约瑟夫环中：

A利用单循环链表作为存储结构模拟此过程； B键盘输入总人数、初始报数上限值m及各人密码； C按照出列顺序输出各人的编号。

这些功能要求，首先需要定义单向循环链表，然后逐渐用单循环链表的不同功能模块。 typedef struct LNode {

int number; int data;

struct LNode *next;

}LNode, *LinkList; //定义单向循环链表

基本运算是：

LinkList EvaluList(int n);/* 对单向循环链表进行尾插入赋值*/ Status DisplayList(LinkList &L);/*单向循环链表的输出*/ int size(LinkList L);/*求链表的节点个数*/ Status ScanList(LinkList L);/*遍历单向循环链表*/

int ListLength(LinkList &L);/*返回单向循环链表的长度*/ Status ListDelet(LinkList L,int *e); /*删除单循环链表的结点*/

Status Joseph(LinkList &L,int m); //约瑟夫环的实现

int check(int *t,LinkList &L,int m);//判断游戏者输入的编号是否与实际出列编号相符合 除此之外，还用到一些抽象数据类型常量： #define max 100

5

#define TRUE 1 #define FALSE 0 #define OK 1 typedef int Status; typedef double ElemType;

另外，为求运行窗口的美观，以及能给游戏者一个愉悦的心情，我使用了清屏

的功能：

#include system(\"cls\");

6

（二）算法设计流程图 a)约瑟夫环主函数流程图

开 始 inttemp[max]; cout<<\"\\"<<\"*************n<=1 cout<<\"\\"<<\"输入人数不适cout<<\"\\"<<\"请输入密码 m<=1 cout<<\"\\"<<\"密码范围有误cout<>temp[j]; cout<<\"\\"<7

图7 约瑟夫环流程图

三、详细设计（关键代码）

1）约瑟夫环游戏的主函数： #include #include #define max 100 #define TRUE 1 #define FALSE 0 #define OK 1

using namespace std; typedef int Status; typedef double ElemType;

//定义单向循环链表 typedef struct LNode {

int number; int data;

struct LNode *next;

}LNode, *LinkList;

//-----------------------------------

LinkList EvaluList(int n);/* 对单向循环链表进行尾插入赋值*/ Status DisplayList(LinkList &L);/*单向循环链表的输出*/ int size(LinkList L);/*求链表的节点个数*/ Status ScanList(LinkList L);/*遍历单向循环链表*/ int ListLength(LinkList &L);/*返回单向循环链表的长度*/

8

Status ListDelet(LinkList L,int *e); /*删除单循环链表的结点*/

Status Joseph(LinkList &L,int m);/*约瑟夫环的实现 */ int check(int *t,LinkList &L,int m);

/*判断游戏者输入的编号是否与实际出列编号相符合*/

//------------------------------------------------- void main() { l;

cout<<\"\\"<<\"* cout<<\"\\"<<\"******************************************************\"<*\"<cout<<\"\\"<<\"* *\"<cout<<\"\\"<<\"* --------------约瑟夫环---------------

*\"<cout<<\"\\"<<\"* -------------- Joseph ---------------

*\"<cout<<\"\\"<<\"* 欢迎您进入本游戏，祝您游戏愉快！

*\"<cout<<\"\\"<<\"*

*\"<cout<<\"\\"<<\"* *\"<9

cout<<\"\\"<<\"* 游戏正式开始！！ ！ *\"<cout<cout<<\"\\"<<\"******************************************************\"<int n; int m;

cout<<\"\\"<<\"请输入人数:\"; cin>>n; if(n<=1)

{

cout<<\"\\"<<\"您所输入人数不适合，请重新输入:\"<>n; cout<}

cout<<\"\\"<<\"请输入初始密码（正整数）:\"; cin>>m; if(m<=1) {

cout<<\"\\"<<\"您所输入的密码范围有误，请重新输入密码:\"<>m;

}

cout<cout<<\"\\"<<\"--------------------------------------\"<cout<<\"\\"<<\"--------------------------------------\"<LinkList L=EvaluList(n);

DisplayList(L);

10

cout<cout<<\"\\"<cout<<\"\\"<<\"请根据密码和人数输入约瑟夫序列:\"<<\"\\"<cin>>temp[j];

do {

if(check(temp,L,m)==0)

{

cout<<\"\\"<<\"很遗憾！您输入的序列错误!\"<cout<<\"\\"<<\"1.请重新输入序列,2.或选择查看正确结果\"<cin>>i;

cout<<\"\\"<<\"请输入序列:\"<if(i==1)

for(int j=0;j>temp[j]; else

{

cout<<\"\\"<Joseph(L,m); break; }

}

else {

cout<<\"\\"<<\"结果正确，你好聪明!\"; cout<break; }

11

}while(i==1);

cout<cout<<\" **************感谢您参加本游戏!*********** \"<cout<<\" --------------Joseph------------------ \"<cout<<\" --------------约瑟夫环---------------- \"<>i; system(\"cls\"); }while(i==1);

}

//---------对单向循环链表进行尾插入赋值----------------

LinkList EvaluList(int n) { if(n==0) return NULL; int key;

cout<<\"\\"<<\"输入第1个人的密码: \"; cin>>key;

LinkList L=new LNode; L->data=key; L->number=1; L->next=L;

for(int i=2;i<=n;i++)

{

12

}

}

LinkList p=new LNode; int key;

cout<<\"\\"<<\"输入第\"<>key; p->data=key; p->number=i; p->next=L->next; L->next=p; L=L->next;

cout<next; return L;

//------------单向循环链表的输出------------------

Status DisplayList(LinkList &L) {

//输出循环链表L struct LNode *p,*Head; if(L) { Head=L; p=Head;

cout<<\"\\"<<\"约瑟夫环人员情况单向循环链表的如下：\"; cout<cout<<\"\\"<<\"List Head\"; do

13

{

cout<<\"->\"<data; p=p->next;

}

while(p!=Head); cout<cout<<\"\\"<<\"单链线性表为空！\"<//---------------求链表的节点个数-------------------

int size(LinkList L) { }

if(L==NULL)

return 0;

int i=1;

LinkList p=L->next; while(p!=L) { } return i;

i++; p=p->next;

14

//---------------遍历单向循环链表--------------------

Status ScanList(LinkList L) { }

//----------单向循环链表的长度-----------------------

int ListLength(LinkList &L) {

LinkList p=L; if(p==NULL) { }

cout<<\"\\"<<\"第1个人的密码: \"; cout<data; cout<next; while(p!=L) { }

cout<cout<<\"\\"<<\"第\"<number<<\"个人的密码 : \"; cout<data; cout<next;

cout<<\"人数为空!\"<15

//返回循环链表的长度 return L->number; }

//---------------删除单循环链表的结点--------------------

Status ListDelet(LinkList L,int *e) { }

//----------------约瑟夫环的实现-----------------------

int i;

LinkList p=(L)->next,q; int j=0;

if(i<=0||i>ListLength(L))

return FALSE;

while(jq=p->next; p->next=q->next; *e=q->data; if(L==q)

L=p; p=p->next; j++;

free(q); return OK;

16

Status Joseph(LinkList &L,int m) { }

//---------核对游戏者输入的出列编号---------------------------

int check(int *t,LinkList &L,int m) {

if(L==NULL) { }

LinkList p=L; while(p->next!=L)

p=p->next;

cout<<\"\\"<<\"人数为空，出列结束\"; cout<for(int n=size(L); n>0 ; n--) { }

return OK;

cout<<\"\\"<<\"密码为\"<next;

cout<next->number; cout<next->data; LinkList q=p->next; p->next=q->next; free(q);

17

int text[max]; int st[max]={0}; int k=0; LinkList p=L; while(p->next!=L)

p=p->next;

for(int n=size(L); n>0 ; n--) { for(int i=1; i<=m-1||st[p->next->number]==1; i++) { if(st[p->next->number]==1)

i--;

p=p->next; }

text[k++]=p->next->number;

m=p->next->data;

st[p->next->number]=1; }

for(int i=0;i}

}

return OK;

}

18

四、调试分析

这是约瑟夫环游戏的主界面：

当然，界面里输入的人数以及初始密码由游戏者自己设定，只要人数不超过100人，密码只要求是正整数。那么在接下来的游戏环节当中，当程序提醒游戏者根据密码输入自己计算出来的出序号码，然后，程序里check函数中text[]，st[]将正确答案与游戏者输入的序列进行核对。

a)当游戏者输入序列不正确时：

19

b)当游戏者输入的序列编号与答案相符时：

五、课程设计总结

小结一下，这次课程设计的综合题目之一 ，约瑟夫环问题中要深入学习单链表以及循环链表的知识，首先对于尾插法，遍历，求结点数等等的算法要熟悉，然后这么一个报数游戏跟猴子选大王的原理其实差不多，然后在整个约瑟夫环的实现过程中，开始求出列人的编号时我用cout<<\"密码为\"<20

i++)；p=p->next;的代码，结果没到最后2个人时，输出结构都是错误的，经过分析之后改为for(int i=1; i<=m-1; i++)；p=p->next;结果才是对的。然后不足的是界面控制不大好，我设置不了输入你认为的出列编号的格式与其他的对齐。

另外通过一周的课程设计之后，培养了我选用参考书，查阅手册及文献资料的能力，培养思考，深入研究，分析问题、解决问题的能力，提高综合运用本课程所学知识的能力，还对设计的基本过程的设计方法、步骤、思路、有一定的了解与认识，并对存储结构，比如线形表、链表、循环链表、树、图等存储结构，特别是对单循环链表理解的更深。也使我认识到《数据结构》这门课程是计算机程序设计的重要理论技术基础，在我们计算机专业的学习中占据着十分重要的地位。同时也使我知道，要学好这门课程，仅学习书本上的知识是不够的，还要有较强的实践能力。因为我们学习知识就是为了实践。而只有多实践，多编写程序，才能更好的理解与掌握书本上的东西。

本次课程设计的主题是用单循环链表来模拟约瑟夫环游戏，由于刚开始对循环链表的理解不够，也没理请约瑟夫环的基本思路，做起来有点难，但通过反复的修改，最终还是能够理解。

我学到了很多的东西，通过实际编译系统的分析设计、编程调试，也掌握了一些工程设计方法。现在也能够按要求编写课程设计报告书，能正确阐述设计和实验结果，正确绘制程序框图。课程设计是把我们所学的理论知识进行系统的总结并应用于实践的良好机会，有利于加强我们用知识理论来分析实际问题的能力，进而加强了我们对知识认识的实践度，巩固了我们的理论知识，深化了对知识的认识，并为走向社会打下一个良好的基础。

参 考 文 献

[1] 数据结构教程（第3版） [2] c++面向对象程序设计（第二版）

21

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文