#include<stdio.h>

int josephus(int n,int k,int m){//n个人，编号为k
    int result=0;//初始时，只有一个人结果是0
    for(int i=2;i<=n;i++){
        result=(result+m)%i;
    }
    return (result+k)%n;
}
int main(){
    int n,k,m;
    scanf("%d %d %d",&n,&k,&m);
    int king=josephus(n,k,m);
    printf("%d",king);
}

解决思路：

这个问题可以通过递归来求解，假设有 n 个人，从编号为 k 的人开始报数，每次报数到第 m 个人出队，最终剩下的人的编号可以通过递归关系得到：

  • 如果只有一个人，那么显然这个人就是“大王”，编号是 0（从 0 开始编号）。

  • 如果有 n 个人，编号为 x0,x1,...,xn−1，且从编号为 k 的人开始报数，每次报数到第 m 个人出队。此时的递归公式是：

    J(n,m)=(J(n−1,m)+m)%n

    其中 J(n,m) 表示有 n 个人时，最终剩下的人在原始序列中的编号。J(n−1,m) 是在 n−1个人时求得的解，然后通过加上 m 来确定新出队的人，最后使用模 n 来保持在 n 个人范围内。

递归到循环：

为了避免递归调用的开销，我们可以将这个问题转化为迭代（循环）求解。

具体算法步骤：

  1. 假设初始时 n=1，此时唯一剩下的人的编号是 0（即第一个人）。
  2. 对于每一个 n 从 2 到给定的 n，用公式逐步计算出最后剩下的人的编号。
  3. 最终的编号是从 0 开始的，如果题目要求从 1 开始编号，只需在结果上加 1。