当前位置: 首页 > news >正文

C语言:约瑟夫环问题详解

前言
哈喽,宝子们!本期为大家带来一道C语言循环链表的经典算法题(约瑟夫环)。

目录

  • 1.什么是约瑟夫环
  • 2.解决方案思路
  • 3.创建链表头结点
  • 4.创建循环链表
  • 5.删除链表
  • 6.完整代码实现

1.什么是约瑟夫环

据说著名历史学家Josephus有过以下的故事:在罗马人占领乔塔帕特后,39个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被人抓到,于是决定了一个自杀方式,41个人拼成一个圆圈,由第一个人开始报数,每报数到第三人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。
然而Josephus和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。
这道题的原理也是一样的,来看看这道题长什么样吧。
描述:
编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数,报到 m 的人离开。下一个人继续从 1 开始报数。
n - 1 轮结束以后,只剩下一个人,问最后留下的这个人编号是多少?
示例1:
输入:5, 2
返回值:3
说明:
开始5个人 1,2,3,4,5 ,从1开始报数,1->1,2->2编号为2的人离开。
1,3,4,5,从3开始报数,3->1,4->2编号为4的人离开。
1,3,5,从5开始报数,5->1,1->2编号为1的人离开。
3,5,从3开始报数,3->1,5->2编号为5的人离开。
最后留下人的编号是3。

2.解决方案思路

既然是循环的报数,那我们就可以用我们所学过的单链表来解决这道题。

  1. 那假设我们有n个人,就要创建n个节点,首先创建一个节点,然后同时用两个指针指向这个节点,这个节点既是头指针head,也是尾指针ptail
  2. 然后把这个创建的过程用一个函数封装起来,调用函数来创建剩下的几个节点,每次调用完就让ptail的next指针指向我们新创建的节点,然后更新ptail指针的位置。
  3. 此时,我们的节点已经全部创建完成了,但是最重要的一步,就是要让我们的链表形成一个环,最后让尾指针的next指针指向我们的head
  4. 接着就是报数的实现需要有循环,报数要用一个计数器count来记录,当count等于m的时候,就要删除当前这个节点,然后更改头指针和尾指针的位置,最后直到头指针指向自己,此时指针里val的值就是最终留下来的值。
    在这里插入图片描述

3.创建链表头结点

//创建头链表
ListNode* ListBuyNode(int x)
{ListNode* newhead = (ListNode*)malloc(sizeof(ListNode));//动态申请内存失败if (newhead == NULL){exit(1);}//申请成功newhead->val = x;newhead->next = NULL;return newhead;
}

4.创建循环链表

//创建带环链表
ListNode* CreateCircle(int n)
{//先创建第一个节点ListNode* head = ListBuyNode(1);ListNode* ptail = head;for (int i = 2; i <= n; i++){//用尾插的方式把节点连接起来ptail->next = ListBuyNode(i);ptail = ptail->next;//更新尾节点位置}//收尾相连,链表成环ptail->next = head;return ptail;
}

5.删除链表

