Javaでジョセフ問題を解く方法

1. ジョセフの質問の紹介

1. ジョセフの質問の原題:

n 人の子供たちが手をつないで輪を作ります。 k 番の人 (1

2. 問題分析:

問題の説明によると、一方向循環リンク リストを使用してシミュレーションすることは容易に考えられます。まず、n 個のノードからなる一方向循環連結リストを作成し、ノード K が 1 からカウントを開始します。m がカウントされると、該当するノードが連結リストから削除され、次に削除されたノードから 1 からカウントが開始されます。すべてのノードが削除されるまで。

一方通行循環リンクリスト

番号1の人から番号が報告されるたびに、番号2の人がリストアップされるとします。 . $n= 5$ の個人がいる場合、$k=1,m=2$ になります。最終的な結果は 2、4、1、5、3 になるはずです。

2. 一方向循環リンクリストの構築

1. 構築のアイデア:

• まず最初のノードを作成し、最初のポインタでそのノードをポイントし、次のポインタでそれ自体をポイントします。

最初のノード

• 次に、次のように 2 番目のノードを作成し、最初のノードの次のポインタを 2 番目のノードにポイントし、2 番目のノードの次のポインタを最初のノードにポイントします。図に示すように:

# 2 番目のノード

# など、一方向の循環リンク リストを構築できます。 。トラバース中に、ノードの次が最初と等しい場合、トラバースが完了したことを意味します。

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             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. 子のデキューの実装

1. アイデア:

まず、カウントが開始されるノードを見つけて、cur を使用してそれを記録します。 k 番目の開始番号から、cur はノード k を指す必要があります。次に、cur の前のノードを見つけて、pre で記録します。これら 2 つのノードを見つけた後、cur から (m-1) 回のカウントを開始します。つまり、cur と pre同時に (m-1) 回移動し、この時点で cur は削除されるノードを指します。削除されるノードを出力し、次に cur を削除されたノードの次のノード、つまり

に移動します。 cur = cur.next、pre の next は新しい cur、つまり pre.next = cur を指します。

2. コード実装:

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

入力パラメータが k=1、m=2、n=5 の場合、このメソッドの実行結果は同じです上記の解析のように、出力シーケンスは 2,4,1,5,3 になります。

以上がJavaでジョセフ問題を解く方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。