目 录

1 需求分析*1

2 概要设计*4

3 详细设计*10

4 调试分析及测试*21

5 总结25

1 需求分析

​ 约瑟夫环桌前报数游戏，本游戏是来自于求解约瑟夫环问题的衍生，游戏规则是：已知一共由两队人，一个 n 个人参与游戏（以编号 1，2，3，…，n 分别表示）围坐在一张圆桌周围，从编号为 k 的人开始顺时针报数，第一次顺时针报数m的那个人出列；第二次逆时针报数他的下一个人又从 1 开始报数，数到n的那个人出列；然后又从他的下一个人顺时针又从1开始报数；依次重复下去。
​ 最后淘汰一半的人，剩下的人中，哪一个队伍的人数越多就获得本次胜利。
例如：
​ 有 5 个人，要求从编号为 3 的人开始，先顺时针数到3的那个人出列，然后数到2的那个人出列，反复报数最终只剩人数一半时停止。

讯享网

出列顺序依次为：

​ 编号为 3 的人开始，4 顺时针数 1，然后 5 数 2，然后 1 数 3，所以 1 先出列；

​ 1 出列后，从 2 开始，5 逆时针数 1，4 数 2，所以 4 出列；

​ 4 出列后，从 5 开始，3 顺时针数 1，2 数 2，5 数 3，所以 5 出列；

​ 最后剩余人数小于n/2;

​ 出局者编号为：1 -> 4 -> 5

​ 幸存者编号为：3 -> 2

1.1 选题理由

​ 据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置。这样当所有犹太人全部自杀后，他和他的朋友就逃过了这场死亡游戏。
​ 这是一类经典题目，实际应用中没怎么见过，在竞赛题目中会出现类似的题，其实，我觉得研究它主要的意义是在于算法能力的提高，这一类题目都是很有代表性的，很有意思；经典的东西，永远都是打基础的首选，万变不离其宗嘛，所以我们的教科书里才会经常出现这些经典的题目；
​ 一方面也是为了提高自己的算法水平，另一方给也是根据自己的知识功底和能力水平择选了约瑟夫环问题。 而且随着计算机技术的飞速发展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上。运用所学计算机知识来试着解决这个问题是个锻炼和提高我自己编程能力和独立解决问题能力的好机会，可以使我增强信心，为我以后的编程开个好头，故我选择了这个有趣的课题。此题还涉及了大量有关数据结构的知识，让我跟深入的理解数据结构的各种存储思想，加深对编程的理解。

1.2 涉及到的知识点

​ 通过这一学期的数据结构与算法课程的学习，利用双链表有关的数据结构相关的有对数据结构链表存储结构的理解，同时也对上学期所学习的C语言程序设计各种语法的熟练运用，对存储构建链表存储人数，变动出局者编号等数据存储问题所需变量的变量类型的分析，对各种循环、判断语句的灵活运用，对递归这种编程思想的深入理解与运用，灵活运用数组，链表，队列的不同场景的适用场景分析与运用，同时链表是数据结构中的最基础内容，也是学习数据结构全部内容的基础，其掌握的好坏直接影响着后继知识的学习。借此次关于约瑟夫环游戏的程序设计，正好能够更加深入的理解数据结构这门课程。加深对数据分析能力，选择不同存储结构的能力。

2 概要设计

2.1 功能模块设计

首先自己利用这学期所学的数据结构知识，构建出循环链表，其中循环链表，要有以下功能，
1.初始化循环链表；
2.对链表进行数据的插入；
3.获取首结点的信息；
4.根据位置删除链表中对应位置的信息；
5.根据值删除链表中匹配的信息；
6.获取链表的长度；
7.能判断链表是否为空；
8.提供查找链表中信息的功能；
9.打印所有链表中的所有信息的功能；
10.释放链表内存。
然后利用自己构造的这个循环链表实现对约瑟夫环问题的求解。

2.2 问题求解思路

