问题来历

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
 

面向对象还是面向过程？

如果你脑海里都是if-else之类的，或者各种高阶公式，那么你可能在使用面向过过程的思维方式，当然如果你数学够好，可能有很好的解法

如果你想不到直接的解决办法，不妨尝试下面向对象的思维方式。

先构造一个环形结构，每个节点代表一个人，然后开始数数，数到第三个就把这个节点从环形结构中移除，最后剩下的就是活下来的，这样是不是就简单很多了。

当然，这个环形结构肯定需要有个头，不然Josephus可能也不知道该站在第几个位置。

其实实现方式有很多，环形结构用数组和链表也都行。

以下是我的实现方式，仅供参考。

代码实现：

package com.zby;

public class JosephusCircle {

    private Node headNode;

    public void add(Object data) {
        Node newNode = new Node();
        newNode.dataObject = data;
        if (null == headNode) {
            headNode = newNode;
            newNode.preNode = newNode;
            newNode.nextNode = newNode;
        } else {
            Node lastNode = headNode.preNode;
            lastNode.nextNode = newNode;
            newNode.preNode = lastNode;
            newNode.nextNode = headNode;
            headNode.preNode = newNode;
        }

    }

    public void removeIndexAndReset(int index) {
        if (null == headNode) {
            System.out.println("请先添加节点");
            return;
        }
        while (headNode.nextNode != headNode) {
            Node removeNode = headNode;
            for (int i = 1; i < index; i++) {
                removeNode = removeNode.nextNode;
            }
            headNode = removeNode.nextNode;
            removeNode.preNode.nextNode = removeNode.nextNode;
            removeNode.nextNode.preNode = removeNode.preNode;
            System.out.println(removeNode + "自杀");
        }
        System.out.println(headNode + "存活");
    }

    private class Node {
        private Node preNode;
        private Node nextNode;
        private Object dataObject;

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            builder.append("Node [dataObject=");
            builder.append(dataObject);
            builder.append("]");
            return builder.toString();
        }


    }

    public static void main(String[] args) {
        JosephusCircle josephusCircle = new JosephusCircle();
        for (int i = 1; i < 42; i++) {
            if (i == 16) {
                josephusCircle.add("第" + i  + "个是约瑟夫的朋友");
            } else if (i == 31) {
                josephusCircle.add("第" + i  + "个是约瑟夫");
            } else {
                josephusCircle.add("第" + i + "个是犹太人");
            }
        }
        josephusCircle.removeIndexAndReset(3);

    }
}

Node [dataObject=第3个是犹太人]自杀
Node [dataObject=第6个是犹太人]自杀
Node [dataObject=第9个是犹太人]自杀
Node [dataObject=第12个是犹太人]自杀
Node [dataObject=第15个是犹太人]自杀
Node [dataObject=第18个是犹太人]自杀
Node [dataObject=第21个是犹太人]自杀
Node [dataObject=第24个是犹太人]自杀
Node [dataObject=第27个是犹太人]自杀
Node [dataObject=第30个是犹太人]自杀
Node [dataObject=第33个是犹太人]自杀
Node [dataObject=第36个是犹太人]自杀
Node [dataObject=第39个是犹太人]自杀
Node [dataObject=第1个是犹太人]自杀
Node [dataObject=第5个是犹太人]自杀
Node [dataObject=第10个是犹太人]自杀
Node [dataObject=第14个是犹太人]自杀
Node [dataObject=第19个是犹太人]自杀
Node [dataObject=第23个是犹太人]自杀
Node [dataObject=第28个是犹太人]自杀
Node [dataObject=第32个是犹太人]自杀
Node [dataObject=第37个是犹太人]自杀
Node [dataObject=第41个是犹太人]自杀
Node [dataObject=第7个是犹太人]自杀
Node [dataObject=第13个是犹太人]自杀
Node [dataObject=第20个是犹太人]自杀
Node [dataObject=第26个是犹太人]自杀
Node [dataObject=第34个是犹太人]自杀
Node [dataObject=第40个是犹太人]自杀
Node [dataObject=第8个是犹太人]自杀
Node [dataObject=第17个是犹太人]自杀
Node [dataObject=第29个是犹太人]自杀
Node [dataObject=第38个是犹太人]自杀
Node [dataObject=第11个是犹太人]自杀
Node [dataObject=第25个是犹太人]自杀
Node [dataObject=第2个是犹太人]自杀
Node [dataObject=第22个是犹太人]自杀
Node [dataObject=第4个是犹太人]自杀
Node [dataObject=第35个是犹太人]自杀
Node [dataObject=第16个是约瑟夫的朋友]自杀
Node [dataObject=第31个是约瑟夫]存活

 当然，我们只留下了最后一个人，第31号位置，说明如果Josephus把自己放在了绝对安全的位置，如果他的朋友想继续玩，那么Josephus也不会死！