• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

约瑟夫环问题(Joseph)

互联网 diligentman 4个月前 (10-21) 38次浏览

“约瑟夫生者死者”游戏内容大致描述为: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;
    }
}

 


程序员灯塔
转载请注明原文链接:约瑟夫环问题(Joseph)
喜欢 (0)