（1）双向循环链表

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NmOpdel8-1671444137356)(file:///C:\Users\anuouan\AppData\Local\Temp\ksohtml14356\wps7.jpg)]

（2）公式法（数学公式法）
关于约瑟夫环问题，无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此 如果要追求效率，就要打破常规实施一点数学策略。
为了讨论方便，先把问题稍微改变一下，并不影响原意：
问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。
我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
k k+1 k+2 … n-2, n-1, 0, 1, 2, … k-2并且从k开始报0。
现在我们把他们的编号做一下转换：
k –> 0
k+1 –> 1
k+2 –> 2
…
…
k-2 –> n-2
k-1 –> n-1
解x’ —-> 解为x
注意：< x’就是最终的解 >
变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x’=(x+k)%n
如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 —- 这显然就是一个倒推问题！
下面举例说明：
假设现在是6个人（编号从0到5）报数，报到（2-1）的退出，即 < m=2>。那么第一次编号为1的人退出圈子，从他之后的人开始算起，序列变为2,3,4,5,0，即问题变成了这5个人报数的问题，将序号做一下转换：
2 –>0
3 –>1
4 –>2
5 –>3
0 –>4
现在假设x为0,1,2,3,4的解，x’设为那么原问题的解（这里注意，2,3,4,5,0的解就是0,1,2,3,4,5的解，因为1出去了，结果还是一个），根据观察发现，x与x’关系为x’=(x+m)%n，因此只要求出x，就可以求x’。x怎么求出呢？继续推导吧。0,1,2,3,4,，同样是第二个1出列，变为（2,3,4,0），转换下为：
2 –>0
3 –>1
4 –>2
0 –>3
很简单，同样的道理，公式又出来了，x=(x”+m)%5，这里变成5了。即求n-1个人的问题就是找出n-2的人的解，n-2就是要找出n-3，等等
因此，就可以回去看上面的推导过程了。
好了，思路出来了，下面写递推公式：
令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]
递推公式：
f[1]=0;
f[i]=(f[i-1]+m)%i; (i>1)
有了这个公式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1
由于是逐级递推，不需要保存每个f[i]，程序也是异常简单：

#include <stdio.h> int main() { 
    int n, m, i, s = 0; printf ("N M = "); scanf("%d%d", &n, &m); for (i = 2; i <= n; i++) { 
    s = (s + m) % i; } printf ("\nThe winner is %d\n", s+1); } 

2.3 存储结构定义

//定义双链表的结构；

