约瑟夫环程序设计报告书

约瑟夫问题实验报告背景约瑟夫问题（Josephus Problem）据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。

然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

原题：用户输入M,N值，N个人围成一个环，从0号人开始数,数到M,那个人就退出游戏，直到最后一个人求最后一个剩下的人是几号？问题描述设编号为1-n的n(n>0)个人按顺时针方向围成一圈．首先第1个人从1开始顺时针报数．报m的人(m 为正整数)．令其出列。

然后再从他的下一个人开始，重新从1顺时针报数，报m的人，再令其出列。

如此下去，直到圈中所有人出列为止。

求出列编号序列。

一.需求分析：(1)基本要求需要基于线性表的基本操作来实现约瑟夫问题需要利用循环链表来实现线性表（2）输入输出格式输入格式：n，m(n,m均为正整数，)输出格式1：在字符界面上输出这n个数的输出序列(3)测试用例（举例）输入：8，4输出：4 8 5 2 1 3 7 6二．概要设计（1）抽象数据类型：数据对象：n个整数数据关系：除第一个和最后一个n外，其余每个整数都有两个元素与该元素相邻。

基本操作：查找，初始化，删除，创建链表循环链表的存储结构:（2）.算法的基本思想循环链表基本思想：先把n个整数存入循环链表中，设置第m个数出列，从第一个开始查找，找到第m个时，输出第m个数，并删掉第m个节点，再从下一个数开始查找,重复上一步骤，直到链表为空，结束。

（3）.程序的流程程序由三个模块组成：1.输入模块：完成两个正整数的输入，存入变量n和m中2.处理模块：找到第m个数3.输出模块：按找到的顺序把n个数输出到屏幕上三．详细设计首先，设计实现约瑟夫环问题的存储结构。

《数据结构》实验报告班级：姓名：学号：日期：08-10-20题目：约瑟夫环一、上机实验的问题和要求：问题描述：编号为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; /*编号*/int cipher; /*密码*/struct Lnode *next; /*指针*/}Lnode,*CLinklist; /*重定向命名*/CLinklist H; /*Ｈ为全局单链表*/算法的实现详见源程序。

输入/输出设计本程序并未采用任何二进制文件出入的方式，这点说明将在最后总结提到。

至于函数的出入口问题，在源程序及注释中将得到详细说明，这里不再赘述。

三、源程序及注释：(说明函数功能、入口及出口参数,其他)#include <stdio.h> /* 头文件*/#include <stdlib.h>#include <alloc.h>typedef struct Lnode /*定义单链表*/{int number; /*编号*/int cipher; /*密码*/struct Lnode *next; /*指针*/}Lnode,*CLinklist; /*重定向命名*/CLinklist H; /*Ｈ为全局单链表*/struct Lnode *crt_CLinkList(CLinklist H,int m) /*创建一个不带头结点的单向循环链表*/{ /*其中，Ｈ为全局单链表，m为链表结点总数*/ int i; /*循环记数用*/struct Lnode *ptr1; /*用于索引*/if((ptr1=(struct Lnode *)malloc(sizeof(struct Lnode)))==NULL) /*一旦动态内存分配失败，报错退出！*/ {perror("malloc");return ptr1;}H=ptr1; /*形成单个结点的单循环链表*/ptr1->next=H;for(i=1;i<m;i++) /*形成m个结点的不带头结点的单循环链表*/ {if((ptr1->next=(struct Lnode *)malloc(sizeof(struct Lnode)))==NULL){perror("malloc");ptr1->next=H;return H;}ptr1=ptr1->next; /*其中Ｈ指头，ptr指尾*/ptr1->next=H;}return H; /*返回成功新建的单链表Ｈ*/}void locfor(CLinklist H,int m) /*寻找输出删除链表Ｈ中的第m个结点*/{ /*H为全局链表，m为要查找删除的结点位置*/ int i; /*循环计数*/struct Lnode *ptr;for(i=1;i<=5;i++) /*考虑图形界面的美观问题*/printf("number\tcipher\t");i=1; /*初始化*/while(H->next!=H) /*只剩单个结点时停止循环，进行最后输出！*/ {if(m==1) /*考虑进行自身删除的情况，即m=1*/{for(ptr=H->next;ptr->next!=H;ptr=ptr->next);/*正因为是自身删除才要费大劲寻找其父结点*/printf("%-6d\t",H->number); /*找到后，先输出*/printf("%-6d\t",H->cipher);m=H->cipher; /*确定下一次寻找的m值*/ptr->next=H->next; *删除结点，即自身结点*/ptr=ptr->next;free(H); /*因为对于链表中的结点，每个之前都分配了内存，所以free是必要的*/H=ptr; /*不同于以下普通结点的删除，自身删除还要还原H*/i=1; /*i重置，以方便下一次的循环操作*/}else if(i==m-1) /*因为从自身开始即为1号，因为m-1,而不是m*/{ptr=H->next; /*结点的删除操作同于上面的情况!*/printf("%-6d\t",ptr->number);printf("%-6d\t",ptr->cipher);m=ptr->cipher;H->next=ptr->next;H=H->next;free(ptr);i=1;}else{H=H->next; /*若未找到，则继续遍历！*/i++;}}printf("%-6d\t",H->number); /*对于单个结点的单循环链表，进行最终的输出操作！*/ printf("%-6d",H->cipher);free(H); /*完成所有任务并释放所有内存占用！*/}void main() /*主函数接口*/{ /*调用所有函数，进行实验模拟，并得出实验结果！*/ int i,j,n=30,m,k;struct Lnode *ptr;randomize(); /*因为下面调用了random函数，故此处的初始化很有必要！*/ printf("Now the experiment will begin.You have two choices!\n");/*数据输入可以电脑随机，也可以自行输入*/printf("If you want to enter the datas all by yourself,please enter 1.\n");/*自行输入（方便检测程序问题）*/ printf("If you want to get the datas by the computer,please enter 0.\n"); /*电脑随机产生数据*/printf("Now your choice:"); /*用户选择*/scanf("%d",&j);while(j!=0&&j!=1) /*考虑程序的完善性，对于误输入的提示并报警！*/ {printf("\nYou enter is unillage!Please try again!\n");printf("Now your choice:"); /*重新输入*/scanf("%d",&j);}H=crt_CLinkList(H,n); /*初始化链表*/if(j==0) /*电脑随机充入数据*/for(i=1;i<=30;i++){H->number=i;H->cipher=rand(); /*随机函数*/H=H->next;}else /*此时选择实验者输入数据！*/{for(i=1;i<=30;i++){H->number=i;printf("Now number %d,please enter the cipher:",i);scanf("%d",&k);H->cipher=k;H=H->next;}}m=rand(); /*默认情况下，m随机产生*/printf("Do you want to enter the number m?Enter 1 to set or others cancel!\n");/*当然，如果想自已输，可以进行覆盖*/scanf("%d",&k);if(k==1) /*自行输入m值*/{printf("Please enter the number m:");scanf("%d",&m);}system("cls"); /*考虑屏幕大小，进行分屏显示*/printf("All followed are your datas!\n"); /*界面友善*/for(i=1;i<=5;i++)printf("number\tcipher\t");for(i=0;i<30;i++) /*显示所有处理前数据*/{printf("%-6d\t",H->number);printf("%-6d\t",H->cipher);H=H->next;}printf("And the number m is :%d\n",m);printf("\nAfter the program,the result is:\n");locfor(H,m); /*对所有数据进行实验处理，直至所有结点处理完！*/ getchar();printf("\nPress any key return!"); /*TC环境下，方便查看结果！*/getchar();}四、用户使用说明与测试运行结果：1．运行程序后，首先弹出界面，截图如右：理性化的选择：如果打1，则所有的cipher均由用户输入，这样方便对特殊数据进行程序测试！如果打0，那么所有的数据均由电脑产生！那如果打其他的呢？考虑到误输入，加了一个循环，以提高程序的健壮性！2．首先自行输入数据进行测试。

