题目描述题目链接1504 - 约瑟夫问题-东方博宜OJ约瑟夫问题Josephus problem是一个经典的数学问题有n个人围成一圈从第1个人开始报数数到第m个人出列然后从下一个人重新开始报数数到第m个人再出列如此循环直到所有人都出列为止。求最后一个出列的人的编号。输入格式输入包含两个整数n和m表示总人数和报数的间隔。数据范围1 ≤ n, m ≤ 1000输出格式输出一个整数表示最后一个出列的人的编号。样例输入5 3样例输出4算法分析1. 模拟法暴力解法最直观的方法是使用数组或链表模拟整个过程创建一个长度为 n 的数组初始值表示每个人是否还在圈中例如用 1 表示在圈中0 表示已出列。从第一个人开始报数每次数到 m 时将当前位置的人标记为出列。继续从下一个人开始报数直到只剩下一个人。时间复杂度O(n×m)当 n 和 m 较大时效率较低。2. 数学递推法约瑟夫环公式约瑟夫环问题有一个经典的数学递推公式设 f(n, m) 表示 n 个人报数到 m 时最后剩下的人的编号编号从 0 开始。递推公式f(1, m) 0 f(n, m) (f(n-1, m) m) % n (n 1)如果编号从 1 开始则最后结果为 f(n, m) 1。时间复杂度O(n)空间复杂度O(1)。代码实现C 实现数学递推法#include iostream using namespace std; int main() { int n, m; cin n m; int result 0; // f(1, m) 0 for (int i 2; i n; i) { result (result m) % i; } // 编号从1开始所以加1 cout result 1 endl; return 0; }Python 实现n, m map(int, input().split()) result 0 for i in range(2, n 1): result (result m) % i print(result 1)C函数版本#include iostream using namespace std; int josephus(int n,int m){ bool vis[100]{false}; int pos0,cnt0,num0; while(cntn-1){ pos; if(posn) pos1; if(!vis[pos]) num; if(numm){ vis[pos]true; cnt; num0; } } for(int i1;in;i){ if(!vis[i]) return i; } } int main(){ int n,m; cinnm; int resjosephus(n,m); cout幸存者res; return 0; }Java 实现import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); int result 0; for (int i 2; i n; i) { result (result m) % i; } System.out.println(result 1); } }算法推导过程为了更好地理解递推公式我们来推导一下当 n1 时只有一个人最后剩下的人编号为 0如果从 0 开始编号。当 n1 时第一轮报数后第 m%n 个人出列如果 m%n0则是第 n 个人出列。剩下 n-1 个人重新编号原来第 m%n1 个人变成新编号的 0 号以此类推。问题转化为 n-1 个人的约瑟夫问题新编号下的解为 f(n-1, m)。将新编号转换回原编号原编号 (新编号 m) % n。因此得到递推公式f(n, m) (f(n-1, m) m) % n。样例解析以样例输入 n5, m3 为例初始1 2 3 4 5第1轮报数到33出列 → 剩余1 2 4 5第2轮从4开始报数4→5→11出列 → 剩余2 4 5第3轮从2开始报数2→4→55出列 → 剩余2 4第4轮从2开始报数2→4→22出列 → 剩余4最后剩下的是4号使用递推公式计算f(1,3)0 f(2,3)(03)%21 f(3,3)(13)%31 f(4,3)(13)%40 f(5,3)(03)%53 最后结果314复杂度分析时间复杂度O(n)只需要一次循环。空间复杂度O(1)只使用了常数个变量。注意事项注意编号从1开始还是从0开始题目通常要求从1开始编号。当 m1 时就是顺序出列最后剩下的是第 n 个人。当 n 和 m 很大时递推法仍然高效而模拟法可能会超时。如果题目要求输出出列顺序则需要使用模拟法或链表实现。扩展思考约瑟夫环问题还有一些变体输出出列顺序而不仅仅是最后一个人。当 m 不是常数而是随着轮数变化时。当 n 非常大如 10^9时需要使用更高效的数学方法。总结约瑟夫环问题是一个经典的算法问题掌握其数学递推公式可以高效解决。对于 OJ 题目 1504推荐使用递推法时间复杂度 O(n)可以轻松通过所有测试用例。