So lösen Sie das Joseph-Problem in Java

1. Einführung in Josephs Frage

1. Originaltitel von Josephs Frage:

n Kinder halten sich an den Händen und bilden einen Kreis. Die Person mit der Nummer k (1

2. Problemanalyse:

Nach der Beschreibung des Problems ist es einfach, sich die Verwendung eines einseitig verknüpften Rundschreibens vorzustellen Liste, um es zu simulieren. Zuerst wird eine einseitig zirkulär verknüpfte Liste mit n Knoten gebildet, und dann beginnt Knoten K mit der Zählung bei 1. Wenn m gezählt wird, wird der entsprechende Knoten aus der verknüpften Liste gelöscht, und dann beginnt die Zählung bei 1 ab dem nächsten gelöschten Knoten bis alle Knoten gelöscht sind. Nr. Person 2 kommt aus der Spalte, wenn es $n=5$ Personen gibt, dann $k=1,m=2$. Dann sollte das Endergebnis lauten: 2, 4, 1, 5, 3.

2. Konstruktion einer einseitig kreisförmigen verknüpften Liste

1. Konstruktionsideen: #🎜🎜 ## 🎜🎜#

Erstellen Sie zuerst den ersten Knoten, zeigen Sie mit dem ersten Zeiger darauf und sein nächster zeigt auf sich selbst, wie unten gezeigt:

# 🎜🎜# Der erste Knoten

• Dann erstellen Sie den zweiten Knoten und fügen die ersten Knoten hinzu Der nächste Zeiger zeigt auf den zweiten Knoten und gleichzeitig zeigt der nächste Zeiger des zweiten Knotens auf den ersten Knoten, wie in der folgenden Abbildung dargestellt:

#🎜🎜 # #🎜 🎜#Zweiter Knoten

Und so weiter können Sie eine einseitig zirkulär verknüpfte Liste erstellen. Wenn beim Durchlaufen der nächste Knoten gleich dem ersten ist, bedeutet dies, dass die Durchquerung abgeschlossen ist.

• 2. Code-Implementierung:

Basierend auf der obigen Analyse kann der folgende Code geschrieben werden:

rrree ​ 3. Implementierung des Entfernens von Kindern aus der Warteschlange

1. Idee:

Suchen Sie zuerst den Knoten, an dem die Zählung beginnt, verwenden Sie cur Record Wenn Sie beispielsweise vom k-ten Knoten ausgehen, sollte cur auf den Knoten k zeigen. Suchen Sie dann den vorherigen Knoten von cur und zeichnen Sie ihn mit pre auf. Beginnen Sie mit dem Zählen (m-1) von cur , das heißt, cur und pre move (m-1) gleichzeitig. Zu diesem Zeitpunkt zeigt cur auf den zu löschenden Knoten und verschiebt dann cur zum nächsten gelöschten Knoten Knoten, also #🎜🎜 #.

2. Code-Implementierung:

<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>

Wenn die eingehenden Parameter k=1, m=2, n=5 sind, führen Sie diese Methode aus Das Ergebnis ist das gleiche wie bei der obigen Analyse und die Ausgabesequenz ist 2,4,1,5,3.

Das obige ist der detaillierte Inhalt vonSo lösen Sie das Joseph-Problem in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!