Java プログラミング スキル - データ構造とアルゴリズム「循環リンク リストとジョセフ問題」

[[386837]]

ジョセフ問題

1、2、...n と番号が付けられた n 人が輪になって座り、番号 k (1<<k<<n) の人が数え始め、m まで数えた人が列から離れ、次の人が再び 1 から数え始め、m まで数えた人も列から離れ、全員が列から離れるまでこれを繰り返し、終了番号のシーケンスを生成することに同意したとします。

ジョセフ問題を解く循環リンクリスト

まず、n 個のノードを持つ一方向の循環リンク リストが構築され、次に k ノード カウンターが 1 からカウントを開始します。m に達すると、対応するノードがリンク リストから削除され、削除されたノードの次のノードからカウントが再び 1 から開始され、最後のノードがリンク リストから削除されるまでカウントが続きます。

一方向循環リンクリストを構築する

1. 最初に最初のノードを作成し、最初にそのノードを指すようにして、リングを形成します。

2. 新しいノードが作成されるたびに、それを循環リンク リストに追加します。

コード例

パッケージ com.structures.linkedlist; 
 
パブリッククラス Josephu {
公共 静的void main(String[] args) {
        CircleSingleLinkedList を新しい CircleSingleLinkedList() に追加します。
        円シングルリンクリスト.addBoy(5);
        シングルリンクリストの男の子を表示します。
        円シングルリンクリスト.countBoy(1,2,5); 
 
        /*
        子供の人数: 1
        子供の人数: 2
        子供の人数: 3
        子供の人数: 4
        子供の番号: 5
        チャイルド2が話題に
        サークルから外れた子供4
        サークルから外れた子供1
        サークルから外れた子供5
        輪の中に最後に残った子供は3番です
        */
    }
 } 
 
 //循環的な一方向リンクリストを作成する
クラス CircleSingleLinkedList {
    //最初のノードを作成します。現在は番号はありません
    プライベートBoy first = new Boy(-1); 
 
    //子ノードを追加して循環リンクリストを構築します
パブリックvoid addBoy( int nums) {
        （数値<1）の場合{
            System.out.println ( "numsの値が正しくありません" );
戻る;
        }
        男の子 curBoy = null ;
        //循環リンクリストを作成するための forループ
( int i = 1; i <= 数値; i++) {
            男の子 男の子 = 新しい男の子(i);
            //最初の子の場合
            (i == 1) の場合 {
最初= 男の子;
最初.setNext(最初);
                curBoy = first ; //curBoyを最初のものを指すようにする
            }それ以外{
                curBoy.setNext(男の子);
                boy.setNext(最初);
                curBoy = 男の子;
            }
        }
    } 
 
    //現在の循環リンクリストを走査する
パブリックvoid showBoys() {
        if ( first .getNext() == null ) {
            System.out.println ( "子が存在しません~~" );
戻る;
        }
        男の子の臨時雇用者=最初;
        （真）の間{
            System.out.println ( "子供の番号:" + temp.getNo ());
            if ( temp .getNext() == first ) {
                壊す;
            }
 temp = temp.getNext ();
        }
    } 
 
    /**
     * ユーザーの入力に基づいて、サークルから出る子供の順番を計算します
     *
     * @param startNoはカウントを開始する子の数を示します
     * @param countNumは回数を示します
     * @param numsはサークル内の子の数を示します
     */
パブリックvoid countBoy( int startNo, int countNum, int nums) {
        //まずデータをチェックする
        if ( first == null || startNo < 1 || startNo > nums) {
            System.out.println ( "パラメータ入力が正しくありません。再入力してください" );
戻る;
        }
        // 子が円から抜け出すのを助ける補助ポインタを作成する
        ボーイヘルパー =最初;
        //ヘルパーが循環リンクリストの最後のノードを指すようにします
        helper.getNext() がfirstではない場合、
            ヘルパー = helper.getNext();
        }
        // 報告する前に、ヘルパーとファーストをk-1 回移動させて、ファーストが開始ノードに位置し、ヘルパーがファーストに追従するようにします。  
 ( int i = 0; i < 開始番号 - 1; i++) {
最初=最初.getNext();
            ヘルパー = helper.getNext();
        }
        //報告するときは、最初のポインタとヘルパーポインタを同時に移動させ、その後円から出るようにします
        （真）の間{
            //円内にノードが1つしかない場合
            if (ヘルパー == first ) {
                壊す;
            }
            //最初のポインタとヘルパーポインタを同時に countNum - 1 回移動します
( int i = 0; i < countNum - 1; i++) {
最初=最初.getNext();
                ヘルパー = helper.getNext();
            }
            //この時点で、最初のノードは、子供がサークルから出たいノードです
            System.out.printf ( "子%dがサークル外です\n" 、 first.getNo ());
最初=最初.getNext();
            helper.setNext(最初);
        }
        System.out.printf ( "円内に残っている最後の子の番号は%dです\n" 、 first.getNo ());
    }
 } 
 
 //ノードを表すBoyクラスを作成する
クラスBoy {
    プライベートint  いいえ; // 番号
    private Boy next ;//次のノードを指します。デフォルトはnullです  
 
パブリックボーイ( int  いいえ） {
        this.no =いいえ;
    } 
 
公共 整数getNo() {
戻る いいえ;
    } 
 
パブリックボイドsetNo( int  いいえ） {
        this.no =いいえ;
    } 
 
パブリックボーイgetNext() {
戻る 次;
    } 
 
パブリックvoid setNext(Boy next ) {
        this.next =次へ;
    }
 }

【編集者のおすすめ】

1. いいですね、上司からシンプルなワークフロー エンジンを開発するように言われました...
2. Windows 10 は世界を揺るがす変化をもたらします!今年最初のアップデートが来ました
3. 2021年に注目すべき6つのサイバーセキュリティトレンド
4. 近年の Windows 10 における最大の改善点! Windows 10 21H2 新機能プレビュー
5. Xiao Aiは本当にPC版をリリースしたのか？コンピュータ版のXiao Aiを体験してみましょう