MENU

约瑟夫环

2020 年 04 月 19 日 • 阅读: 8207 • 算法

据说著名犹太历史学家 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 大佬群

最后编辑于: 2020 年 04 月 21 日
返回文章列表 文章二维码
本页链接的二维码
打赏二维码
添加新评论

Loading captcha...

已有 2 条评论
  1. 初夏阳光 初夏阳光   Windows 10 x64 Edition  Google Chrome 81.0.4044.113

    什么?什么电影?约瑟夫环?科幻的吗?

    进来:哦,原来是算法啊! Logi 更算法了!

    (你这个全屏遮罩过分了 ::quyin:angry::

    1. LOGI LOGI   Windows 10 x64 Edition  Google Chrome 81.0.4044.113

      @初夏阳光遮罩是这站的唯一亮点@(捂嘴笑)