企业网站明细费用,一键建站源码,php mysql开发的网站,使用三剑客做网站欢迎拜访#xff1a;羑悻的小杀马特.-CSDN博客 本篇主题#xff1a;带你众人皆知的约瑟夫环问题 制作日期#xff1a;2024.12.29 隶属专栏#xff1a;C/C题海汇总 目录
引言#xff1a;
一约瑟夫环问题介绍#xff1a;
11问题介绍#xff1a;
1.2起源与历史背景羑悻的小杀马特.-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 开始对于n1的情况。利用这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的值就好了。
公式 sumsumk)%i 这里前面的sum也就是我们对应的i个人最后剩下的编号后面的sum就是i-1了这里就实现了随着人数增多每次对上一次人数进行覆盖一直到n个人的时候。
注意这里我们要返回的是题目中的下标而我们给它错位对应了一下因此返回的是dp或者sum1.
当然了肯定sum的这种写起来比较简单因此对于我们只需要最后一个结果其他结果初始化后不需要的就可以采用这种覆盖来完成就可以用sum这样的变量完成覆盖。
2.3代码解答
2.3.1dp数组解答
#includebits/stdc.h
//为了方便n个人重新编号为0~n-1
using namespace std;
const int a1e65;int dp[a]{0};//表示i个人一组依次编号为k-1的淘汰最后剩下编号是多少
int main(){int n,k;cinnk;dp[1]0;for(int i2;in;i) dp[i](dp[i-1]k)%i;coutdp[n]1endl;//恢复原题编号映射关系return 0;
}
2.3.2sum解答
#includebits/stdc.h
using namespace std;
int main(){int n,k;cinnk;int sum 0;for (int i 2; i n; i) sum (sum k) % i;coutsum1endl;//恢复原题编号映射关系return 0;
}
最后也是通过了: 三·本篇小结 个人认为对于每道题可能有多个解法有时候我们往往想不到最优解法甚至有时候都无法解答故不要对于一道题死磕可以多参照下题解学习学习学习学习大佬们的思路把它理解总结比如这道既可以链表节点解决也可以动态规划也就是本篇所介绍因此我们肯定更喜欢简单的啦故学习才会让我们看到不一样的思路更加充实自己。
