java怎么解决约瑟夫问题
一、约瑟夫问题介绍
1、约瑟夫问题原题：
n个小孩子手拉手围成一个圈，编号为k(1 <= k <= n )的人从1开始报数，报到m的那个人出列，它的下一位又从1开始报数，报到m的又出列……依此类推，直到所有人都出列，由此产生一个出队编号的序列。
2、问题分析：
根据题目的描述，很容易可以想到用单向循环链表来模拟。先构成一个有n个节点的单向循环链表，然后节点K由1开始计数，计到m时，对应的节点从链表中删除，然后再从被删除的下一个节点由1开始计数，直到所有节点都被删除掉。
假设从编号为1的人开始，每次报数报到2的人出列，如果有$n=5$个人，则$k=1,m=2$。那么最后出列的结果应该是：2，4，1，5，3。
二、单向环形链表的构建
1、构建思路：
首先创建第一个节点，用first指针指向它，它的next指向自己，如下图：
接着，建立第二个节点，并将第一个节点的next指针指向第二个节点，同时将第二个节点的next指针指向第一个节点，如下图所示：
依此类推，就可以构建出单向环形链表。遍历的时候，当节点的next等于first时，表示遍历完毕。
2、代码实现：
根据上面的分析，可以写出如下代码：
<code>package com.zhu.study.linkedList;<br><br>/**<br> * 约瑟夫问题，即单向循环链表问题<br> * @author: zhu<br> * @date: 2020/8/30 17:57<br> */<br>public class Josepfu {<br> public static void main(String[] args){<br> CircleSingleLinkedlist linkedlist = new CircleSingleLinkedlist();<br> linkedlist.add(5);<br> linkedlist.showNodes();<br> }<br>}<br><br>/**<br> * 单向循环链表<br> */<br>class CircleSingleLinkedlist{<br> private Node first = null;<br> /**<br> * 添加节点<br> * @param num 需要添加的节点个数<br> */<br> public void add(int num){<br> if (num < 1){<br> throw new RuntimeException("非法参数");<br> }<br> Node cur = null; // 当前node<br> for (int i = 1; i <= num; i++) {<br> Node node = new Node(i);<br> if (i == 1) {<br> first = node;<br> first.setNext(first); // next指向自己，构成环<br> cur = first;<br> } else {<br> cur.setNext(node);<br> node.setNext(first);<br> cur = node;<br> }<br> }<br> }<br><br> /**<br> * 遍历<br> */<br> public void showNodes(){<br> if (first == null){ // 链表为空<br> return;<br> }<br> Node cur = first;<br> while (true){<br> System.out.printf("小孩编号%d \n", cur.getNo());<br> if (cur.getNext() == first){ // 遍历完毕<br> break;<br> } else {<br> cur = cur.getNext();<br> }<br> }<br> } <br>}<br><br>/**<br> * 节点内部类<br> */<br>class Node{<br> private int no; // 编号<br> private Node next; // 下一个节点<br><br> public Node(int no){<br> this.no = no;<br> }<br><br> public int getNo() {<br> return no;<br> }<br><br> public void setNo(int no) {<br> this.no = no;<br> }<br><br> public Node getNext() {<br> return next;<br> }<br><br> public void setNext(Node next) {<br> this.next = next;<br> }<br>}<br></code>三、小孩出列的实现
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、代码实现：
<code>/**<br> * 出圈，圈中共有n个人，从第k个开始，数m个开始出圈<br> * @param k<br> * @param m<br> * @param n<br> */<br> public void get(int k, int m, int n){<br> if (k > n || k < 1 || first == null || m > n){<br> throw new IllegalArgumentException("非法参数");<br> }<br> // 先找到k节点，即开始报数的节点，用cur记录下来<br> Node cur = first;<br> for (int i = 1; i < k; i++) {<br> cur = cur.getNext();<br> }<br> // 找到k的前一个节点，用pre记录下来<br> Node pre = cur;<br> while (true){<br> if (pre.getNext() == cur){<br> break;<br> } else{<br> pre = pre.getNext();<br> }<br> }<br> // 出圈<br> while (true) {<br> if (pre == cur) { // 只有一个节点了<br> System.out.printf("小孩编号%d\n", cur.getNo());<br> break;<br> }<br> // cur和pre同时移动 m-1次<br> for (int i = 1; i < m; i++) {<br> cur = cur.getNext(); // 这个就是要出圈的节点<br> pre = pre.getNext(); // 这个是要出圈节点的前一个节点<br> }<br> System.out.printf("小孩编号%d\n", cur.getNo());<br> cur = cur.getNext();<br> pre.setNext(cur);<br> }<br> }</code>传入参数为k=1，m=2，n=5时，执行该方法的结果与上述分析相同，输出序列为2,4,1,5,3。
以上就是java怎么解决约瑟夫问题的详细内容，更多请关注其它相关文章！