头脑风暴之约瑟夫环问题
一 问题的引入
约瑟夫问题的源头完全可以命名为“自杀游戏”。本着和谐友爱和追求本质的目的,可以把问题描述如下:
- 现有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的坐标变量相加,同时传递个给相…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
智能AI电话机器人系统的识别能力现状与发展水平
一、引言 随着人工智能技术的飞速发展,AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术,在客户服务、营销推广、信息查询等领域发挥着越来越重要…...
push [特殊字符] present
push 🆚 present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中,push 和 present 是两种不同的视图控制器切换方式,它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能
1. 开发环境准备 安装DevEco Studio 3.1: 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK 项目配置: // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...
实战三:开发网页端界面完成黑白视频转为彩色视频
一、需求描述 设计一个简单的视频上色应用,用户可以通过网页界面上传黑白视频,系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观,不需要了解技术细节。 效果图 二、实现思路 总体思路: 用户通过Gradio界面上…...
Visual Studio Code 扩展
Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后,命令 changeCase.commands 可预览转换效果 EmmyLua…...
前端调试HTTP状态码
1xx(信息类状态码) 这类状态码表示临时响应,需要客户端继续处理请求。 100 Continue 服务器已收到请求的初始部分,客户端应继续发送剩余部分。 2xx(成功类状态码) 表示请求已成功被服务器接收、理解并处…...

