01.约瑟夫环

约瑟夫环问题（Josephus Problem）

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

利用数组解决该问题

int total = 41; //总人数
int alive = 41; //幸存人数
int index = 0;  //轮转下标
int count = 1;  //计数
int[] a = new int[total];// 0-幸存  1-死亡
//循环直至剩余两个人
while(alive > 2) {
    //如果报数到3，且这个人还幸存
    if(count % 3 == 0 && a[index] == 0) {
        a[index] = 1;  //干掉这个人
        alive--;   //幸存人数-1
        count = 0;  //计数器归0
    }       
    if(index == 40) {  //如果到达队尾
        index = 0;  //重新回到队首
    }else {
        index++;   //否则继续下一个人
    }
    if(a[index] == 0) {
        count++;  //如果下一个人幸存,报数+1
    }
}
//遍历剩余幸存者的下标，+1即是站位
for(int i = 0; i < total; i++) {
    if(a[i] == 0) {
        System.out.println(i+1);
    }
}   

我想这货不是历史学家，应该是个计算机。

这道题目的变形：
(1)加斯帕的教徒问题
15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。
(2)猴子选王问题
一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。

基本类似于在m个人组成的圆圈中每隔n个人进行排除的类似描述基本都可以理解为是约瑟夫环的变形。