数据结构与算法之约瑟夫问题

2021-08-07 05:58:55

约瑟夫问题介绍：

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

编程描述:

有N个孩子手拉手围成一圈，从第M个孩子开始报数，报到第K个孩子出队，然后从下一个孩子继续开始报数，问：所有孩子的出队顺序？
如下图：
数据结构与算法之约瑟夫问题

约瑟夫问题的数据结构引出：
图 1-1：
数据结构与算法之约瑟夫问题

问：用什么数据结构来处理这个问题比较合适呢？
我们不妨将图1-1稍作处理，如下图1-2：

数据结构与算法之约瑟夫问题

如果我们将每一个小人看人一个node节点，每一个节点都有一个指针指向下一个节点，我们很容易的就想到一种数据结构便是单向链表，如果我们将该单项链表的尾和首相连，将尾部指向首部便是图1-1了，便很适合解决该约瑟夫问题，于是我们可以使用单向环形链表数据结构来模拟解决该问题。

数据结构的实现
基础类如下：
模拟孩子的类Child:

class Child {

    private int no;

    private Child next;

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

    public int getNo() {
        return no;
    }

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

    public Child getNext() {
        return next;
    }

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

模拟约瑟夫环的类CircleSingleLinkedList:

class CircleSingleLinkedList {
    private Child head;

    public void init(int n) {
        //todo
      

    }


    public void show() {
        //todo
    }

    public void delete(int no) {
        //todo
    }
}

CircleSingleLinkedList的方法实现：

  1. 初始化创建带有N个节点的约瑟夫环：
    分析：我们只要做到将上一个节点的next指向下一个节点，最后一个节点的next指向第一个即可
public void init(int n) {
        Child cur;
        if (n < 1) {
            return;
        } else if (n == 1) {
            child = new Child(1);
            child.setNext(child);
        } else {
            child = new Child(1);
            child.setNext(child);
            cur = child;
            for (int i = 2; i <= n; i++) {
                cur = cur.getNext();
                Child cd = new Child(i);
                cur.setNext(cd);
                cd.setNext(child);
            }
        }

    }

2.打印约瑟夫环：
分析：从头结点遍历每一个节点，当节点的getNext()==head时，便遍历结束了，相当于遍历到了最后一个

public void show() {
        if (head == null) {
            return;
        }
        if (head.getNext() == head) {
            System.out.println(head.getNo());
            return;
        }
        Child cur = head;
        while (cur.getNext() != head) {
            System.out.println(cur.getNo());
            cur = cur.getNext();

        }
        System.out.println(cur.getNo());
    }

3.为约瑟夫环增加一个节点到最后:
分析：从头结点遍历到最后，将最后一个节点的next指向增加的节点，将增加的节点next指向头结点head即可

public void addLast(Child child) {
        Child cur = head;
        while (cur.getNext() != head) {
            if (cur.getNo()==child.getNo()){
                throw new RuntimeException("编号已存在！！");
            }
            cur = cur.getNext();
        }
        if (cur.getNo()==child.getNo()){
            throw new RuntimeException("编号已存在！！");
        }
        cur.setNext(child);
        child.setNext(head);
    }

4.删除一个约瑟夫环的节点：
遍历约瑟夫环，找到待删除节点的上一个节点，将上一个节点的next指向待删除节点的next即可，但是如果是删除的头结点，则需要将头结点的下一个节点指定为头结点

public void delete(int no) {
        if (head == null) {
            return;
        }
        Child cur = head;
        while (cur.getNext() != head) {
            if (cur.getNext().getNo() == no) {
                cur.setNext(cur.getNext().getNext());
                return;
            }
            cur = cur.getNext();
        }
        if (cur.getNext().getNo() == no) {
            cur.setNext(cur.getNext().getNext());
            head = cur.getNext();
        }

    }

至此约瑟夫环的数据结构及基础方法如下：

class CircleSingleLinkedList {
    private Child head;

    public void init(int n) {
        Child cur;
        if (n < 1) {
            return;
        } else if (n == 1) {
            head = new Child(1);
            head.setNext(head);
        } else {
            head = new Child(1);
            head.setNext(head);
            cur = head;
            for (int i = 2; i <= n; i++) {
                cur = cur.getNext();
                Child cd = new Child(i);
                cur.setNext(cd);
                cd.setNext(head);
            }
        }

    }

    public void addLast(Child child) {
        Child cur = head;
        while (cur.getNext() != head) {
            if (cur.getNo()==child.getNo()){
                throw new RuntimeException("编号已存在！！");
            }
            cur = cur.getNext();
        }
        if (cur.getNo()==child.getNo()){
            throw new RuntimeException("编号已存在！！");
        }
        cur.setNext(child);
        child.setNext(head);
    }


