Bagaimana untuk menyelesaikan masalah Joseph dalam java

1 Pengenalan kepada Soalan Joseph

1. orang bernombor k (1

2. Analisis masalah:

Menurut huraian masalah, mudah untuk difikirkan menggunakan senarai pautan pekeliling sehala untuk mensimulasikannya. Mula-mula bentuk senarai terpaut bulat sehala dengan n nod, dan kemudian kira nod K bermula dari 1. Apabila m dikira, nod yang sepadan dipadamkan daripada senarai terpaut, dan kemudian pengiraan bermula dari 1 dari nod dipadam seterusnya sehingga semua Nod dipadamkan.

Senarai pautan pekeliling sehala

2. Pembinaan senarai terpaut pekeliling sehala

1 >

Mula-mula buat nod pertama, tuding kepadanya dengan penuding pertama, dan seterusnya menghala pada dirinya sendiri, seperti yang ditunjukkan di bawah:

• Nod pertama

Nod kedua

dan seterusnya, anda boleh membina senarai terpaut bulatan sehala . Apabila melintasi, apabila nod seterusnya adalah sama dengan yang pertama, ini bermakna bahawa traversal telah selesai.

• 2. Pelaksanaan kod:

Berdasarkan analisis di atas, kod berikut boleh ditulis:

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

Salin selepas log masuk

, 3. Pelaksanaan dequeuing kanak-kanak

1 Idea:

Mula-mula cari nod tempat pengiraan bermula, dan gunakan cur untuk merekodkannya, contohnya, dari nombor permulaan k, maka cur harus menunjuk ke nod k, kemudian mencari nod sebelumnya cur dan merekodkannya dengan pra selepas mencari dua nod ini, mula mengira (m-1) kali dari cur, iaitu, cur dan pra bergerak pada masa yang sama (m-1) kali, pada masa ini cur menghala ke nod yang akan dipadamkan; , dan pra seterusnya menghala ke lekuk baharu, iaitu .

2. Pelaksanaan kod:

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

Salin selepas log masuk

Apabila parameter input ialah k=1, m=2, n=5, hasil daripada melaksanakan kaedah ini adalah sama seperti analisis di atas, jujukan keluaran ialah 2,4,1,5,3.

Atas ialah kandungan terperinci Bagaimana untuk menyelesaikan masalah Joseph dalam java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!