Comment résoudre le problème de Joseph en Java

1. Introduction au problème de Joseph

1. Titre original du problème de Joseph :

n enfants forment un cercle main dans la main, et la personne numérotée k (1

2. Analyse du problème :

Selon la description du problème, il est facile de penser à utiliser une liste chaînée circulaire à sens unique pour le simuler. Tout d'abord, une liste chaînée circulaire unidirectionnelle avec n nœuds est formée, puis le nœud K commence à compter à partir de 1. Lorsque m est compté, le nœud correspondant est supprimé de la liste chaînée, puis le comptage commence à partir de 1 à partir du prochain nœud supprimé. jusqu'à ce que tous les nœuds soient supprimés.

Liste chaînée circulaire à sens unique

Supposons qu'à partir de la personne numérotée 1, la personne déclarant 2 à chaque fois sort de la file d'attente. S'il y a $n=5$ personnes, alors $k=1, m=2$ . Le résultat final devrait alors être : 2, 4, 1, 5, 3.

2. Construction d'une liste chaînée circulaire unidirectionnelle

1. Idée de construction :

• Créez d'abord le premier nœud, pointez-le avec le premier pointeur et ses points suivants vers lui-même, comme indiqué ci-dessous :

Le premier nœud

• Ensuite, créez le deuxième nœud, pointez le pointeur suivant du premier nœud vers le deuxième nœud, et pointez le pointeur suivant du deuxième nœud vers le premier nœud, comme le montre la figure ci-dessous :

Le deuxième nœud

et ainsi de suite, vous pouvez créer une liste chaînée circulaire à sens unique. Lors du parcours, lorsque le prochain du nœud est égal au premier, cela signifie que le parcours est terminé.

2. Implémentation du code :

Sur la base de l'analyse ci-dessus, le code suivant peut être écrit :

<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. Implémentation du retrait des files d'attente des enfants

1. Idée :

Trouvez d'abord le nœud qui commence à compter et utilisez cur pour l'enregistrer. Par exemple, à partir du kème nœud, cur doit pointer vers le kème nœud ; puis recherchez le nœud précédent de cur et enregistrez-le avec pre ; après avoir trouvé ces deux nœuds, commencez à compter (m-1) fois à partir de cur, c'est-à-dire les fois cur et pre move (m-1) en même temps. cette fois, cur pointe vers le point souhaité. Le nœud en cours de suppression ; imprimez le nœud à supprimer, puis déplacez cur vers le nœud suivant après le nœud supprimé, qui est cur = cur.next，pre的next指向新的cur，即pre.next = cur.

2. Implémentation du code :

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

Lorsque les paramètres d'entrée sont k=1, m=2, n=5, le résultat de l'exécution de cette méthode est le même que l'analyse ci-dessus et la séquence de sortie est 2, 4,1,5,3.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!