数据结构与算法之约瑟夫问题-低调大师

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

2019-09-10 909 89

约瑟夫问题介绍：

据说著名犹太历史学家 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的方法实现：

初始化创建带有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

微信关注我们

原文链接：https://yq.aliyun.com/articles/718047

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

Python 的整数与 Numpy 的数据溢出

某位 A 同学发了我一张截图，问为何结果中出现了负数？看了图，我第一感觉就是数据溢出了。数据超出能表示的最大值，就会出现奇奇怪怪的结果。然后，他继续发了张图，内容是 print(100000*208378)，就是直接打印上图的 E[0]*G[0]，结果是 20837800000，这是个正确的结果。所以新的问题是：如果说上图的数据溢出了，为何直接相乘的数却没有溢出？由于我一直忽视数据的表示规则（整型的上限是多少？），而且对 Numpy 了解不多，还错看了图中结果，误以为每一个数据都是错误的，所以就解答不出来。最后，经过学习群里的一番讨论，我才终于明白是怎么回事，所以本文把相关知识点做个梳理。在正式开始之前，先总结一下上图会引出的话题： Python 3 中整数的上限是多少？Python 2 呢？ Numpy 中整数的上限是多少？出现整数溢出该怎么办？关于第一个问题，先看看 Python 2，它有两种整数：一种是短整数，也即常说的整数，用 int 表示，有个内置函数 int()。其大小有限，可通过sys.maxint() 查看（取决于平台是 32 位还是 64 位）一种是...

623

简述下Vue组件化封装过程?

概念组件系统是 Vue 的另一个重要概念，因为它是一种抽象，允许我们使用小型、独立和通常可复用的组件构建大型应用。仔细想想，几乎任意类型的应用界面都可以抽象为一个组件树： !!! 熟记 : 页面中可复用的结构、样式和功能，抽离成一个文件; 特点: 为了便于组织和管理代码 , 便于维护和扩展维护组件化和模块化的不同: 模块化:是从代码逻辑的角度进行划分的;方便代码分层开发，保证每个功能模块的职能单一组件化:是从UI界面的角度进行划分的前端的组件化方便组件的重用; 全局组件这些组件是全局注册的。也就是说它们在注册之后可以用在任何新创建的 Vue 根实例 (new Vue) 的模板中。 1. 注册 Vue.component('MyDemo'{ template:`<div>这个的全局组件的注册</div>` }) 2.实例化 Vue var vm = new Vue({ el:'#app', }) 3. 使用组件 <div id="app"> <my-demo></my-demo> </div> !!!注意事...

968

资源下载

更多资源

优质分享Android(本站安卓app)

近一个月的开发和优化，本站点的第一个app全新上线。该app采用极致压缩，本体才4.36MB。系统里面做了大量数据访问、缓存优化。方便用户在手机上查看文章。后续会推出HarmonyOS的适配版本。

Mario，低调大师唯一一个Java游戏作品

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长，特征是大鼻子、头戴帽子、身穿背带裤，还留着胡子。与他的双胞胎兄弟路易基一起，长年担任任天堂的招牌角色。

Oracle Database，又名Oracle RDBMS

Oracle Database，又名Oracle RDBMS，或简称Oracle。是甲骨文公司的一款关系数据库管理系统。它是在数据库领域一直处于领先地位的产品。可以说Oracle数据库系统是目前世界上流行的关系数据库管理系统，系统可移植性好、使用方便、功能强，适用于各类大、中、小、微机环境。它是一种高效率、可靠性好的、适应高吞吐量的数据库方案。

Java Development Kit(Java开发工具)

JDK是 Java 语言的软件开发工具包，主要用于移动设备、嵌入式设备上的java应用程序。JDK是整个java开发的核心，它包含了JAVA的运行环境（JVM+Java系统类库）和JAVA工具。