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

  1. 云栖社区>
  2. 博客>
  3. 正文

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

pioneer17 2019-09-11 11:52:37 浏览303
展开阅读全文

约瑟夫问题介绍

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

编程描述:

有N个孩子手拉手围成一圈,从第M个孩子开始报数,报到第K个孩子出队,然后从下一个孩子继续开始报数,问:所有孩子的出队顺序?
如下图:
image

约瑟夫问题的数据结构引出:
图 1-1:
10_09_56__09_11_2019

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

10_18_15__09_11_2019

如果我们将每一个小人看人一个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

网友评论

登录后评论
0/500
评论
pioneer17
+ 关注