讯享网typedef struct LNode { 
    int data; struct LNode *next, *front; } LNode; typedef struct { 
    LNode *rear, *prior; //队头、队尾指针； int size; //定义队列的长度，用于判断是否为空； } LinkLNode; 

2.4 功能函数介绍

//打印回调并返回
typedef int (*COMPARENODE)(CircleLinkNode *, CircleLinkNode *);
//打印回调不返回值
typedef void (*PRINTNODE)(CircleLinkNode *);
//链表初始化函数
CircleLinkList *Init_CircleLinkList();
//向链表中插入函数
void Insert_CircleLinkList(CircleLinkList *clist, int pos, CircleLinkNode *data);
//获取链表的第一个元素
CircleLinkNode *Front_CircleLinkList(CircleLinkList *clist);
//根据位置删除
void RemoveByPos_CircleLinkList(CircleLinkList *clist, int pos);
//根据值去删除
void RemoveByValue_CircleLinkList(CircleLinkList *clist, CircleLinkNode *data, COMPARENODE compare);
//获得链表的长度
int Size_CircleLinkList(CircleLinkList *clist);
//判断是否为空
int IsEmpty_CircleLinkList(CircleLinkList *clist);
//查找某个值在链表中的位置
int Find_CircleLinkList(CircleLinkList *clist, CircleLinkNode *data, COMPARENODE compare);
//打印所有结点节点信息
void Print_CircleLinkList(CircleLinkList *clist, PRINTNODE print);
//释放链表的内存
void FreeSpace_CircleLinkList(CircleLinkList *clist);

3 详细设计

根据上述的分析，下面给出详细代码：

#include <stdio.h> //scanf printf函数； #include <stdlib.h> //malloc free函数； //定义双链表的结构； typedef struct LNode { 
    int data; struct LNode *next, *front; } LNode; typedef struct { 
    LNode *rear, *prior; //队头、队尾指针； int size; //定义队列的长度，用于判断是否为空； } LinkLNode; 

//编写针对链表结构体操作的API函数

讯享网#define CIRCLELINKLIST_TRUE 1 #define CIRCLELINKLIST_FALSE 0 //比较回调 typedef int(*COMPARENODE)(CircleLinkNode*, CircleLinkNode*); //打印回调 typedef void(*PRINTNODE)(CircleLinkNode*); //初始化函数 CircleLinkList* Init_CircleLinkList(); //插入函数 void Insert_CircleLinkList(CircleLinkList* clist, int pos, CircleLinkNode* data); //获得第一个元素 CircleLinkNode* Front_CircleLinkList(CircleLinkList* clist); //根据位置删除 void RemoveByPos_CircleLinkList(CircleLinkList* clist,int pos); //根据值去删除 void RemoveByValue_CircleLinkList(CircleLinkList* clist, CircleLinkNode* data, COMPARENODE compare); //获得链表的长度 int Size_CircleLinkList(CircleLinkList* clist); //判断是否为空 int IsEmpty_CircleLinkList(CircleLinkList* clist); //查找 int Find_CircleLinkList(CircleLinkList* clist, CircleLinkNode* data, COMPARENODE compare); //打印节点 void Print_CircleLinkList(CircleLinkList* clist, PRINTNODE print); //释放内存 void FreeSpace_CircleLinkList(CircleLinkList* clist); #endif 

//针对链表结构体操作的API函数方法的实现

//初始化函数 CircleLinkList* Init_CircleLinkList(){ 
    CircleLinkList* clist = (CircleLinkList*)malloc(sizeof(CircleLinkList)); clist->head.next = &(clist->head); clist->size = 0; return clist; } //插入函数 void Insert_CircleLinkList(CircleLinkList* clist, int pos, CircleLinkNode* data){ 
    if (clist == NULL){ 
    return; } if (data == NULL){ 
    return; } if (pos <0 || pos > clist->size){ 
    pos = clist->size; } //根据位置查找结点 //辅助指针变量 CircleLinkNode* pCurrent = &(clist->head); for (int i = 0; i < pos;i++){ 
    pCurrent = pCurrent->next; } //新数据入链表 data->next = pCurrent->next; pCurrent->next = data; clist->size ++; } //获得第一个元素 CircleLinkNode* Front_CircleLinkList(CircleLinkList* clist){ 
    return clist->head.next; } //根据位置删除 void RemoveByPos_CircleLinkList(CircleLinkList* clist, int pos){ 
    if (clist == NULL){ 
    return; } if (pos < 0 || pos >= clist->size){ 
    return; } //根据pos找结点 //辅助指针变量 CircleLinkNode* pCurrent = &(clist->head); for (int i = 0; i < pos;i++){ 
    pCurrent = pCurrent->next; } //缓存当前结点的下一个结点 CircleLinkNode* pNext = pCurrent->next; pCurrent->next = pNext->next; clist->size--; } //根据值去删除 void RemoveByValue_CircleLinkList(CircleLinkList* clist, CircleLinkNode* data, COMPARENODE compare){ 
    if (clist == NULL){ 
    return; } if (data == NULL){ 
    return; } //这个是循环链表 CircleLinkNode* pPrev = &(clist->head); CircleLinkNode* pCurrent = pPrev->next; int i = 0; for (i = 0; i < clist->size; i++){ 
    if (compare(pCurrent, data) == CIRCLELINKLIST_TRUE){ 
    pPrev->next = pCurrent->next; clist->size--; break; } pPrev = pCurrent; pCurrent = pPrev->next; } } //获得链表的长度 int Size_CircleLinkList(CircleLinkList* clist){ 
    return clist->size; } //判断是否为空 int IsEmpty_CircleLinkList(CircleLinkList* clist){ 
    if (clist->size == 0){ 
    return CIRCLELINKLIST_TRUE; } return CIRCLELINKLIST_FALSE; } //查找 int Find_CircleLinkList(CircleLinkList* clist, CircleLinkNode* data, COMPARENODE compare){ 
    if (clist == NULL){ 
    return -1; } if (data == NULL){ 
    return -1; } CircleLinkNode* pCurrent = clist->head.next; int flag = -1; for (int i = 0; i < clist->size; i ++){ 
    if (compare(pCurrent,data) == CIRCLELINKLIST_TRUE){ 
    flag = i; break; } pCurrent = pCurrent->next; } return flag; } //打印节点 void Print_CircleLinkList(CircleLinkList* clist, PRINTNODE print){ 
    if (clist == NULL){ 
    return; } //辅助指针变量 CircleLinkNode* pCurrent = clist->head.next; for (int i = 0; i < clist->size;i++){ 
    if (pCurrent == &(clist->head)){ 
    pCurrent = pCurrent->next; printf("------------------\n"); } print(pCurrent); pCurrent = pCurrent->next; } } //释放内存 void FreeSpace_CircleLinkList(CircleLinkList* clist){ 
    if (clist == NULL){ 
    return; } free(clist); } 

