【动态规划篇】穿越算法迷雾：约瑟夫环问题的奇幻密码

 

欢迎拜访：羑悻的小杀马特.-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;
}

最后也是通过了: 

三·本篇小结：

 个人认为，对于每道题可能有多个解法；有时候我们往往想不到最优解法；甚至有时候都无法解答；故不要对于一道题死磕；可以多参照下题解学习学习；学习学习大佬们的思路；把它理解总结；比如这道既可以链表节点解决也可以动态规划（也就是本篇所介绍）；因此我们肯定更喜欢简单的啦，故学习才会让我们看到不一样的思路；更加充实自己。