约瑟夫问题Java环形单向链表代码实现

约瑟夫问题Java环形单向链表代码实现

这里写目录标题

• 约瑟夫问题的由来
• 解题思路
• 代码实现
• 测试

约瑟夫问题的由来

约瑟夫是1世纪的一名犹太历史学家。他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而约瑟夫和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。Josephus将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

简而言之

• N个人围成一圈
• 从第M个开始报数，第K个将被杀掉
• 剩余的人重新围成圈，从被杀的下一个人开始报数，将报到K的人杀掉
• 依此循环直到剩下最后一个人
  例如N=6，M=2，K=5，被杀掉的顺序是：6、5、1、3、4、2。

解题思路

首先初始化环形单向链表并且定义两个指针一个指向链表的首结点一个指向链表的尾结点

然后确定第一个开始数数的人的位置（本题以M=2为例）

找到数到K的人（本题K=5）

杀掉数到K的人

接下里依次循环上述步骤

代码实现

public class PersonNode {
	//人的编号
    private int no;
    //指向下一个结点
    private PersonNode next;
    //构造方法
    public PersonNode(int no) {
        this.no = no;
    }
    public int getNo() {
        return no;
    }
    public void setNo(int no) {
        this.no = no;
    }
    public PersonNode getNext() {
        return next;
    }
    public void setNext(PersonNode next) {
        this.next = next;
    }
    @Override
    public String toString() {
        return "PersonNode{" +"no=" + no +'}';
    }
}

public class PersonCirclelinkList {
	//初始化首结点
    private PersonNode first = new PersonNode(-1);
    
    public void init(int num){
        if (num<1){
        	//链表长度小于1没有意义
            System.out.println("结点的数量不能小于1");
            return;
        }
        PersonNode temp = first;
        for (int i = 1; i <=num ; i++) {
            if(i == 1){
                //如果只有一个结点就让首结点的next指向自己
                temp.setNo(1);
                temp.setNext(first);
            }else{
            	//当环形链表长度大于2时每次循环都会创建一个结点加在链表的尾部
            	//再让尾部结点的next指向首结点
                PersonNode personNode = new PersonNode(i);
                temp.setNext(personNode);
                personNode.setNext(first);
                temp=temp.getNext();
            }
        }
    }
    
    public void show(){
        if (first.getNext() == null){
            System.out.println("当前链表为空");
            return;
        }
        PersonNode temp = first;
        while(true){
            System.out.println(temp);
            if (temp.getNext() == first){
                //遍历到链表的最后一个结点
                return;
            }
            temp = temp.getNext();
        }
    }

    
    public void killPerson(int start,int num,int count){
        init(count);
        if(first == null||start<0||num<0||start>count){
            System.out.println("参数不正确");
        }
        PersonNode last = first;
        while(true){
            if (last.getNext() == first) {
                //last指向环形链表中的最后一个元素
                break;
            }
            last = last.getNext();
        }
        //确定开始报数的位置
        for (int i = 0; i < start-1 ; i++) {
            first = first.getNext();
            last = last.getNext();
        }

        while(true){
            if (last == first){
                //只有一个结点就结束循环（剩下最后一个人）
                break;
            }
            //开始数数 for循环结束first指向数到K的人
            for (int i = 0; i < num - 1; i++) {
                first = first.getNext();
                last = last.getNext();
            }
            System.out.println(first.getNo()+"号kill");
            first=first.getNext();
            last.setNext(first);
        }
        //最后一个存活下来的人
        System.out.println(first.getNo()+"号存活");
    }
}

测试

public class PersonCircleTest {
    public static void main(String[] args) {
        PersonCirclelinkList linkList = new PersonCirclelinkList();
        linkList.killPerson(2,5,6);
    }
}

输出结果