一 问题的引入

约瑟夫问题的源头完全可以命名为“自杀游戏”。本着和谐友爱和追求本质的目的,可以把问题描述如下:

* 现有n个人围成一桌坐下,编号从1到n,从编号为1的人开始报数。
* 报数也从1开始,报到m人离席,从离席者的下一位在座成员开始,继续从1开始报数。
* 复现这个过程(各成员的离席次序),或者求最后一个在座的成员编号。

二 思路的讲解

1. 想必我们看到这个游戏场景,再结合链表相关的知识,我们也就大概有了一个方向了吧~~~

没错,解决约瑟夫问题的关键就是创建一个带环链表

 2.当我们链表创建好之后,就是考虑如何讲单链表转换成带头循环链表

是滴,就是将我们的链表的尾结点指向我们的头节点即可

ptail->next = phead;

 对应代码如下:
ListNode* CreatList(int x)//链表创建 { ListNode* phead =
ListBuyNode(1);//注意是从数据1开始为每一个人创建结点 ListNode* ptail =
phead;//注意当链表只有一个数据时,头节点也是尾结点 //来到这里说明头节点已经创建好,下面就需要进行尾插即可,尾插之前需找到前面的结点 for
(int i = 2; i <= x; i++) { ListNode* node = ListBuyNode(i); ptail->next = node;
ptail = ptail->next;//尾结点时刻更新 } //以上只是单链表创建好了,下面需把他变成单向循环链表 ptail->next =
phead; return ptail;//返回尾结点即可,有了尾结点可以直接找到头节点,若是返回头节点,需要遍历才可以找到尾结点 }

3.以上我们把前期准备工作已经做好了,接下来我们开始约瑟夫游戏

其实就是一个删除结点的问题

注意我们这里不能直接删除结点

1.)删除结点之前我们需要先找到这个结点的前一个结点,也就是pre这个结点

2.)其次就是找到这个结点的后一个结点,即pcur->next;

3.)最最最重要的是,我们在删除这个结点之后,不要忘了让下一个人重新报数

草图如下:

 代码如下:

 接下来重复以上操作即可,也就是对应代码里面的循环,具体详见代码:
while (pcur->next != pcur) { if (count == m) { //报到为m 的人直接删除就Ok pre->next =
pcur->next; free(pcur);//此时pcur是个野指针 pcur = pre->next; count =
1;//删除结点后,别忘了count 是从1重新开始报数 } else { pre = pcur;//pcur移动之前,需让pre 来保存pcur位置,
pcur = pcur->next; count++;//注意别忘了要报数 } }
相信各位对以上的分析应该有了自己的理解了吧~~~

 

对于IO答题方式:完整代码如下:
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<assert.h>
#include<malloc.h> int yef(int x, int y); typedef struct ListNode { int
val;//数据域 struct ListNode* next;//指针域 }ListNode;//重命名 ListNode* ListBuyNode(int
x)//创建结点 { ListNode* node = (ListNode*)malloc(sizeof(ListNode)); if (node ==
NULL)//会存在开辟失败 { perror("malloc fail\n"); return 5; } //空间开辟成功 node->val = x;
node->next = NULL; return node; } ListNode* CreatList(int x)//链表创建 { ListNode*
phead = ListBuyNode(1);//注意是从数据1开始为每一个人创建结点 ListNode* ptail =
phead;//注意当链表只有一个数据时,头节点也是尾结点 //来到这里说明头节点已经创建好,下面就需要进行尾插即可,尾插之前需找到前面的结点 for
(int i = 2; i <= x; i++) { ListNode* node = ListBuyNode(i); ptail->next = node;
ptail = ptail->next;//尾结点时刻更新 } //以上只是单链表创建好了,下面需把他变成单向循环链表 ptail->next =
phead; return ptail;//返回尾结点即可,有了尾结点可以直接找到头节点,若是返回头节点,需要遍历才可以找到尾结点 } int ysf(int
n, int m) { ListNode* ptail = CreatList(n);//为1~n个人创建单循环链表,注意链表创建返回的就是尾结点
//开始游戏,涉及到删除结点,注意不能直接删除,删除前需要先找到对应的前一个结点和后一个结点 ListNode* pcur =
ptail->next;//游戏是从第一个人开始的 ListNode* pre = ptail;//当前节点的前一个结点 int count =
1;//就是一个报数器,注意是从1开始的而不是0开始的,因为游戏是从第一个人开始 while (pcur->next != pcur) { if (count
== m) { //报到为m 的人直接删除就Ok pre->next = pcur->next; free(pcur);//此时pcur是个野指针 pcur
= pre->next; count = 1;//删除结点后,别忘了count 是从1重新开始报数 } else { pre =
pcur;//pcur移动之前,需让pre 来保存pcur位置, pcur = pcur->next; count++;//注意别忘了要报数 } }
//此时只剩一个结点 return pcur->val; } int main() { int ret = ysf(43,9001);
printf("%d", ret); return 0; }
对于OJ的答题方式,完整代码如下
//解答思路 首先创建一个带头单向循环链表 其次删除这个链表的结点,注意不能直接删除,要找到删除此节点的前一个和后一个结点 typedef struct
ListNode ListNode;//重命名 ListNode* ListBuyNode(int x)//创建结点 { ListNode* node =
(ListNode*)malloc(sizeof(ListNode)); if(node == NULL)//会存在开辟失败 { perror("malloc
fail\n"); } //空间开辟成功 node->val = x; node->next = NULL; return node; } ListNode*
CreatList(int x)//链表创建 { ListNode* phead = ListBuyNode(1);//注意是从数据1开始为每一个人创建结点
ListNode* ptail = phead;//注意当链表只有一个数据时,头节点也是尾结点
//来到这里说明头节点已经创建好,下面就需要进行尾插即可,尾插之前需找到前面的结点 for(int i = 2;i <= x;i++) { ListNode*
node = ListBuyNode(i); ptail->next = node; ptail = ptail->next;//尾结点时刻更新 }
//以上只是单链表创建好了,下面需把他变成单向循环链表 ptail->next = phead; return
ptail;//返回尾结点即可,有了尾结点可以直接找到头节点,若是返回头节点,需要遍历才可以找到尾结点 } int ysf(int n, int m ) {
ListNode* pre = CreatList(n);//为1~n个人创建单循环链表,注意链表创建返回的就是尾结点
//开始游戏,涉及到删除结点,注意不能直接删除,删除前需要先找到对应的前一个结点和后一个结点 ListNode* pcur =
pre->next;//游戏是从第一个人开始的 int count = 1;//就是一个报数器,注意是从1开始的而不是0开始的,因为游戏是从第一个人开始
while(pcur->next != pcur) { if(count == m) { //报到为m 的人直接删除就Ok pre->next =
pcur->next; free(pcur);//此时pcur是个野指针 pcur = pre->next; count =
1;//删除结点后,别忘了count 是从1重新开始报数 } else { pre = pcur;//pcur移动之前,需让pre 来保存pcur位置,
pcur = pcur->next; count++;//注意别忘了要报数 } } //此时只剩一个结点 return pcur->val; }
 各位大佬都已经来这里了,若是觉得还不错,咱点个赞,互关一下呗,蟹蟹大家了,小生有礼了。

技术
今日推荐
阅读数 155
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信