    public void show() {
        if (head == null) {
            return;
        }
        if (head.getNext() == head) {
            System.out.println(head.getNo());
            return;
        }
        Child cur = head;
        while (cur.getNext() != head) {
            System.out.println(cur.getNo());
            cur = cur.getNext();

        }
        System.out.println(cur.getNo());
    }

    public void delete(int no) {
        if (head == null) {
            return;
        }
        Child cur = head;
        while (cur.getNext() != head) {
            if (cur.getNext().getNo() == no) {
                cur.setNext(cur.getNext().getNext());
                return;
            }
            cur = cur.getNext();
        }
        if (cur.getNext().getNo() == no) {
            cur.setNext(cur.getNext().getNext());
            head = cur.getNext();
        }

    }
}

在约瑟夫环数据结构上解决约瑟夫问题
我们从beginNo个孩子开始报数，每一次报readNum个数，则如何进行出队呢？
分析：从第beginNo个孩子作为游戏的开始，就相当于移动约瑟夫环的头结点，将第beginNo个节点作为头结点。我们需要一个辅助指针来进行出队，该指针初始指向尾节点。报数相当于移动头结点和辅助指针，头结点到出队的那一个节点，将辅助指针的next指向头结点的next便完成了出队。然后将辅助指针的next作为头结点即可，直到只剩下最后一个节点。及头结点和辅助指针指向的节点是同一个接点。

public void josephPop(int beginNo, int readNum) {
        if (head == null) {
            return;
        }
        Child helper = head;
        while (true) {
            if (helper.getNext() == head) {
                break;
            }
            helper = helper.getNext();
        }
        for (int i = 1; i < beginNo; i++) {
            head = head.getNext();
            helper = helper.getNext();
        }
        while (head != helper) {
            for (int i = 0; i < readNum - 1; i++) {
                head = head.getNext();
                helper = helper.getNext();
            }
            System.out.println(head.getNo());
            helper.setNext(head.getNext());
            head = helper.getNext();
        }

        System.out.println(helper.getNo());

    }

至此约瑟夫环及约瑟夫问题模拟如下：

class CircleSingleLinkedList {
    private Child head;

    public void init(int n) {
        Child cur;
        if (n < 1) {
            return;
        } else if (n == 1) {
            head = new Child(1);
            head.setNext(head);
        } else {
            head = new Child(1);
            head.setNext(head);
            cur = head;
            for (int i = 2; i <= n; i++) {
                cur = cur.getNext();
                Child cd = new Child(i);
                cur.setNext(cd);
                cd.setNext(head);
            }
        }

    }

    public void addLast(Child child) {
        Child cur = head;
        while (cur.getNext() != head) {
            if (cur.getNo()==child.getNo()){
                throw new RuntimeException("编号已存在！！");
            }
            cur = cur.getNext();
        }
        if (cur.getNo()==child.getNo()){
            throw new RuntimeException("编号已存在！！");
        }
        cur.setNext(child);
        child.setNext(head);
    }


    public void show() {
        if (head == null) {
            return;
        }
        if (head.getNext() == head) {
            System.out.println(head.getNo());
            return;
        }
        Child cur = head;
        while (cur.getNext() != head) {
            System.out.println(cur.getNo());
            cur = cur.getNext();

        }
        System.out.println(cur.getNo());
    }

    public void delete(int no) {
        if (head == null) {
            return;
        }
        Child cur = head;
        while (cur.getNext() != head) {
            if (cur.getNext().getNo() == no) {
                cur.setNext(cur.getNext().getNext());
                return;
            }
            cur = cur.getNext();
        }
        if (cur.getNext().getNo() == no) {
            cur.setNext(cur.getNext().getNext());
            head = cur.getNext();
        }

    }

    public void josephPop(int beginNo, int readNum) {
        if (head == null) {
            return;
        }
        Child helper = head;
        while (true) {
            if (helper.getNext() == head) {
                break;
            }
            helper = helper.getNext();
        }
        for (int i = 1; i < beginNo; i++) {
            head = head.getNext();
            helper = helper.getNext();
        }
        while (head != helper) {
            for (int i = 0; i < readNum - 1; i++) {
                head = head.getNext();
                helper = helper.getNext();
            }
            System.out.println(head.getNo());
            helper.setNext(head.getNext());
            head = helper.getNext();
        }

        System.out.println(helper.getNo());


    }
}

测试
创建一个5个节点的约瑟夫环，从第一个节点开始报数，每次报3个数，出队顺序如下：

public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.init(5);
        circleSingleLinkedList.josephPop(1, 3);
    }

出队顺序为：3 1 5 2 4

上一篇：Shell总结


下一篇：大数据：新的自然资源