pNew->next = pCur->next;
pCur->next = pNew;
pCur = pNew;
printf("结点%d,密码%d\n",pCur->id, pCur->cipher);
}
}
printf("完成单向循环链表的创建!\n");
}
(3)运行"约瑟夫环"问题
static void StartJoseph(NodeType **, int)
exit(-1);
}
pNew->id = iId;
pNew->cipher = iCipher;
pNew->next = NULL;
return pNew;
}
(6)测试链表是否为空,空为TRUE，非空为FALSE
static unsigned EmptyList(const NodeType *pHead)
实验内容
利用循环链表实现约瑟夫环求解。
实验说明
1.问题描述
约瑟夫问题的：编号为1，2，....,N的N个人按顺时针方向围坐一圈,每人持有一个密码(正整数)，一开始任选一个正整数作为报数上限值M，从第一个人开始按顺时针方向自1开始顺序报数，报到M时停止报数。报M的人出列，将他的密码作为新的M值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。
{
if(!pHead)
{
return TRUE;
}
return FALSE;
}
实验中遇到的问题及解决方法
实验结果如下：
实验总结（结果和心得体会）

约瑟夫环问题实验报告一、实验内容本实验利用单向循环链表模拟约瑟夫环问题（编号为1,2，…，n的n个人按顺时针方向围坐一圈，没人持有一个密码（正整数）。

开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始报数，报到m是停止报数。

报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止），按照出列顺序印出个人的编号。

M的初值为20，n=7,7个人的密码依次为3,1,7,2,4,8,4，首先m值为6。

二、源程序#include"stdafx.h"#include<iostream>using namespace std;#include<conio.h>//getch();/*write: Han.JH*/static int people_number_count; typedef struct People_Node{int Password_Data,people_number;struct People_Node *next;}People_Node,*People_LinkList;void GreatList(People_LinkList &L){People_Node *s,*r; int flag=1;int Password;L=new People_Node;L->next=NULL;r=L;while(flag==1){cout<<"输入每个人的密码,以回车作间隔,'0'表示结束:";cin>>Password;//输入每个人的密码；if(Password!=0){s=new People_Node;s->Password_Data=Password;people_number_count++; //对人的编号s->people_number=people_number_count;r->next=s;r=s;}else{ r->next=L->next;flag=0;}}}void GetList(People_LinkList &L){People_Node *r;int m,k;int count=0;cout<<"输入报数上限值m:";cin>>m;r=L;cout<<"出列排序:";while(count!=people_number_count){ //则所有人以出列，结束循环for(k=1;k<=m-1;k++){r=r->next;}count++;m=r->next->Password_Data;cout<<"["<<r->next->people_number<<"]";r->next=r->next->next;}}void main(){People_LinkList L;void GreatList(People_LinkList &);void GetList(People_LinkList &);cout<<"++++++++++++约瑟夫环问题+++++++++++"<<endl;GreatList(L);GetList(L);cout<<"[--结束--]"<<endl;getch();}三、调试刚开始调试时出现了无法打开<iostream.h>头文件的错误，经过上网查询，#include<iostream.h>是C语言风格，但是在标准 C 里面,是不用#include <iostream.h>的，而要使用#include <iostream>把#include<iostream.h>改为：#include<iostream>using namespace std;后，问题解决。