約瑟夫問題 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個元素，后面元素往前移動