约瑟夫问题 java 实现详解编程语言

约瑟夫问题

这是17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，数到第九个人就将他扔入大海。该人后面的人从1开始重新报数，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。

思路
1. 先建立一个类，有 id 和 isRemove

class Person { 
    int id; 
    boolean isRemove; 
 
    public Person(int id, boolean isRemove) { 
        this.id = id; 
        this.isRemove = isRemove; 
    } 
 
    public boolean isRemove() { 
        return isRemove; 
    } 
 
    public void setRemove(boolean isRemove) { 
        this.isRemove = isRemove; 
    } 
}

2.

class Circle { 
    private ArrayList<Person> circle = new ArrayList<Person>(); 
 
    private int amount; // 一共多少人 
 
    Circle(int amount) { 
        this.amount = amount; 
        for (int i = 0; i < amount; i++) { 
            Person p = new Person(i + 1, false); 
            circle.add(p); 
        } 
    } 
 
    /** * * @param index * 最开始扔人的位置，比如第9人 * @param total * 共需要扔几次 */ 
    public void getIndex(int index, int total) { 
 
        // 起始位置 
        int currentIndex = -1; 
 
        for (int t = 0; t < total; t++) { 
            int notRemove = 0; 
 
            //本来是notRemove != 9，写死不好 
            while (notRemove != index) { 
                currentIndex++; 
                // 或者用 currentIndex % amount 解决 
                if (currentIndex == amount) { 
                    currentIndex = 0; 
                } 
                if (!circle.get(currentIndex).isRemove) { 
                    notRemove++; 
                } 
            } 
 
            // 将扔的人设为 true 
            Person p = circle.get(currentIndex); 
            p.setRemove(true); 
            circle.set(currentIndex, p); 
 
            System.out.printf("第 %-2d 次仍的人id是%4d/n", t + 1, p.id); 
 
        } 
 
    } 
 
} 

代码建立一个容器来保存各个人，主要就是不移除这个人，而是把他状态设为setRemove(true)，好处这样容器的大小保持不变。如果删掉这样人，容器大小每次减1，算起来麻烦

if (currentIndex == amount) { currentIndex = 0; }

本来是用 currentIndex % amount 实现的，不过本代码都是+1，肯定会有 == amount的情况，用置为0更好

结果

第 1  次仍的人id是   9 
第 2  次仍的人id是  18 
第 3  次仍的人id是  27 
第 4  次仍的人id是   6 
第 5  次仍的人id是  16 
第 6  次仍的人id是  26 
第 7  次仍的人id是   7 
第 8  次仍的人id是  19 
第 9  次仍的人id是  30 
第 10 次仍的人id是  12 
第 11 次仍的人id是  24 
第 12 次仍的人id是   8 
第 13 次仍的人id是  22 
第 14 次仍的人id是   5 
第 15 次仍的人id是  23 

优化

也可以用数组实现，下标和 boolean 正好模拟上面的 Person 类

static void other() { 
    boolean[] usaJapa = new boolean[30]; 
    // 用类库初始化 
    Arrays.fill(usaJapa, true); 
 
    int leftCount = usaJapa.length; 
 
    int countNum = 0; 
    int index = 0; 
    int i = 0; 
    while (leftCount > 15) { 
        if (usaJapa[index]) { 
            countNum++; 
        } 
 
        if (countNum == 9) { 
            countNum = 0; 
            usaJapa[index] = false; 
            leftCount--; 
            System.out.printf("第 %-2d 次仍的人id是%4d/n", ++i, index + 1); 
 
        } 
 
        index++; 
        if (index == usaJapa.length) { 
            index = 0; 
        } 
    } 
 
}

用链表实现，remove 其中的数据

class Circle { 
    private LinkedList<Person> circle = new LinkedList<Person>(); 
 
    private int amount; // 一共多少人 
 
    Circle(int amount) { 
        this.amount = amount; 
        for (int i = 0; i < amount; i++) { 
            Person p = new Person(i + 1, false); 
            circle.add(p); 
        } 
    } 
 
    public void othergetIndex(int mark, int total) { 
        // remain 是剩下的人数，total 是需要删除的人数 
        int remain = amount; 
        int count = 0; 
        int current = 0; 
        int i = 0; 
        while (remain > amount - total) { 
            count++; 
            // 注意这人如果达到 mark，比如第9个人 
            // 删掉第9个人后，再删第9个人，就是删原来的第10个人 
            if (count == mark) { 
                // remove 返回的是删除的 Person 
                Person p = circle.remove(current); 
                System.out.printf("第 %-2d 次仍的人id是%4d/n", ++i, p.id); 
                count = 0; 
                remain--; 
            } else { 
                current++; 
            } 
            if (current == amount - i) { 
                current = 0; 
            } 
 
        } 
 
    } 
}

用 LinkedList 删除操作更快，

Person p = circle.remove(current);
remove 返回删除的元素

LinkedList<Integer> testList = new LinkedList<Integer>(); 
for (int i = 0; i < 10; i++) { 
        testList.add(i); 
} 
for (int i = 0; i < 5; i++) { 
    System.out.println(testList.remove(3)); 
}   /** * 3 * 4 * 5 * 6 * 7 */ 
 

这段代码的输出可以看出，删除了第3个元素，后面元素往前移动