本篇内容介绍了“java怎么解决约瑟夫问题”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!
1、约瑟夫问题原题:
n个小孩子手拉手围成一个圈,编号为k(1 <= k <= n )的人从1开始报数,报到m的那个人出列,它的下一位又从1开始报数,报到m的又出列……依此类推,直到所有人都出列,由此产生一个出队编号的序列。
2、问题分析:
根据题目的描述,很容易可以想到用单向循环链表来模拟。先构成一个有n个节点的单向循环链表,然后节点K由1开始计数,计到m时,对应的节点从链表中删除,然后再从被删除的下一个节点由1开始计数,直到所有节点都被删除掉。
如上图,n等于5,假设从1号开始报数,报到2就出列,即k等于1,m等于2。那么最后出列的结果应该是:2,4,1,5,3。
1、构建思路:
依此类推,就可以构建出单向环形链表。遍历的时候,当节点的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元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。
原文链接:https://my.oschina.net/u/4602675/blog/4651514