“約瑟夫生者死者”游戲內(nèi)容大致描述為：30個(gè)游客同乘一條船，因?yàn)閲?yán)重超載，加上風(fēng)浪大作，危險(xiǎn)萬(wàn)分。因此，船長(zhǎng)告訴乘客，只有將船上一半的旅客投入大海中，其余的人才能幸免于難。無(wú)奈，大家只得同意這種辦法，并議定30個(gè)人圍城一圈，由第一個(gè)人數(shù)起，依次報(bào)數(shù)，數(shù)到第9人，便把他投入大海中，然后再?gòu)乃南乱粋€(gè)數(shù)起，數(shù)到第9人，再把他扔進(jìn)大海中，如此重復(fù)地進(jìn)行，直到剩下15個(gè)乘客為止。請(qǐng)編程模擬此過(guò)程。

不帶頭結(jié)點(diǎn)，帶頭指針和尾指針的單線循環(huán)鏈表實(shí)現(xiàn)（參數(shù)可調(diào)控）：

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();              //創(chuàng)建的約瑟夫環(huán)所含的結(jié)點(diǎn)個(gè)數(shù)
        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();              //投入大海間隔的人數(shù)（每次數(shù)到gapOfDeaths即投入大海）
        System.out.print("Enter the number of deaths to die: ");
        final int numberOfDeaths = scanner.nextInt();           //投入大海的人數(shù)
        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;
    }
}