java怎么解决约瑟夫问题
- 王林转载
- 2023-06-03 09:49:201949浏览
一、约瑟夫问题介绍
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、代码实现：
/**
* 出圈，圈中共有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=1，m=2，n=5时，执行该方法的结果与上述分析相同，输出序列为2,4,1,5,3。
以上是java怎么解决约瑟夫问题的详细内容。更多信息请关注PHP中文网其他相关文章！