【Java】单循环链表解决约瑟夫环问题

问题描述

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

数据结构

辅助解决问题的数据结构： 单向循环链表

编写结点类

本例中用Integer而放弃了泛型

public class LinkedNode {
    
    private Integer data;
    
    private LinkedNode next;
    
    public LinkedNode() {
        this.data = null;
        this.next = null;
    }
    
    public LinkedNode(Integer element) {
        this.data = element;
        this.next = null;
    }

    public Integer getData() {
        return data;
    }

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

    public LinkedNode getNext() {
        return next;
    }

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

}

约瑟夫环的链表实现（单向循环链表）

public class CircularSinglyLinkedList {
    
    /**
     * 尾引用
     */
    protected LinkedNode rear;
    
    /**
     * 头引用
     */
    protected LinkedNode first;
    
    public CircularSinglyLinkedList() {
        rear = null;
    }
    
    public void joseph(int n, int m) {
        //createCircular函数初始化n个结点的约瑟夫环
        createCircular(n);
        //初始化pre为表尾
        LinkedNode pre = rear;
        //初始化p为表头
        LinkedNode p = rear.getNext();
        //初始化计数器count
        int count = 1;
        System.out.println("出环的顺序为：");
        //循环到环中只剩一个结点
        while (p.getNext() != p) {
            //计数器未累加到密码值
            if (count