【动态规划篇】穿越算法迷雾:约瑟夫环问题的奇幻密码
欢迎拜访:羑悻的小杀马特.-CSDN博客
本篇主题:带你众人皆知的约瑟夫环问题
制作日期:2024.12.29
隶属专栏:C/C++题海汇总
目录
引言:
一·约瑟夫环问题介绍:
1·1问题介绍:
1.2起源与历史背景:
1.3问题求解思路:
1.3.1模拟法:
1.3.2数学递推法:
1.4实际应用领域:
1.4.1计算机科学与编程竞赛:
1.4.2操作系统进程调度:
1.4.3密码学与加密算法:
二·约瑟夫问题实际解法:
2.1约瑟夫环:
2.2解法叙述:
2.3代码解答:
2.3.1dp数组解答:
2.3.2sum解答:
三·本篇小结:
引言:
当古老的传说与现代的智慧交织,一场数字的盛宴拉开帷幕。约瑟夫环问题宛如一座神秘的迷宫,静静矗立在算法的王国。它见证了无数思维的碰撞与火花的绽放,如今,我们将手持逻辑的利斧,斩断层层迷雾,深入其内核,探寻隐藏在数字循环背后的终极真相,开启一场扣人心弦的解谜冒险,让智慧之光穿透谜题的黑暗,照亮那最终的答案。
一·约瑟夫环问题介绍:
1·1问题介绍:
约瑟夫环(Josephus Problem)是一个经典的数学和计算机科学问题。其描述为:有个n人围成一圈,从某一特定位置的人开始按顺时针方向依次报数,每次报到特定数字m的人被淘汰出局,然后下一个人接着从 1 开始报数,如此循环进行,直到圈中只剩下最后一个人,目标是确定这个最后幸存者在原始n个人中的初始位置。
1.2起源与历史背景:
这个问题的起源可以追溯到古代罗马时期。相传犹太历史学家约瑟夫(Josephus)和他的一群士兵被罗马军队包围在山洞中,他们决定宁愿自杀也不愿被俘虏。他们围成一个圈,并商定了一个自杀规则,即每三个人一组,依次报数,报到 3 的人自杀,约瑟夫和他的一个朋友不想自杀,于是通过快速计算,找到了在这个规则下他们应该站在圈中的什么位置,从而避免了自杀,这便是约瑟夫环问题的雏形,此后这个问题逐渐在数学和算法领域流传开来,成为一个经典的问题模型,被广泛研究和讨论,用于各种理论和实际应用场景的算法设计与分析。
1.3问题求解思路:
1.3.1模拟法:
按照问题描述的规则,使用数组或链表来模拟整个报数和淘汰的过程。从第一个人开始报数,每报到m就将对应的元素标记为已淘汰,直到只剩下一个未被标记的元素,这个元素的位置就是最终的解。这种方法直观易懂,但对于较大的n和m值,时间复杂度较高,效率较低,因为每次报数都需要遍历数组或链表中的大部分元素。
1.3.2数学递推法:
通过分析问题的规律,可以发现存在数学递推关系。设表示n个人报数到m时最后幸存者的位置。当只有一个人时,
(这里位置编号从 0 开始);对于n>1的情况,。利用这f(n,m)=(f(n-1,m)+m)%m个递推公式,可以从f(1,m)开始逐步计算出f(n,m),时间复杂度为O(N),相比模拟法大大提高了效率,这种方法利用了数学规律,避免了繁琐的模拟过程,在解决大规模约瑟夫环问题时表现出明显的优势。
1.4实际应用领域:
1.4.1计算机科学与编程竞赛:
在数据结构与算法的教学和学习中,约瑟夫环问题是一个很好的案例,用于讲解循环链表、数组操作、递归和动态规划等知识。通过实际编写代码解决约瑟夫环问题,可以加深对这些数据结构和算法的理解和掌握。在编程竞赛中,也经常会出现约瑟夫环问题的变形题目,考察选手的算法设计和编程能力,例如在 ACM 国际大学生程序设计竞赛等赛事中,类似的题目要求选手能够快速分析问题,选择合适的算法求解,并优化代码以满足时间和空间的限制。
1.4.2操作系统进程调度:
操作系统中的进程调度算法可以借鉴约瑟夫环的思想。例如,在某些简单的轮转调度算法中,进程被看作是围成一圈的 “人”,时间片的轮转相当于报数过程,当一个进程的时间片用完(相当于报到特定的数),该进程可能会被暂停或切换到其他状态,等待下一次调度机会,就如同约瑟夫环中被淘汰的人暂时离开圈子一样。这种类比有助于理解进程调度的基本原理和机制,以及如何优化进程的执行顺序和资源分配,以提高系统的整体性能和效率。
1.4.3密码学与加密算法:
在一些密码学的加密和解密算法设计中,约瑟夫环的原理可以被用来对数据进行变换和处理。例如,将数据元素按照一定的顺序排列成环形结构,通过类似于约瑟夫环的操作方式,对数据进行特定的置换和选择,增加数据的安全性和保密性。这种应用方式使得约瑟夫环问题不仅仅局限于简单的数字游戏或算法示例,而是在信息安全领域发挥了实际作用,为加密算法的设计提供了新的思路和方法。
二·约瑟夫问题实际解法:
2.1约瑟夫环:
下面我们以一道题来引入正题,使用动态规划解法来解答吧:

