How to solve Joseph problem in java

1. Introduction to Joseph’s Question

1. Original title of Joseph’s Question:

n children hold hands and form a circle. The person numbered k (1

2. Problem analysis:

According to the description of the problem, it is easy to think of using a one-way circular linked list to simulate it. First, a one-way circular linked list with n nodes is formed, and then node K starts counting from 1. When m is counted, the corresponding node is deleted from the linked list, and then counting starts from 1 from the next deleted node until all Nodes are deleted.

One-way circular linked list

Assume that starting from the person numbered 1, each time the number is reported, the person 2 will be listed out. If there are $n= 5$ individuals, then $k=1,m=2$. Then the final result should be: 2, 4, 1, 5, 3.

2. Construction of one-way circular linked list

1. Construction ideas:

• First create the first node, point to it with the first pointer, and its next points to itself, as shown below:

First node

• Next, create a second node, point the next pointer of the first node to the second node, and point the next pointer of the second node to the first node, as follows As shown in the figure:

The second node

and so on, you can build a one-way circular linked list. When traversing, when the next of the node is equal to first, it means that the traversal is completed.

2. Code implementation:

Based on the above analysis, the following code can be written:

<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             throw new RuntimeException("非法参数");<br>        }<br>        Node cur = null; // 当前node<br>        for (int i = 1; i             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>

​

3. Implementation of children dequeuing

1. Idea:

First find the node where the counting starts, and use cur to record it, for example, from the kth starting number, then cur should point to node k; then find the previous node of cur and record it with pre; after finding these two nodes, start counting (m-1) times from cur, that is, cur and pre move at the same time (m-1) times, at this time cur points to the node to be deleted; print the node to be deleted, and then move cur to the next node after the deleted node, that is, cur = cur.next, the next of pre points to the new cur, that is, pre.next = cur.

2. Code implementation:

<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  n){<br>            throw new IllegalArgumentException("非法参数");<br>        }<br>        // 先找到k节点，即开始报数的节点，用cur记录下来<br>        Node cur = first;<br>        for (int i = 1; i             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                 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>

When the incoming parameters are k=1, m=2, n=5, the result of executing this method is the same as the above analysis. , the output sequence is 2,4,1,5,3.

The above is the detailed content of How to solve Joseph problem in java. For more information, please follow other related articles on the PHP Chinese website!