约瑟夫环问题实验报告书讲解

算法与程序设计

实验报告

实验课程： 约瑟夫环问题

专 业： 计算机与科学技术 班 级：

学 号：

姓 名：

一、课程设计的目的（需求分析）

【实验内容与要求】

问题描述：编号是1,2,„,n(n>0)的n个人按照顺时针方向围坐一圈，每人持有一正整数密码。开始时任选一个正整数作为报数上限值m，从某个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。令n最大值取30。设计一个程序来求出出列顺序，并输出结果。

【基本要求】：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各人的编号。

【实现提示】

由于该问题是由古罗马著名史学家Josephus提出的问题演变而来，所以通常称之为Josephus问题。Josephus问题的解决需要采用循环链表，先构造一个有n个结点的单循环链表，再给出一个报数上限值m(假设m>1)，在链表的首结点开始从1计数，计到m时，对应的结点从链表中删除，然后在被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。

本设计采用的是不带头结点的循环链表，其中循环链表中结点的结构如下： typedef struct

{ int num;

int cipher;

struct node *next;

}linklist;

该问题可由两部分组成，分别由如下两个算法完成：

（1）建立一个由头指针head指示的有n个结点的约瑟夫单循环链表creat。

（2）寻找、输出和删除head所指的单循环链表的第m个结点select。该算法由如

下具体步骤组成：

①在head中的第一个结点起循环记数找第m个结点；

②输出该结点的num值，把该结点的cipher(密码)值赋给m；

③删除该结点；

④转去执行①,直到所有结点被删除为止。

二、测试数据

进入程序，显示“1.开始游戏 0.退出游戏”输入非0数进入游戏，输入0退出游戏。

进入游戏后显示“输入总人数” ，输入大于0的整数；若输入错误，则光标处清空，重新输入。

后提示“输入开始人的序号” ；范围是大于零，小于总人数的整数，若输入错误，则光标处清空，重新输入。

后提示“输入间隔数字” ，范围是任意正整数；若输入错误，则光标处清空，重新输入。

按回车键，显示结果，并重新询问“1.开始游戏 0.退出游戏”。

三、算法思想

首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环本身具有循环性质，考虑采用循环链表，为了统一对表中任意节点的操作，循环链表不带头结点。循环链表的结点定义为如下结构类型：

typedef struct node

{

int data;

struct node *next;

}LNode;

其次，建立一个不带头结点的循环链表并由头指针p指示。

最后，设计约瑟夫环问题的算法。

1、工作指针first，r，s，p，q初始化

2、输入人数（n）和报数（m）

3、循环n次，用尾插法创建链表

int start=k-1;

LNode *s,*p,*L=0,*t;

if (start==0) start=n;

while (n!=0)

{

s=(LNode *)malloc(sizeof(LNode));

if (L==0) p=s;

if (n==start) t=s;

s->data=n;

s->next=L;

L=s;

n--;

}

p->next=L;

return t;

}

LNode* GetNode(LNode *p)/*出队函数*/

{

LNode *q;

for (q=p;q->next!=p;q=q->next);

q->next=p->next;

free (p);

return (q);

}

4、输入报数的起始人号数k;

5、循环n次删除结点并报出位置（其中第一个人后移k个）

当i移动指针k-1次s->next=L;

删除p结点的后一结点q

q=p;q->next!=p;q=q->next

q->next=p->next;

报出位置后free q;

计数器i++;

四、流程图

五、源代码

#include

#include

typedef struct node

{

int data;

struct node *next;

}LNode;

main()

{

LNode* Create(int,int);

LNode* GetNode(LNode *);

int Print(LNode *,int);

LNode *p;

int n,k,m;

int flag;

while(1)

{

printf(\"1.开始游戏 0.退出游戏\\n\"); scanf(\"%d\

if(!flag) break;

do

{

printf(\"请输入个数：\\n\");

scanf(\"%d\输入个数

if(n>30 || n <1)

{

printf(\"个数在1到30之间\\n\"); return 1;

}

}

while (n<=0);

do

{

printf (\"输入开始人的序号(1~%d)\

}

while (k<=0 || k>n);

do

{

printf (\"输入间隔数字\");

scanf (\"%d\

}

while(m<=0);

p=Create(n,k);

Print(p,m);

}

return 0;

}

LNode* Create(int n,int k)/*创建循环链表*/ {

int start=k-1;

LNode *s,*p,*L=0,*t;

if (start==0) start=n;

while (n!=0)

{

s=(LNode *)malloc(sizeof(LNode)); if (L==0) p=s;

if (n==start) t=s;

s->data=n;

s->next=L;

L=s;

n--;

}

p->next=L;

return t;

}

LNode* GetNode(LNode *p)/*出队函数*/ {

LNode *q;

for (q=p;q->next!=p;q=q->next); q->next=p->next;

free (p);

return (q);

}

Print(LNode *p,int m)/*输出函数*/ {

int i;

printf (\"出队编号:\\n\");

while (p->next!=p)

{

for (i=1;i<=m;i++)

p=p->next;

printf (\"%d \