输入:10 3 输出:4
洛谷原题链接:[蓝桥杯 2018 国 AC] 约瑟夫环 - 洛谷
2.2解法叙述:
首先我们这道题其实可以用链表(循环遍历等方法去解决,但是这里我们选择一种最简单的思想:即动态规划思想去解决)
思路:约瑟夫环问题,即n个下标,从0开始数,每当到下标为k-1为止就删除,从它下一个为0开始循环,求最后剩下的第一个,
这里可以利用递推的方法也就是前缀和动态规划思想:把从这n个下标删除指定个后就是n-1个再删除k-1下标处,因此把n个和n-1个每k个删除一个它们对应的下标写出,可以发先相差k但是当是下标0的时候n-1个的时候就成了-k,因此要根据它上一个的下标进行调整也就是n-k;因此可以得到一个公式使得上面成立dp[n]=(dp[n-1]+k)%n:这里dp[n]表示n个,每k个删除一个最后剩下的下标是多少。
首先我们请看图:

这里我们就推导出了个公式:
dp[i]=(dp[i-1]+k)%i
这的i表示我们多少个人;因此这就联想到了动态规划了;下面不就是我们熟悉的填表初始化了;
其次就是这里要从2开始遍历;比如一个人他肯定返回编号0;这里我们直接把dp数组都初始化为0,就好。
当然了这里其实可以不用把从2个人到n个人的最后返回编号的情况都列举出来,也就是我们不需要填充dp只要最后一次即可;这里我们就可以用一个变量sum记录;每次填充随着人数的增多来更新sum的值就好了。
公式:
sum=(sum+k)%i
这里前面的sum也就是我们对应的i个人最后剩下的编号;后面的sum就是i-1了;这里就实现了随着人数增多每次对上一次人数进行覆盖一直到n个人的时候。
注意:这里我们要返回的是题目中的下标而我们给它错位对应了一下;因此返回的是dp或者sum+1.
当然了肯定sum的这种写起来比较简单:因此对于我们只需要最后一个结果;其他结果初始化后不需要的;就可以采用这种覆盖来完成,就可以用sum这样的变量完成覆盖。
2.3代码解答:
2.3.1dp数组解答:
#include<bits/stdc++.h>
//为了方便n个人重新编号为0~n-1
using namespace std;
const int a=1e6+5;int dp[a]={0};//表示i个人一组;依次编号为k-1的淘汰;最后剩下编号是多少
int main(){int n,k;cin>>n>>k;dp[1]=0;for(int i=2;i<=n;i++) dp[i]=(dp[i-1]+k)%i;cout<<dp[n]+1<<endl;//恢复原题编号映射关系return 0;
}
2.3.2sum解答:
#include<bits/stdc++.h>
using namespace std;
int main(){int n,k;cin>>n>>k;int sum = 0;for (int i = 2; i <= n; i++) sum = (sum + k) % i;cout<<sum+1<<endl;//恢复原题编号映射关系return 0;
}
最后也是通过了:

