約瑟夫環問題（Joseph）

“約瑟夫生者死者”游戲內容大致描述為：30個游客同乘一條船，因為嚴重超載，加上風浪大作，危險萬分，因此，船長告訴乘客，只有將船上一半的旅客投入大海中，其余的人才能幸免于難，無奈，大家只得同意這種辦法，并議定30個人圍城一圈，由第一個人數起，依次報數，數到第9人，便把他投入大海中，然后再從他的下一個數起，數到第9人，再把他扔進大海中，如此重復地進行，直到剩下15個乘客為止，請編程模擬此程序，

不帶頭結點，帶頭指標和尾指標的單線回圈鏈表實作（引數可調控）：

package data_structure_experiment2_linkedlist.applied_design_experiment;

import java.util.Scanner;

public class JosephCycle<T> {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the number of nodes in Joseph's cycle: ");
        int numberOfJosephNode = scanner.nextInt();              //創建的約瑟夫環所含的結點個數
        JosephCycle<Integer> josephCycle = new JosephCycle();
        for (int i = 0; i < numberOfJosephNode; i++) {
            josephCycle.add(new JosephCycleNode(i + 1));
        }
        System.out.println("The Joseph cycle was successfully created: ");
        josephCycle.print();
        System.out.print("Enter the gap of deaths to die: ");
        final int gapOfDeaths = scanner.nextInt();              //投入大海間隔的人數（每次數到gapOfDeaths即投入大海）
        System.out.print("Enter the number of deaths to die: ");
        final int numberOfDeaths = scanner.nextInt();           //投入大海的人數
        josephCycle.josephCycleLifeOrDeath(gapOfDeaths, numberOfDeaths);
        System.out.println("After the man was killed, joseph circled the people left behind: ");
        josephCycle.print();
        /*int curNumberOfDeaths = 0;                          //以下注釋了的代碼，為封裝成方法前撰寫的代碼，可以忽略，
        int indexOfJosephCycle = 0;
        int indexOfCount = 0;
        JosephCycleNode<Integer> josephCycleNode = josephCycle.getHead();
        while (curNumberOfDeaths<numberOfDeaths){
            josephCycleNode = josephCycleNode.getNext();
            indexOfJosephCycle = (indexOfJosephCycle+1)%josephCycle.getNumberOfNode();
            indexOfCount = (indexOfCount+1)%gapOfDeaths;
            if (indexOfCount==gapOfDeaths-1){
                josephCycle.delete(indexOfJosephCycle);
                indexOfJosephCycle--;
                curNumberOfDeaths++;
            }
        }
        josephCycleNode = josephCycle.getHead();
        for (int i = 0; i < josephCycle.getNumberOfNode(); i++) {
            System.out.print(josephCycleNode.getData()+"\t");
            josephCycleNode = josephCycleNode.getNext();
        }*/
    }

    private JosephCycleNode<T> head;
    private JosephCycleNode<T> tail;
    private int numberOfNode = 0;

    public JosephCycle() {
    }

    public JosephCycleNode<T> getHead() {
        return head;
    }

    public JosephCycleNode<T> getTail() {
        return tail;
    }

    public int getNumberOfNode() {
        return numberOfNode;
    }

    public void add(JosephCycleNode<T> node) {
        if (head == null) {
            head = tail = node;
            node.setNext(node);
        } else {
            tail.setNext(node);
            tail = node;
            tail.setNext(head);
        }
        numberOfNode++;
    }

    public void delete(int index) {
        if (index < 0) {
            throw new RuntimeException("The index of the deleted node cannot be negative.The deletion failed!");
        }
        if (index == 0) {
            tail.setNext(head.getNext());
            head = tail.getNext();
            numberOfNode--;
            return;
        }
        int indexOfJosephCycle = 0;
        JosephCycleNode josephCycleIndexNode = head;
        for (; josephCycleIndexNode.getNext() != head && indexOfJosephCycle < index - 1; indexOfJosephCycle++) {
            josephCycleIndexNode = josephCycleIndexNode.getNext();
        }
        if (indexOfJosephCycle == index - 1) {
            josephCycleIndexNode.setNext(josephCycleIndexNode.getNext().getNext());
            if (index == numberOfNode - 1) {
                tail = josephCycleIndexNode;
            }
            numberOfNode--;
        } else {
            throw new RuntimeException("The number of nodes in Joseph's cycle is:" + ++indexOfJosephCycle);
        }
    }

    public void josephCycleLifeOrDeath(int gapOfDeaths, int numberOfDeaths) {
        if (numberOfDeaths >= numberOfNode) {
            throw new RuntimeException("The death toll is greater than or equal to the total number of deaths");
        }
        int curNumberOfDeaths = 0;
        int indexOfJosephCycle = 0;
        int indexOfCount = 0;
        JosephCycleNode<T> josephCycleNode = head;
        while (curNumberOfDeaths < numberOfDeaths) {
            josephCycleNode = josephCycleNode.getNext();
            indexOfJosephCycle = (indexOfJosephCycle + 1) % numberOfNode;
            indexOfCount = (indexOfCount + 1) % gapOfDeaths;
            if (indexOfCount == gapOfDeaths - 1) {
                delete(indexOfJosephCycle);
                indexOfJosephCycle--;
                curNumberOfDeaths++;
            }
        }
    }

    public void print() {
        JosephCycleNode<T> josephCycleNode = head;
        for (int i = 0; i < numberOfNode; i++) {
            System.out.print(josephCycleNode.getData() + "\t");
            josephCycleNode = josephCycleNode.getNext();
        }
        System.out.println();
    }

}

class JosephCycleNode<T> {
    private T data;
    private JosephCycleNode next;

    public JosephCycleNode() {
    }

    public JosephCycleNode(T data) {
        this.data = data;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public JosephCycleNode getNext() {
        return next;
    }

    public void setNext(JosephCycleNode next) {
        this.next = next;
    }
}