[数据结构与算法]Josephu（约瑟夫）问题

Josephu（约瑟夫）问题

一、介绍

1、Josephu（约瑟夫）问题

? 设编号为1,2,…n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依此类推，直到所有人出列为止，由此产生一个出队编号的序列

提示:用一个不带头节点的圆形链表来解决Josephu问题: 首先形成一个循环链表节点n,然后从k节点数从1,数到m,相应的节点从链表中删除,然后从删除节点的下一个节点数从1,直到最后一个节点从链表的删除算法结束。

2、单向循环链表

二、单项循环链表

1、节点

public class Boy {

    /**
     * 编号
     */
    private int no;

    /**
     * 下一个元素 Boy
     */
    private Boy next;

    public Boy(int no){
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

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

2、单向循环列表

public class CircleSingleLinkedList {


    /**
     * 初始化第一个节点
     */
    private Boy first = null;


    /**
     * 添加nums个元素
     *
     * @param nums
     */
    public void addBoy(int nums) {


        if (nums < 1) {
            System.out.println("参数错误，参数需大于0");
            return;
        }


        Boy temp = null;


        for (int i = 1; i <= nums; i++) {


            Boy boy = new Boy(i);


            if (i == 1) {

                first = boy;

                first.setNext(first);

                temp = first;
            } else {

                temp.setNext(boy);

                boy.setNext(first);

                temp = boy;

            }

        }

    }


    /**
     * 打印链表
     */
    public void print() {


        if (first == null) {
            System.out.println("链表为空");
            return;
        }


        Boy temp = first;


        while (true) {

            //打印
            System.out.printf("编号：%d\n", temp.getNo());


            if (temp.getNext() == first) {
                break;
            }


            temp = temp.getNext();
        }
    }


    /**
     * @param startNo  表示从第几个小孩开始数数
     * @param countNum 表示数几下
     * @param nums     表示还有多少小孩在圈中
     */
    public void josepfu(int startNo, int countNum, int nums) {


        if (first == null) {
            System.out.println("链表为空");
            return;
        }


        if (countNum < 1) {
            System.out.println("countNum输入有误，需大于等于1");
            return;
        }


        if (startNo > nums) {
            System.out.println("startNo输入有误，需小于等于nums");
        }


        Boy helper = first;


        while (true) {
            if (helper.getNext() == first) {
                break;
            }
            helper = helper.getNext();
        }


        for (int j = 0; j < startNo - 1; j++) {
            first = first.getNext();
            helper = helper.getNext();
        }

        while (true) {

            if (helper == first) {
                break;
            }

            for (int j = 0; j < countNum - 1; j++) {
                first = first.getNext();
                helper = helper.getNext();
            }


            System.out.printf("小孩%d出圈\n", first.getNo());


            first = first.getNext();
            helper.setNext(first);

        }
        System.out.printf("最后留在圈中的小孩编号%d\n", first.getNo());
    }

}

3、约瑟夫问题测试

public class Josepfu {

    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(5);
        circleSingleLinkedList.josepfu(1,2,5);
    }

}

4、结果