Josephus问题 博客分类： 算法

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

php 实现代码

$person_num = 41;
$person_count = 3;

$persons = array();
for($i=1;$i<=$person_num;$i++)
{
    $next = $i;
    if($i==$person_num)
    {
        $next = 0;
    }
    $persons[] = array($i, $next);
}

$next = 0;
$i = 0;
$next_next = 0;
while(count($persons)>1)
{
    $i++;
    if($i==($person_count-1))
    {
        echo "out:" . $persons[$persons[$next][1]][0] . "\n";
        $next_next = $persons[$next][1];
        $persons[$next][1] = $persons[$persons[$next][1]][1];
        unset($persons[$next_next]);
        $i = 0;
    }

    $next = $persons[$next][1];
}

echo "left:" . $persons[$next][0] . "\n";

output：

out:3
out:6
out:9
out:12
out:15
out:18
out:21
out:24
out:27
out:30
out:33
out:36
out:39
out:1
out:5
out:10
out:14
out:19
out:23
out:28
out:32
out:37
out:41
out:7
out:13
out:20
out:26
out:34
out:40
out:8
out:17
out:29
out:38
out:11
out:25
out:2
out:22
out:4
out:35
out:16
left:31