//主函数方法实现

讯享网//插入数据； void InsertLink(LinkLNode &L, int data) { 
    LNode *p = (LNode *)malloc(sizeof(LNode)); p->data = data; if (L.rear == NULL) //判断插入的是否是第一个元素； { 
    p->next = p; p->front = p; L.prior = L.rear = p; } else { 
    p->next = L.rear->next; L.rear->next->front = p; p->front = L.rear; L.rear->next = p; L.rear = p; } L.size++; } //删除数据结点p；返回删除的下一个结点n； LNode *DeleteLink(LinkLNode &L, LNode *p) { 
    LNode *n = NULL; if (L.size == 0) //队列空报错； return n; if (L.size == 1) //删除的是最后一个元素； { 
    L.prior = L.rear = NULL; free(p); //释放指针p的指向； return n; } else if (L.prior->data != p->data) { 
    /* 在此程序中，每个指针指向的data数据不一样，可作为判断 是否是头指针的依据；在此需要保护双向链表的头指针的指向， 打印的时候需要头指针，而尾指针已经没有用处，不需要保护； */ p->front->next = p->next; p->next->front = p->front; } else { 
    L.prior = p->next; p->front->next = p->next; p->next->front = p->front; } n = p->next; free(p); L.size--; return n; } //结点s向前查找m个元素(逆时针) LNode *GetFront(LNode *s, int m) { 
    LNode *p; for (int j = 0; j < m; j++) p = s->front; return p; } //结点s向后查找n个元素(顺时针) LNode *GetBehind(LNode *s, int n) { 
    LNode *p = s; for (int j = 0; j < n; j++) p = s->next; return p; } //打印队列； bool PrintLink(LinkLNode L) { 
    if (L.size == 0) return false; LNode *p = L.prior; //定位链表的头指针指向； for (int j = 0; j < L.size; j++) { 
    printf("%d <-> ", p->data); p = p->next; } printf("NULL\n"); return true; } int main() { 
    LinkLNode people; LinkLNode delpeople; LNode *p; //定义旅客人数、正向离开间隔数、反向离开间隔数、开始人的位置 int pnum, fornum, renum, stnum; //初始化两个双向链表；用于存放旅客的情况； InitLink(people); InitLink(delpeople); printf("欢迎来到游戏，现在开始了！\n"); while (1) { 
    printf("输入总人数："); scanf("%d", &pnum); if (pnum > 0) break; } for (int i = 1; i < pnum + 1; i++) InsertLink(people, i); printf("输入顺时针报数规则 ？次："); scanf("%d", &fornum); printf("输入逆时针报数规则 ？次："); scanf("%d", &renum); printf("输入第一报数序号："); scanf("%d", &stnum); //进行游戏！！！！定位到开始人的位置； p = GetBehind(people.prior, stnum - 1); //淘汰一半的人； for (int j = 0; j < pnum / 2; j++) { 
    if (j % 2 == 0) //第一次顺时针； p = GetBehind(p, fornum); else p = GetFront(p, renum); InsertLink(delpeople, p->data); //将要淘汰的人加入到delpeople链表中； p = DeleteLink(people, p); //删除指定节点； if (p == NULL) { 
    printf("发生错误"); return 1; } } printf("离开者的编号为：\n"); PrintLink(people); printf("幸存者的编号为：\n"); PrintLink(delpeople); } 

4 调试分析及测试

4.1 遇到的问题及解决方法

