温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

java怎么解决约瑟夫问题

发布时间:2022-03-22 16:57:56 阅读:183 作者:iii 栏目:大数据
Java开发者专用服务器限时活动,0元免费领,库存有限,领完即止! 点击查看>>

本篇内容介绍了“java怎么解决约瑟夫问题”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!

一、约瑟夫问题介绍

1、约瑟夫问题原题:

n个小孩子手拉手围成一个圈,编号为k(1 <= k <= n )的人从1开始报数,报到m的那个人出列,它的下一位又从1开始报数,报到m的又出列……依此类推,直到所有人都出列,由此产生一个出队编号的序列。

2、问题分析:

根据题目的描述,很容易可以想到用单向循环链表来模拟。先构成一个有n个节点的单向循环链表,然后节点K由1开始计数,计到m时,对应的节点从链表中删除,然后再从被删除的下一个节点由1开始计数,直到所有节点都被删除掉。

java怎么解决约瑟夫问题
单向循环链表

如上图,n等于5,假设从1号开始报数,报到2就出列,即k等于1,m等于2。那么最后出列的结果应该是:2,4,1,5,3。

 

二、单向环形链表的构建

1、构建思路:

  • 首先创建第一个节点,用first指针指向它,它的next指向自己,如下图:
java怎么解决约瑟夫问题
第一个节点
  • 然后创建第二个节点,将第一个节点的next指向第二个节点,第二个节点的next指向第一个节点,如图:
java怎么解决约瑟夫问题
第二个节点

依此类推,就可以构建出单向环形链表。遍历的时候,当节点的next等于first时,表示遍历完毕。

2、代码实现:

根据上面的分析,可以写出如下代码:

package com.zhu.study.linkedList;/** * 约瑟夫问题,即单向循环链表问题 * @author: zhu * @date: 2020/8/30 17:57 */public class Josepfu {    public static void main(String[] args){        CircleSingleLinkedlist linkedlist = new CircleSingleLinkedlist();        linkedlist.add(5);        linkedlist.showNodes();    }}/** * 单向循环链表 */class CircleSingleLinkedlist{    private Node first = null;    /**     * 添加节点     * @param num 需要添加的节点个数     */    public void add(int num){        if (num < 1){            throw new RuntimeException("非法参数");        }        Node cur = null// 当前node        for (int i = 1; i <= num; i++) {            Node node = new Node(i);            if (i == 1) {                first = node;                first.setNext(first); // next指向自己,构成环                cur = first;            } else {                cur.setNext(node);                node.setNext(first);                cur = node;            }        }    }    /**     * 遍历     */    public void showNodes(){        if (first == null){ // 链表为空            return;        }        Node cur = first;        while (true){            System.out.printf("小孩编号%d \n", cur.getNo());            if (cur.getNext() == first){ // 遍历完毕                break;            } else {                cur = cur.getNext();            }        }    }   }/** * 节点内部类 */class Node{    private int no; // 编号    private Node next; // 下一个节点    public Node(int no){        this.no = no;    }    public int getNo() {        return no;    }    public void setNo(int no) {        this.no = no;    }    public Node getNext() {        return next;    }    public void setNext(Node next) {        this.next = next;    }}
     

三、小孩出列的实现

1、思路:

先要找到开始报数的节点,用cur记录下来,比如从第k个开始数,那么cur应该指向k号节点;然后再找到cur的前一个节点,用pre记录下来;找到这两个节点后,由cur开始数(m-1)次,即cur和pre同时移动(m-1)次,此时cur就指向了要被删除的节点;打印要被删除的节点,然后将cur移动到被删除节点的下一个节点,即cur = cur.next,pre的next指向新的cur,即pre.next = cur

2、代码实现:

/**     * 出圈,圈中共有n个人,从第k个开始,数m个开始出圈     * @param k     * @param m     * @param n     */    public void get(int k, int m, int n){        if (k > n || k < 1 || first == null || m > n){            throw new IllegalArgumentException("非法参数");        }        // 先找到k节点,即开始报数的节点,用cur记录下来        Node cur = first;        for (int i = 1; i < k; i++) {            cur = cur.getNext();        }        // 找到k的前一个节点,用pre记录下来        Node pre = cur;        while (true){            if (pre.getNext() == cur){                break;            } else{                pre = pre.getNext();            }        }        // 出圈        while (true) {            if (pre == cur) { // 只有一个节点了                System.out.printf("小孩编号%d\n", cur.getNo());                break;            }            // cur和pre同时移动 m-1次            for (int i = 1; i < m; i++) {                cur = cur.getNext(); // 这个就是要出圈的节点                pre = pre.getNext(); // 这个是要出圈节点的前一个节点            }            System.out.printf("小孩编号%d\n", cur.getNo());            cur = cur.getNext();            pre.setNext(cur);        }    }

调用该方法,k、m、n分别输入1、2、5,最后发现结果和上面分析的一样,打印的是2,4,1,5,3。

“java怎么解决约瑟夫问题”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站,小编将为大家输出更多高质量的实用文章!

亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

原文链接:https://my.oschina.net/u/4602675/blog/4651514

AI

开发者交流群×