旅游网站模板大全,做网站主机选择,企业信息管理系统登录,长寿网站制作一 问题的引入
约瑟夫问题的源头完全可以命名为“自杀游戏”。本着和谐友爱和追求本质的目的#xff0c;可以把问题描述如下#xff1a;
现有n个人围成一桌坐下#xff0c;编号从1到n#xff0c;从编号为1的人开始报数。报数也从1开始#xff0c;报到m人离席#xff0c…一 问题的引入
约瑟夫问题的源头完全可以命名为“自杀游戏”。本着和谐友爱和追求本质的目的可以把问题描述如下
现有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 的人直接删除就Okpre-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
#includestdio.h
#includeassert.h
#includemalloc.hint 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 的人直接删除就Okpre-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 的人直接删除就Okpre-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;}各位大佬都已经来这里了若是觉得还不错咱点个赞互关一下呗蟹蟹大家了小生有礼了。