三·本篇小结:
个人认为,对于每道题可能有多个解法;有时候我们往往想不到最优解法;甚至有时候都无法解答;故不要对于一道题死磕;可以多参照下题解学习学习;学习学习大佬们的思路;把它理解总结;比如这道既可以链表节点解决也可以动态规划(也就是本篇所介绍);因此我们肯定更喜欢简单的啦,故学习才会让我们看到不一样的思路;更加充实自己。
相关文章:
【动态规划篇】穿越算法迷雾:约瑟夫环问题的奇幻密码
欢迎拜访:羑悻的小杀马特.-CSDN博客 本篇主题:带你众人皆知的约瑟夫环问题 制作日期:2024.12.29 隶属专栏:C/C题海汇总 目录 引言: 一约瑟夫环问题介绍: 11问题介绍: 1.2起源与历史背景&…...
代码随想录算法训练营第51期第32天 | 理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯
理论基础 动态规划:dp,每一个状态都是由上个状态推导出来的,因为我是先写完三道题再看理论的,所以有点感概; 确定dp数组(dp table)以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举…...
爱思唯尔word模板
爱思唯尔word模板 有时候并不一定非得latex https://download.csdn.net/download/qq_38998213/90199214 参考文献书签链接...
每日一题 354. 俄罗斯套娃信封问题
354. 俄罗斯套娃信封问题 需要对信封排序 ,重点是再宽度相同时,逐步减少其高度 class Solution { public:int maxEnvelopes(vector<vector<int>>& envelopes) {sort(envelopes.begin(),envelopes.end(),[](const vector<int>&a,const v…...
ASP.net网站的注册、登录和密码修改的操作详解
一、进入注册、登录和密码修改操作详解 ASP.net网站为用户提供不同权限状态下的操作界面。根据用户登录状态,页面会显示不同的选项。 已登录用户的操作 图1 登录后操作界面 当用户已登录系统时,会显示以下内容和功能: 1. 欢迎信息 页面顶部…...
2024.12.29(进程线程实现并发服务器)
作业 多进程多线程并发服务器实现一遍提交。 服务器 #include <myhead.h> #define PORT 12345 #define IP "192.168.124.123"void *fun(void *fd) {int newfd *(int *)fd;char buff[1024];while(1){int res recv(newfd,buff,sizeof(buff),0);if(res 0){p…...
如何在 Ubuntu 上安装 PyTorch
简介 PyTorch 因其易用性、动态计算图和高效性而日益流行,成为实现深度学习模型的首选。如果你想探索这个工具并学习如何在 Ubuntu 上安装 PyTorch,本指南将对你有所帮助! 在本教程中,我们将引导你完成在 Ubuntu 系统上使用 Pip…...
8-Gin 中间件 --[Gin 框架入门精讲与实战案例] 【文末有测试代码】
路由中间件 Gin 是一个用 Go (Golang) 编写的 HTTP web 框架。它以性能好、中间件支持灵活著称,非常适合用来构建微服务或 RESTful API 服务。下面我将提供三个使用 Gin 的路由中间件的完整示例。 示例 1: 简单的日志记录中间件 这个中间件会在每个请求处理前后打…...
【潜意识Java】深入详细理解分析Java中的toString()方法重写完整笔记总结,超级详细。
目录 一、toString() 方法是啥? (一)默认的 toString() 方法 (二)toString() 方法的作用 二、为啥要重写 toString() 方法? (一)提高代码的可读性 (二)…...
【论文笔记】Contrastive Learning for Sign Language Recognition and Translation
🍎个人主页:小嗷犬的个人主页 🍊个人网站:小嗷犬的技术小站 🥭个人信条:为天地立心,为生民立命,为往圣继绝学,为万世开太平。 基本信息 标题: Contrastive Learning for…...
Gitlab17.7+Jenkins2.4.91实现Fastapi/Django项目持续发布版本详细操作(亲测可用)
一、gitlab设置: 1、进入gitlab选择主页在左侧菜单的下面点击管理员按钮。 2、选择左侧菜单的设置,选择网络,在右侧选择出站请求后选择允许来自webhooks和集成对本地网络的请求 3、webhook设置 进入你自己的项目选择左侧菜单的设置ÿ…...
一起来看--红黑树
【欢迎关注编码小哥,学习更多实用的编程方法和技巧】 红黑树是一种自平衡的二叉搜索树,广泛应用于计算机科学中,尤其是在实现关联数组和集合时。它的设计旨在确保在最坏情况下,基本动态集合操作(如插入、删除和查找&am…...
SpringBoot整合篇 05、Springboot整合Redission
文章目录 前言Redission详细配置步骤pom依赖application.yaml配置类CacheConfigEnvironmentContext RedissionController单测 前言 本篇博客是SpringBoot整合Redission,若文章中出现相关问题,请指出! 所有博客文件目录索引:博客…...
供应链系统设计-供应链中台系统设计(六)- 商品中心概念篇
概述 我们在供应链系统设计-中台系统设计系列(五)- 供应链中台实践概述 中描述了什么是供应链中台,供应链中台主要包含了那些组成部门。包括业务中台、通用中台等概念。为了后续方便大家对于中台有更深入的理解,我会逐一针对中台…...
胡闹厨房练习(三)
ScriptableObject 一、初步了解 1、实质:是一种特殊类型的Unity对象, 2、作用:用于存储大量数据,而不必依附于游戏场景中的某个GameObject。 3、特点: 可以在不增加场景中对象数量的情况下,管理和存储复杂的数据结构、配置信息、游戏状态等。 4、适用:非常适合用来…...
关于ESD(静电放电)等级的划分
关于ESD(静电放电)等级的划分,主要依据不同的测试模型和测试标准。以下是对HBM(人体模型)和CDM(充电器件模型)两种测试模型下ESD等级划分的详细解释: HBM ESD等级划分 HBM ESD等级…...
探究步进电机与输入脉冲的关系
深入了解步进电机 前言一、 步进电机原理二、 细分三、脉冲数总结 前言 主要是探究以下内容: 1、步进电机的步进角。 2、什么是细分。 3、脉冲的计算。 最后再扩展以下STM32定时器的计算方法。 一、 步进电机原理 其实语言描述怎么样都不直观,我更建议…...
基于YOLOV5+Flask安全帽RTSP视频流实时目标检测
1、背景 在现代工业和建筑行业中,安全始终是首要考虑的因素之一。特别是在施工现场,工人佩戴安全帽是确保人身安全的基本要求。然而,人工监督难免会有疏漏,尤其是在大型工地或复杂环境中,确保每个人都佩戴安全帽变得非…...
Windows内置的服务器IIS(Internet Information Services)托管网站
一. 安装IIS 打开控制面板:在开始菜单搜索“控制面板”并打开它。程序和功能:点击“程序”然后选择“程序和功能”。启用或关闭Windows功能:在左侧菜单中选择“启用或关闭Windows功能”。查找并勾选IIS:在弹出的窗口中,…...
虚幻引擎结构之UObject
一. UObject 的介绍 UObject 是虚幻引擎中的核心基础类,所有其他游戏对象和资源类都直接或间接地继承自它。作为虚幻引擎的基石,UObject 提供了多项关键功能,包括内存管理、序列化、反射(introspection)、垃圾回收以及元数据支持。在虚幻引擎中,UObject 类的实例通常被称…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
实战三:开发网页端界面完成黑白视频转为彩色视频
一、需求描述 设计一个简单的视频上色应用,用户可以通过网页界面上传黑白视频,系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观,不需要了解技术细节。 效果图 二、实现思路 总体思路: 用户通过Gradio界面上…...
论文阅读:LLM4Drive: A Survey of Large Language Models for Autonomous Driving
地址:LLM4Drive: A Survey of Large Language Models for Autonomous Driving 摘要翻译 自动驾驶技术作为推动交通和城市出行变革的催化剂,正从基于规则的系统向数据驱动策略转变。传统的模块化系统受限于级联模块间的累积误差和缺乏灵活性的预设规则。…...
0x-3-Oracle 23 ai-sqlcl 25.1 集成安装-配置和优化
是不是受够了安装了oracle database之后sqlplus的简陋,无法删除无法上下翻页的苦恼。 可以安装readline和rlwrap插件的话,配置.bahs_profile后也能解决上下翻页这些,但是很多生产环境无法安装rpm包。 oracle提供了sqlcl免费许可,…...
【Linux】Linux安装并配置RabbitMQ
目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的,需要先安…...
加密通信 + 行为分析:运营商行业安全防御体系重构
在数字经济蓬勃发展的时代,运营商作为信息通信网络的核心枢纽,承载着海量用户数据与关键业务传输,其安全防御体系的可靠性直接关乎国家安全、社会稳定与企业发展。随着网络攻击手段的不断升级,传统安全防护体系逐渐暴露出局限性&a…...
spring boot使用HttpServletResponse实现sse后端流式输出消息
1.以前只是看过SSE的相关文章,没有具体实践,这次接入AI大模型使用到了流式输出,涉及到给前端流式返回,所以记录一下。 2.resp要设置为text/event-stream resp.setContentType("text/event-stream"); resp.setCharacter…...