//当链表中只有一个节点的情况就是循环的终止条件
while (pcur->next != pcur)
{if (count == m){//销毁pcur节点prev->next = pcur->next;free(pcur);pcur = prev->next;count = 1;}else{//此时不需要销毁节点prev = pcur;pcur = pcur->next;count++;}
}

6.完整代码实现

//定义节点
struct ListNode
{int val;struct ListNode* next;
};
typedef struct ListNode ListNode;//类型重定义
//创建头链表
ListNode* ListBuyNode(int x)
{ListNode* newhead = (ListNode*)malloc(sizeof(ListNode));if (newhead == NULL){exit(1);}newhead->val = x;newhead->next = NULL;return newhead;
}
//创建带环链表
ListNode* CreateCircle(int n)
{//先创建第一个节点ListNode* head = ListBuyNode(1);ListNode* ptail = head;for (int i = 2; i <= n; i++){ptail->next = ListBuyNode(i);ptail = ptail->next;}//收尾相连,链表成环ptail->next = head;return ptail;
}
int ysf(int n, int m) 
{//1.根据n创建带环链表ListNode* prev = CreateCircle(n);//尾指针ListNode* pcur = prev->next;//头指针int count = 1;//当链表中只有一个节点的情况就是循环的终止条件while (pcur->next != pcur){if (count == m){//销毁pcur节点prev->next = pcur->next;free(pcur);pcur = prev->next;count = 1;}else{//此时不需要销毁节点prev = pcur;pcur = pcur->next;count++;}}//此时剩下的最后一个节点里的值就是要返回的值return prev->val;
}
int main()
{//测试用例int win=ysf(5, 2);printf("%d", win);return 0;
}

如果对你有所帮助的话,别忘了点赞+关注哟❤️!

相关文章:

C语言:约瑟夫环问题详解

前言 哈喽&#xff0c;宝子们&#xff01;本期为大家带来一道C语言循环链表的经典算法题&#xff08;约瑟夫环&#xff09;。 目录 1.什么是约瑟夫环2.解决方案思路3.创建链表头结点4.创建循环链表5.删除链表6.完整代码实现 1.什么是约瑟夫环 据说著名历史学家Josephus有过以下…...

【刷题篇】回溯算法(二)

文章目录 1、求根节点到叶节点数字之和2、二叉树剪枝3、验证二叉搜索树4、二叉搜索树中第K小的元素5、二叉树的所有路径 1、求根节点到叶节点数字之和 给你一个二叉树的根节点 root &#xff0c;树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表…...

Windows系统本地部署Jupyter Notebook并实现公网访问编辑笔记

文章目录 1.前言2.Jupyter Notebook的安装2.1 Jupyter Notebook下载安装2.2 Jupyter Notebook的配置2.3 Cpolar下载安装 3.Cpolar端口设置3.1 Cpolar云端设置3.2.Cpolar本地设置 4.公网访问测试5.结语 1.前言 在数据分析工作中&#xff0c;使用最多的无疑就是各种函数、图表、…...

自动化运维(二十七)Ansible 实战Shell 插件和模块工具

Ansible 支持多种类型的插件&#xff0c;这些插件可以帮助你扩展和定制 Ansible 的功能。每种插件类型都有其特定的用途和应用场景。今天我们一起学习Shell 插件和模块工具。 一、 Shell 插件 Ansible shell 插件决定了 Ansible 如何在远程系统上执行命令。这些插件非常关键&a…...

Jenkins使用-绑定域控与用户授权

一、Jenkins安装完成后&#xff0c;企业中使用&#xff0c;首先需要绑定域控以方便管理。 操作方法&#xff1a; 1、备份配置文件&#xff0c;防止域控绑定错误或授权策略选择不对&#xff0c;造成没办法登录&#xff0c;或登录后没有权限操作。 [roottest jenkins]# mkdir ba…...

【前端】es-drager 图片同比缩放 缩放比 只修改宽 只修改高

【前端】es-drager 图片同比缩放 缩放比 ES Drager 拖拽组件 (vangleer.github.io) 核心代码 //初始宽 let width ref(108)//初始高 let height ref(72)//以下两个变量 用来区分是单独的修改宽 还是高 或者是同比 //缩放开始时的宽 let oldWidth 0 //缩放开始时的高 let o…...

蓝桥杯第十四届蓝桥杯大赛软件赛省赛C/C++ 大学 A 组题解

1.幸运数 题目链接&#xff1a;0幸运数 - 蓝桥云课 (lanqiao.cn) #include<bits/stdc.h> using namespace std; bool deng(string& num){int n num.size();int qian 0,hou 0;for(int i0;i<n/2;i) qian (num[i]-0);for(int in/2;i<n;i) hou (num[i]-0);r…...

eclipse .project

.project <?xml version"1.0" encoding"UTF-8"?> <projectDescription> <name>scrm-web</name> <comment></comment> <projects> </projects> <buildSpec> <buil…...

react的闭包陷阱

React 的闭包陷阱是指在使用 React Hooks 时&#xff0c;由于闭包特性导致在某些函数或异步操作中无法正确访问到更新后状态或 prop 的值&#xff0c;而仍旧使用了旧值。下面通过几个代码示例来具体说明闭包陷阱的几种常见情形&#xff1a; 示例 1: useState 闭包陷阱 import…...

神经网络解决回归问题(更新ing)

神经网络应用于回归问题 优势是什么&#xff1f;&#xff1f;&#xff1f;生成数据集&#xff1a;通用神经网络拟合函数调整不同参数对比结果初始代码结果调整神经网络结构调整激活函数调整迭代次数增加早停法变量归一化处理正则化系数调整学习率调整 总结ingfnn.py进行计算&am…...

【小红书校招场景题】12306抢票系统

1 坐过高铁吧&#xff0c;有抢过票吗。你说说抢票系统对于后端开发人员而言会有哪些情况&#xff1f; 对于后端开发人员来说&#xff0c;开发和维护一个高铁抢票系统&#xff08;如中国的12306&#xff09;会面临一系列的挑战和情况。这些挑战主要涉及系统的性能、稳定性、数据…...

Spring(三)

1. Spring单例Bean是不是线程安全的? Spring单例Bean默认并不是线程安全的。由于多个线程可能访问同一份Bean实例&#xff0c;当Bean的内部包含了可变状态&#xff08;mutable state&#xff09;即有可修改的成员变量时&#xff0c;就可能出现线程安全问题。Spring容器不会自动…...

使用element-plus中的表单验证

标签页代码如下&#xff1a; // 注意&#xff1a;el-form中的数据绑定不可以用v-model&#xff0c;要使用:model <el-form ref"ruleFormRef" :rules"rules" :model"userTemp" label-width"80px"><el-row :gutter"20&qu…...

flinksql

Flink SQL 是 Apache Flink 项目中的一个重要组成部分,它允许开发者使用标准的 SQL 语言来处理流数据和批处理数据。Flink SQL 提供了一种声明式的编程范式,使得用户能够以一种简洁、高效且易于理解的方式来表达复杂的数据处理逻辑。 ### 背景 Flink SQL 的设计初衷是为了简…...

Dockerfile中 CMD和ENTRYPOINT的区别

在 Dockerfile 中&#xff0c;CMD 和 ENTRYPOINT 都用于指定容器启动时要执行的命令。它们之间的主要区别是&#xff1a; - CMD 用于定义容器启动时要执行的命令和参数&#xff0c;它设置的值可以被 Dockerfile 中的后续指令覆盖&#xff0c;包括在运行容器时传递的参数。如果…...

【TC3xx芯片】TC3xx芯片的总线内存保护

前言 广义上的内存保护,包括<<【TC3xx芯片】TC3xx芯片MPU介绍>>一文介绍的MPU(常规狭义上的内存保护),<<【TC3xx芯片】TC3xx芯片的Endinit功能详解>>一文中介绍的寄存器的EndInit保护,<<【TC3xx芯片】TC3xx芯片ACCEN寄存器保护详解>>一…...

抖音小店选品必经五个阶段,看你到哪一步了,直接决定店铺爆单率

大家好&#xff0c;我是电商笨笨熊 新手选品必经的阶段就是迷茫期&#xff0c;不知道怎么选品&#xff0c;在哪里选品&#xff0c;选择什么样的品&#xff1b; 而有些玩家也会在进入店铺后疯狂选品&#xff0c;但是上架的商品没有销量&#xff1b; 而这些都是每个玩家都要经…...

ML在骨科手术术前、书中、术后方法应用综述【含数据集】

达芬奇V手术机器人 近年来,人工智能(AI)彻底改变了人们的生活。人工智能早就在外科领域取得了突破性进展。然而,人工智能在骨科中的应用研究尚处于探索阶段。 本文综述了近年来深度学习和机器学习应用于骨科图像检测的最新成果,描述了其贡献、优势和不足。以及未来每项研究…...

vue3-video-play 在安卓上正常播放,在ios上不能播放,问题解决

1.ios上autoplay需要静音&#xff0c;在播放后再打开声音 <vue3videoPlay v-if"!isComponent" v-bind"options" :playsinline"playsinline"></vue3videoPlay>let playsinline computed(() > {if (props.isComponent) {return}o…...

【C++类和对象】上篇

&#x1f49e;&#x1f49e; 前言 hello hello~ &#xff0c;这里是大耳朵土土垚~&#x1f496;&#x1f496; &#xff0c;欢迎大家点赞&#x1f973;&#x1f973;关注&#x1f4a5;&#x1f4a5;收藏&#x1f339;&#x1f339;&#x1f339; &#x1f4a5;个人主页&#x…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)

一、OpenBCI_GUI 项目概述 &#xff08;一&#xff09;项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台&#xff0c;其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言&#xff0c;首次接触 OpenBCI 设备时&#xff0c;往…...