约瑟夫杀人游戏

r囧r小猫 2022-06-05 08:56 203阅读 0赞

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

public class jsoeplus {
        public static int N = 20;
        public static int M = 5;//数到M就咔擦一个人
    
    
        class Node{
            int val;//下标
            Node next;
            public Node(int val){
                this.val = val;
            }
        }
    
        public void killNode(){
            Node header = new Node(1);//第一个结点
            Node x = header;//目前被点到人
            for(int i = 2;i<=N;i++){
                x=(x.next = new Node(i));
            }
            x.next = header;//头尾相接
            System.out.println("被咔擦的顺序为：");
            while(x!=x.next){
                //至少还有俩人，仍然继续报数，咔嚓
                for(int i = 1;i<M;i++){
                    x = x.next;
                }
                System.out.println(x.next.val+"被干掉 ");
                x.next = x.next.next;
            }
            System.out.println("最后这个幸运儿是："+x.val);
        }
    
        public static void main(String[] args){
            jsoeplus jsoeplus = new jsoeplus();
            josephus.killNode();
        }
    }

结果：

> 被咔擦的顺序为：  
> 5被干掉  
> 10被干掉  
> 15被干掉  
> 20被干掉  
> 6被干掉  
> 12被干掉  
> 18被干掉  
> 4被干掉  
> 13被干掉  
> 1被干掉  
> 9被干掉  
> 19被干掉  
> 11被干掉  
> 3被干掉  
> 17被干掉  
> 16被干掉  
> 2被干掉  
> 8被干掉  
> 14被干掉  
> 最后这个幸运儿是：7