头脑风暴之约瑟夫环问题
一 问题的引入
约瑟夫问题的源头完全可以命名为“自杀游戏”。本着和谐友爱和追求本质的目的,可以把问题描述如下:
- 现有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的坐标变量相加,同时传递个给相…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
Java入门学习详细版(一)
大家好,Java 学习是一个系统学习的过程,核心原则就是“理论 实践 坚持”,并且需循序渐进,不可过于着急,本篇文章推出的这份详细入门学习资料将带大家从零基础开始,逐步掌握 Java 的核心概念和编程技能。 …...
selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
C++.OpenGL (20/64)混合(Blending)
混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...
Monorepo架构: Nx Cloud 扩展能力与缓存加速
借助 Nx Cloud 实现项目协同与加速构建 1 ) 缓存工作原理分析 在了解了本地缓存和远程缓存之后,我们来探究缓存是如何工作的。以计算文件的哈希串为例,若后续运行任务时文件哈希串未变,系统会直接使用对应的输出和制品文件。 2 …...
JDK 17 序列化是怎么回事
如何序列化?其实很简单,就是根据每个类型,用工厂类调用。逐个完成。 没什么漂亮的代码,只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...
用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章
用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章 摘要: 操作系统内核的安全性、稳定性至关重要。传统 Linux 内核模块开发长期依赖于 C 语言,受限于 C 语言本身的内存安全和并发安全问题,开发复杂模块极易引入难以…...
stm32进入Infinite_Loop原因(因为有系统中断函数未自定义实现)
这是系统中断服务程序的默认处理汇编函数,如果我们没有定义实现某个中断函数,那么当stm32产生了该中断时,就会默认跑这里来了,所以我们打开了什么中断,一定要记得实现对应的系统中断函数,否则会进来一直循环…...

