题解 | 约瑟夫环

采用递归的思路解，设 Joseph( n , m ) 为解

假设有 n = 5 个人，编号 a[i]={ 0，1，2，3，4 } ，从1开始数到 m = 2 的时候出队，第一个出去的数为 ( m - 1 ) % n = 1 ，

那么剩下 n - 1 个数，如下如蓝色标，将 a[ 2 ] 当作新的数组的开始，则下一个出去的数字为 Joseph( n -1, m )

之前出去的数字为 a[ m ] ，则加上第一轮数字 m = 2 ，第二轮出去的数字为 Joseph( n-1, m ) + m = 3 ，

第三个数超出数组范围，需要取模为 (Joseph( n -1, m ) + m) % n ，故递推关系为 Joseph( n , m ) = (Joseph( n -1, m ) + m) % n

最后如果 Joseph( 1 , m ) ，那结果为 0 。

又因为从编号 k 的人开始报数，那么结果需要再加上 k ，然后取模人数 n

#include <stdio.h>

int Joseph(int n, int m) {
    if (n == 1)
        return 0;

    return (Joseph(n - 1, m) + m ) % n;
}

int main() {
    int n, k, m;
    scanf("%d %d %d", &n, &k, &m);

    int ret = (Joseph(n, m) + k) % n;
    printf("%d", ret);

    return 0;
}