约瑟夫环

据说著名犹太历史学家 Josephus 有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与 Josephus 及他的朋友躲到一个洞中，39 个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41 个人排成一个圆圈，由第 1 个人开始报数，每报数到第 3 人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。Josephus 要他的朋友先假装遵从，他将朋友与自己安排在第 16 个与第 31 个位置，于是逃过了这场死亡游戏。

问题

n 个人围成一圈，第一个人从 0 开始报数，报 m-1 的将被杀掉，下一个人接着从 0 开始报。如此反复，最后剩下一个，求最后的胜利者。

分析

第 1 轮出局者在本轮的位置为 (m-1)%n，重编号后有
第 2 轮第 0 个位置对应第 1 轮的位置为 m%n
第 2 轮第 1 个位置对应第 1 轮的位置为 (m+1)%n
...
第 2 轮第 n-2 个位置对应第 1 轮的位置为 (m+n-2)%n，故
第 2 轮第 k 个位置对应第 1 轮的位置为 (m+k)%n （结论 1），记
f(n,m) 为 n 个人，数到 m-1 的人被杀死，最后一个人的编号，那么 f(n-1,m) 表示 n-1 个人，数到 m-1 的人被杀死，最后一个人的编号。上述重编号规则仅仅是将游戏进行下去，所以这两个人其实是同一个人，再根据结论 1，有 f(n,m) = [m+f(n-1,m)]%n（推论 1）。类似地
第 2 轮出局者在本轮的位置为 (m-1)%(n-1)，重编号后有
第 3 轮第 0 个位置对应第 2 轮的位置为 m%(n-1)
第 3 轮第 1 个位置对应第 2 轮的位置为 (m+1)%(n-1)
...
第 3 轮第 n-3 个位置对应第 2 轮的位置为 (m+n-3)%(n-1)，故
第 3 轮第 k 个位置对应第 2 轮的位置为 (m+k)%(n-1) （结论 2），记
f(n-1,m) 为 n-1 个人，数到 m-1 的人被杀死，最后一个人的编号，那么 f(n-2,m) 就是 n-2 个人，数到 m-1 的人被杀死，最后一个人的编号。上述重编号规则仅仅是将游戏进行下去，这两个人其实是同一个人，再根据结论 2，有 f(n-1,m) = [m+f(n-2,m)]%(n-1)（推论 2），同理，
f(n-2,m) = [m+f(n-3,m)]%(n-2)
f(n-3,m) = [m+f(n-4,m)]%(n-3)
...
f(3,m) = [m+f(2,m)]%3
f(2,m) = [m+f(1,m)]%2
f(1,m) = 0

迭代

#include <stdio.h>

int f(int n, int m)
{
    int s = 0, i = 2;
    for (; i <= n; i++)
    {
        s = (m + s) % i;
    }
    return s;
}

int main(void)
{
    printf("%d", f(7, 3));
    return 0;
}

递归

#include <stdio.h>

int f(int n, int m)
{
    if(n == 1) return 0;
    return (m + f(n-1, m)) % n;
}

int main(void)
{
    printf("%d", f(7, 3));
    return 0;
}

如有问题请在下方留言，文章转载请注明出处，详细交流请加下方群组！请大佬不要屏蔽文中广告，因为它将帮我分担服务器开支，如果能帮忙点击我将万分感谢。

TG 大佬群 QQ 大佬群