1.调用模块时，结点结构的调用与其他模块产生冲突。导致每一行都出现两次错误，加入子函数的声明后错误消失。
2.刚开始时成忽略了一些变量参数的标识符“&”和“*”使用调试时费了很多时间，今后应重视确认参数的变量和赋值属性的区分和标识。
3.本次课程设计采用数据抽象的程序设计方法，将程序划分为三个层次结构。元素节点、单向循环链表，主控制模板，思路较为清晰，实现调用顺利。经过本次实验，使我对数据结构这门课程有了进一步的了解，每个程序经过需求分析，概要设计、详细设计之后，思路就清晰呈现出来了，随之而然程序也很快就出来了，最后经过调试。运行又有了新的体验。
4.细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上。在写主要操作函数caculate（）时，在终止条件的书写处不是很清楚，导致我浪费了很多时间。
5.还有一点很大的感触就是，在自己绞尽脑汁都解决不了遇到的问题时，一个很好的手段就是询问同学，寻求其帮助，就比如我在想函数终止条件时，同学一句简单的话语就让我如梦初醒。这不是什么丢脸的事情，相反的，在快速解决问题的同时，还会收获友谊，不是一举两得吗。我想，这也是合作学习的真谛吧。

4.2 算法的时空分析

双链表方法函数时空分析：
初始化链表操作，时间复杂度为O(1)，空间复杂度为O(1)。
向链表插入数据操作，时间复杂度为O(n)，空间复杂度为O(1)。
删除结点函数操作，时间复杂度为O(n)，空间复杂度为O(1)。
查找值操作操作，时间复杂度为O(n)，空间复杂度为O(1)。
输出打印函数操作，时间复杂度为O(n)，空间复杂度为O(1)。
因为使用的都是一些简单的思维逻辑运算，并没有使用复杂度过高的算法。

4.3 程序模块构架

本程序的模块划分比较清晰，将每个功能利用函数方法单独抽离出来定义，这要就能使下一次需要这个方法时候直接调用不必重复声明定义，使其整个程序结构简单明了，也便于后续的功能增加与维护，极大增强了程序的可维护性和健壮性。

4.4 程序使用说明

（1）本程序的运行环境为Windows操作系统
（2）使用的集成开放工具：Visual Studio Code
（3）主要编程语言：C语言
（4）运行编译环境使用的是：MinGW
（5） 运行程序显示页面：Windows的控制台页面

4.5 测试结果

这输入一个总人数为5，从第3个人开始报数，规则先顺时针报数3出局，然后逆时针报数2出局，最终人数小于总人数的一半后结束游戏，并输出打印幸存者编号和出局者编号，程序运行结果如下图所示：

这输入一个总人数为15，从第1个人开始报数，规则先顺时针报数5出局，然后逆时针报数9出局，最终人数小于总人数的一半后结束游戏，并输出打印幸存者编号和出局者编号，程序运行结果如下图所示：

这输入一个总人数为30，从第5个人开始报数，规则先顺时针报数7出局，然后逆时针报数9出局，最终人数小于总人数的一半后结束游戏，并输出打印幸存者编号和出局者编号，程序运行结果如下图所示：

5 总结

我的这次数据结构课程设计题目是：《约瑟夫环问题》，通过对该题目的设计，我加深了对数据结构及存储结构的理解，进一步的理解和掌握了课本中所学的各种数据结构。尤其是对单链表环链表上基本运算的实现，学会了如何把学到的知识用于解决实际问题，锻炼了自己动手的能力。
通过这次数据结构课程设计，我感受最深的是对于循环链表的使用，可以说对循环链表有了比以前更进一步的认识。以前只是一知半解，如果只给个题目，自己根本不能把程序完整的编写出来，所以这次课程设计最大的收获在于对循环列表有一定的理解，包括其中的一系列操作。如建立一个循环链表，删除节点中的一个结点，增加一个结点等。
在调试程序的时候，我也有所体会，虽然《约瑟夫环问题》不是很难。但调试的时候还是会出现很多错误，因此我们不能认为容易就不去认真对待，在以后的学习中要能不断发现问题，提出问题，解决问题。从不足之处出发，在不断学习和提高自己。
两周的课程设计虽然很短暂，但其间的内容却很充实，在其中我学习到了很多平时书本中无法学到的东西。不但积累了经验也锻炼了自己的分析能力，解决问题的能力。并且学会了如何将所学的各科知识融合。组织起来进行学习运用于实际，总而言之，这两周之中让我学会了很多。受益匪浅。

参考文献

[1]李春葆.数据结构教程(第五版)[M].北京:清华大学出版社,2017:2-77. [2]谭浩强.C程序设计(第五版)[M].北京:清华大学出版社,2017:139-330. [3]吕凤哲.C++语言程序设计(第二版)[M].北京:电子工业出版社,2005. 

记录：2022年12月1日~