头脑风暴之约瑟夫环问题
一 问题的引入
约瑟夫问题的源头完全可以命名为“自杀游戏”。本着和谐友爱和追求本质的目的,可以把问题描述如下:
- 现有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
#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 的人直接删除就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;}
各位大佬都已经来这里了,若是觉得还不错,咱点个赞,互关一下呗,蟹蟹大家了,小生有礼了。
相关文章:
头脑风暴之约瑟夫环问题
一 问题的引入 约瑟夫问题的源头完全可以命名为“自杀游戏”。本着和谐友爱和追求本质的目的,可以把问题描述如下: 现有n个人围成一桌坐下,编号从1到n,从编号为1的人开始报数。报数也从1开始,报到m人离席,…...
【四:Spring整合Junit】
目录 相同点不同点1、导入依赖增加2、编写的位置不同。。路径一定要与实现类一致 相同点 前面都一样和Spring整合mybatis(基于注解形式)一样Spring整合Mybatis 不同点 1、导入依赖增加 <!-- 单元测试 --><dependency><groupId>junit&…...
openHarmony UI开发
常用组件和布局方式 组件 ArkUI有丰富的内置组件,包括文本、按钮、图片、进度条、输入框、单选框、多选框等。和布局一样,我们也可以将基础组件组合起来,形成自定义组件。 按钮: Button(Ok, { type: ButtonType.Normal, stateEf…...
Qt 目录操作(QDir 类)及展示系统文件实战 QFilelnfo 类介绍和获取文件属性项目实战
一、目录操作(QDir 类) QDir 类提供访问系统目录结构 QDir 类提供对目录结构及其内容的访问。QDir 用于操作路径名、访问有关路径和文件的信息以及操作底层文件系统。它还可以用于访问 Qt 的资源系统 Qt 使用“/”作为通用目录分隔符,与“/”在 URL 中用作路径分…...
2023-9-12 阿里健康2024秋招后端开发-体检及泛医疗二面
1 自我介绍 2 快手实习 2.1 说说你在实习期间遇到的挑战、收获 (1)在设计模式的应用能力上,有了很大的提高,使用模板设计模式,架构实例反向同步到架构定义,使用了策略模式 (2) …...
Qt扫盲-QBrush理论使用总结
Q 理论使用总结 一、概述1. 填充模式2. 笔刷颜色3. 纹理 二、 Qt::GlobalColor 一、概述 QBrush类定义了由 QPainter 绘制的形状的填充模式。画笔有样式、颜色、渐变和纹理。 brush style() 使用Qt::BrushStyle 枚举定义填充模式。默认的笔刷样式是 Qt::NoBrush(取决于你如何…...
互联网Java工程师面试题·Java 面试篇·第三弹
目录 39、JRE、JDK、JVM 及 JIT 之间有什么不同? 40、解释 Java 堆空间及 GC? 41、你能保证 GC 执行吗? 42、怎么获取 Java 程序使用的内存?堆使用的百分比? 43、Java 中堆和栈有什么区别? 44、“ab”…...
如何使用VSCode将iPad Pro转化为功能强大的开发工具?
文章目录 前言1. 本地环境配置2. 内网穿透2.1 安装cpolar内网穿透(支持一键自动安装脚本)2.2 创建HTTP隧道 3. 测试远程访问4. 配置固定二级子域名4.1 保留二级子域名4.2 配置二级子域名 5. 测试使用固定二级子域名远程访问6. iPad通过软件远程vscode6.1 创建TCP隧道 7. ipad远…...
将用友U8的数据可视化需要哪些工具?
将金蝶U8的数据可视化需要一个奥威BI数据可视化工具,以及一套专为用友U8打造的标准化BI数据分析方案。 奥威BI SaaS平台:一键链接用友U8,立得报表 别的BI软件围绕用友U8的数据做可视化:1、准备配置环境;2、下载安装配…...
DOS常用指令
一、dir显示目录 dir命令是Windows系统常用的命令,用于显示目录的文件和子目录的列表。如果不使用参数,此命令将显示磁盘的卷标和序列号,然后是磁盘上的目录和文件列表(包括它们的名称以及每个文件最后修改的日期和时间ÿ…...
【Pycharm中python调用另一个文件类或者函数】
Pycharm中python调用另一个文件类或者函数 本文主要介绍了Pycharm中python调用另一个文件类或者函数,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧 文章目录 Pycha…...
pycharm操作git、前后端项目上传到gitee
pycharm操作git 之前用命令做的所有操作,使用pychrm点点就可以完成 克隆代码 上方工具栏Git ⇢ \dashrightarrow ⇢ Clone ⇢ \dashrightarrow ⇢ 填写地址(http、ssh) 提交到暂存区,提交到版本库,推送到远程 直接…...
jmeter监听每秒点击数(Hits per Second)
jmeter监听每秒点击数(Hits per Second) 下载插件添加监听器执行压测,监听结果 下载插件 点击选项,点击Plugins Manager (has upgrades),点击Available Plugins,搜索5 Additional Graphs安装。 添加监听…...
RabbitMQ 消息模型
参考 【RabbitMQ】RabbitMQ架构模型_rabbitmq结构模型-CSDN博客 之前的学习都只是知道名字,但并没有真正的理解,每次看还是不懂,所以今日理解透 ! RabbitMQ 收发消息过程如下: 首先从消费者开始࿱…...
STM32cubemx对FreeRTOS的适配(工程模板配置)
文章目录 前言一、工程的创建二、什么是CMSIS三、STM32cubemx生成的FreeRTOS工程分析总结 前言 本篇文章将带大家使用STM32cubemx对FreeRTOS进行工程模板的配置。 一、工程的创建 1.开始工程的创建: 2.芯片型号选择: 3.修改时钟为TIM8: …...
SpringSecurity+ Oauth2.0+JWT 0-1
这里写目录标题 准备工作准备SQL添加用户添加依赖准备UserInfoUserMapperUserServiceUserServiceImpl配置SpringDataUserDetailsService 授权服务器:AuthorizationServer配置客户端详细信息管理令牌定义TokenConfig定义AuthorizationServerTokenServices 令牌访问端…...
Echart图表收起/展开后无法重新渲染实现自适应(亲测有效)-开发bug总结5
问题描述: 后台管理系统,左侧的菜单栏是可以展开/收起的,默认是展开,此时页面上的图表加载正常,如果收起后再展开,页面底部就会出现滚动轴,图表没有重新绘制。 网上也查了很多方法。基本都是通…...
互联网Java工程师面试题·Java 面试篇·第二弹
目录 15、什么是不可变对象(immutable object)?Java 中怎么创建一个不可变对象? 16、我们能创建一个包含可变对象的不可变对象吗? 17、Java 中应该使用什么数据类型来代表价格? 18、怎么将 byte 转换为 Str…...
【ARM裸机】ARM入门
1.ARM成长史 2.ARM的商业模式和生态系统 ARM只设计CPU,但是不生产CPU 3.为什么使用三星:S5PV210 4.各种版本号 0. ARM和Cortex Cortex就是ARM公司一个系列处理器的名称。比如英特尔旗下处理器有酷睿,奔腾,赛扬。ARM在最初的处理器…...
webGL编程指南 第三章 矩阵旋转三角形rotatedTriangle_Matrix
我会持续更新关于wegl的编程指南中的代码。 当前的代码不会使用书中的缩写,每一步都是会展开写。希望能给后来学习的一些帮助 git代码地址 :git 接着 上一节中 接着做平移的转化。在本次的案例案例中主要是xy的坐标变量相加,同时传递个给相…...
别再死记硬背!用华为/中兴网管实战拆解SDH复杂环网中的SNCP配置逻辑
华为/中兴SDH网管实战:复杂环网中SNCP配置的逻辑拆解与思维训练 在现网传输工程中,SDH环网拓扑的复杂性往往让工程师陷入配置命令的泥潭。当面对多个相交环、多节点业务调度时,盲目套用模板配置不仅效率低下,更可能在故障发生时导…...
Splatoon插件架构革新:FFXIV高难度副本智能导航与机制破解技术实现
Splatoon插件架构革新:FFXIV高难度副本智能导航与机制破解技术实现 【免费下载链接】Splatoon An accessibility tool to assist in gameplay and compensate for human imperfections. 项目地址: https://gitcode.com/gh_mirrors/spl/Splatoon Splatoon作为…...
如何快速实现Android底部导航栏:BottomNavigation完整指南
如何快速实现Android底部导航栏:BottomNavigation完整指南 【免费下载链接】BottomNavigation This Library helps users to use Bottom Navigation Bar (A new pattern from google) with ease and allows ton of customizations 项目地址: https://gitcode.com/…...
如何在Windows上直接安装安卓应用?APK安装器完整指南
如何在Windows上直接安装安卓应用?APK安装器完整指南 【免费下载链接】APK-Installer An Android Application Installer for Windows 项目地址: https://gitcode.com/GitHub_Trending/ap/APK-Installer 你知道吗?现在你可以在Windows电脑上直接运…...
如何使用rsync实现实时文件同步:inotify配置与自动备份完整指南
如何使用rsync实现实时文件同步:inotify配置与自动备份完整指南 【免费下载链接】rsync An open source utility that provides fast incremental file transfer. It also has useful features for backup and restore operations among many other use cases. 项…...
西门子S7-1500 PLC里那个LEAD_LAG指令,到底怎么用?手把手教你调超前滞后时间
S7-1500 PLC中LEAD_LAG指令的实战应用指南 1. 理解LEAD_LAG指令的核心价值 在工业自动化控制系统中,信号处理的质量直接影响着整个控制回路的性能。西门子S7-1500 PLC提供的LEAD_LAG(超前-滞后)指令,正是解决这一问题的利器。这个…...
保姆级教程:非华为笔记本也能用上华为多屏协同,手把手搞定电脑管家11和NFC卡贴
非华为笔记本实现多屏协同的完整实战指南 在移动办公时代,华为的多屏协同功能因其无缝连接手机与电脑的体验而备受追捧。但这项功能原本仅限于华为生态设备使用,让许多非华为笔记本用户望而兴叹。本文将彻底打破这一限制,通过系统化的解决方案…...
论文“焕新术”:书匠策AI,降重降AIGC的秘密武器大揭秘!
在学术的浩瀚宇宙中,每一篇论文都是研究者智慧的结晶,它们如同星辰般璀璨,照亮着知识的殿堂。然而,当这些星辰在查重的天空中闪烁时,重复率过高却成了不少研究者心中的“暗礁”。别怕,今天我要带你走进一个…...
Windows Cleaner完整教程:5分钟学会磁盘清理技巧,彻底解决C盘爆满问题
Windows Cleaner完整教程:5分钟学会磁盘清理技巧,彻底解决C盘爆满问题 【免费下载链接】WindowsCleaner Windows Cleaner——专治C盘爆红及各种不服! 项目地址: https://gitcode.com/gh_mirrors/wi/WindowsCleaner 还在为Windows系统C…...
LeetCode 1722. 执行交换操作后的最小汉明距离 详细技术解析
LeetCode 1722. 执行交换操作后的最小汉明距离 详细技术解析 一、题目核心考点剖析 本题的核心是理解「允许交换」的本质的,以及如何利用这种交换特性最小化汉明距离。关键考点如下: 交换的传递性:allowedSwaps 中给出的交换对具有传递性。例如,若允许交换 [0,1] 和 [1,2…...

