ジョセフリング問題を解決する 3 つの JavaScript メソッド

概要

ジョセフ・リング問題は、ジョセフ殺人問題または紛失ハンカチ問題としても知られ、古典的なアルゴリズムの問​​題です。問題の説明にはさまざまなバリエーションがありますが、問題を解決する基本的な考え方は同じです。この記事では、循環リンクリスト、順序付き配列、数学的再帰の 3 つの方法でジョセフ リング問題を解決します。

問題の説明

まず、ジョセフ・リング問題とは何かを見てみましょう。

ローマ軍がホタパテルを占領した後、39 人のユダヤ人がヨセフスとその友人とともに洞窟に隠れました。39 人のユダヤ人は、敵に捕まるよりは死んだほうがましだと考え、自殺する方法を決定しました。41 人が輪になって立ち、最初の人が数え始めました。3 人目が数えるたびに、その人は自殺しなければならず、全員が自殺するまで次の人が再び数え続けました。しかし、ヨセフスとその友人たちは従うことを望みませんでした。 1 人から始めて、k-2 人をスキップし (最初の人はスキップされているため)、k 番目の人を殺します。次に、k-1人をスキップしてk番目の人を殺します。このプロセスは循環的に続き、最終的に 1 人だけが残り、その人が生き続けることができます。問題は、 と が与えられた場合、処刑を回避するために最初にどこに立つべきかということです。

現在、ジョセフ・リング問題の説明は一般的に次のようになります。

部屋には N 人がいます。全員が輪になって座り、時計回りに数え始めます。M を数えた人がゲームから退出します。次にゲームから退出した人が再びカウントを開始し、M を報告した人が再び退出します。このサイクルは、ゲームに残っている人が 1 人だけになるまで続きます。最後の人の番号は何ですか?

循環リンクリスト

循環リンクリストの問題の解決は比較的簡単です。問題の説明をコードに変換するだけです。部屋にいる N 人の人々は長さ N のリンク リストを形成し、端から端まで接続されて循環リンク リストを形成します。リスト内の各項目の値は、各人の番号です。番号が M に達すると、項目 (x で示される) は削除されます。つまり、項目の前の項目の次が x ではなく x.next を指すようになります。リンク リストに残る項目が 1 つだけになるまで、この方法でリンク リストを走査します。

コードの実装を見てみましょう。

関数createList(num) {
    //リンクリストノードのデータ構造 function createNode(value) {
        戻る {
            値: 値、
            次： ''
        }
    }
    //ヘッドノードをリストします let head = createNode(1);
    ノードをヘッドにします。
    //ヘッドノードの後のノード間の関連付けを作成する for (let i = 2; i <= num; i++) {
        ノードを次に作成します。
        ノード = node.next;
    }
    //最後のノードはヘッドノードを指し、循環リンクリストを形成します。node.next = head;
    ヘッドを返す。
}
関数deleteListNode(num, nth) {
    //データ長 num の循環リンク リストを作成します。let node = createList(num);
    //リンクリストの長さが1より大きい場合は、次のラウンドに進みます while (num > 1) {
        (i = 1 とします; i <= nth - 1; i++) {
            (i == n番目 - 1)の場合{
                //i が nth-1 の場合、node.next は n 番目のノードになります。 node.next を削除します
                ノードの next 要素を次のノードに渡します。
                // リンクリストの長さ --
                数値--;
            }
            ノード = node.next;
        }
    }
    //最後に残ったノードの値は最後の人の番号です。node.value を返します。
}
//deleteListNode(m,n) を実行して最終結果を取得します

順序付き配列

順序付き配列を使用して、循環リンク リストをシミュレートします。配列の最初のトラバースと削除の後、残りの配列項目が新しい配列に形成されます。次に、新しい配列に対して新しいラウンドのトラバースと削除が実行され、このサイクルが配列の長さが 1 になるまで繰り返されます。

コードの実装を見てみましょう。

関数 jhonRing(num, nth) {
    arr = [] とします。
    // 順序付けられた配列を作成する for (let i = 1; i <= num; i++) {
        arr[i - 1] = i;
    }
    //配列の長さがnthより大きい場合、削除するデータをループせずに配列を見つけることができます while (arr.length >= nth) {
        newArr = [] とします。
        // 配列の末尾にある残りのデータを新しい配列の先頭に移動し、生成されたデータから新しい一連のトラバーサルを開始します。let times = arr.length - arr.length % nth;
        newArr = arr.slice(回数)
        arr.slice(0, times).map((item, index) => {
            //削除されたデータを除くすべてのデータを新しい配列に追加します。if ((index + 1) % nth !== 0) {
                newArr.push(アイテム)
            }
        })
        arr = 新しいArr;
    }
    //配列の長さがn番目より小さい場合、削除するデータを見つけるために配列をループで走査する必要があります。モジュロ演算により走査回数を減らすことができます while (arr.length > 1) {
        // 余りを取って、削除するデータのインデックスを取得します。let index = nth % arr.length - 1;
        // データの後半部分を削除し、前半部分と組み合わせて新しい配列を作成します。let newArr = arr.slice(index + 1).concat(arr.slice(0, index));
        arr = 新しいArr;
    }
}
//jhonRing(num, nth) を実行して最終結果を取得します

順序付き配列を使用してリンク リストをシミュレートする操作は、リンク リストの操作と似ているようで、時間の複雑さも同じようで、コードもリンク リストほど簡潔ではありませんが、それでもこの方法を提案するのはなぜでしょうか。この方法の利点は、M>>N の場合、順序付けされたリンク リストが余りを取ることで配列を走査する回数を効果的に削減できることです。 N を 3、M を 100 とすると、リンク リストは 100/3+1 回走査する必要がありますが、順序付き配列は、モジュロ演算 100/3-1=0 の結果に基づいて、削除するデータのインデックスを 0 として直接取得します。

数学的再帰

数学の問題でジョセフ環問題を解くとき、ルールを要約する効果的な方法を見つけられないことは非常によくあります。以下では、ルールを要約するときに取った回り道を説明するために、M = 3 を例として使用します。 (無効なアイデアはスキップして、以下の有効なアイデアを読むことができます)

より少ないデータ量で複数の結果を比較する（❌）

N=1のとき、f(1,3)=1;
N=2のとき、f(2,3)=2;
N=3のとき、f(3,3)=2;
N=4のとき、f(4,3)=1;
N=5のとき、f(5,3)=4;
N=6のとき、f(6,3)=1;
N=7のとき、f(7,3)=4;
N=8のとき、f(8,3)=7;
N=9のとき、f(9,3)=1;
N=10のとき、f(10,3)=4;

例を通して、最終結果が必ずしも特定の数字の範囲内にあるわけではないことがわかります。1、2、4に加えて、7も現れ、その後の結果も同様の状況になる可能性があります。つまり、最終結果が必ずしも特定の数字に限定されるわけではありません。 N が M の倍数である場合、f(3,3)、f(6,3)、f(9,3) などは同じ結果を生成しません。これは、最終結果と 3 の倍数の間に特別な関係がないことを示しています。そのため、データ量が少ない場合に結果を蓄積して比較することでパターンを見つけることは適切ではありません。

前回の除去データとの関係を比較する（❌）

//1からNまでのN人を数える
1、2、3、4......N-2、N-1、N
//最初の除去数は M または M%N であり、M%N として要約され、K として記録されます。 2回目の除去の順序は次のようになります
K+1、K+2、.......N、1、2......K-1
//2番目の消去数はK+M%(N-1) || M%(N-1)-(NK-1)
この規則によれば、N-(K+1)>M%(N-1)のとき、f(n)=f(n-1)+M%(N-(n-1))
N-(K+1)<M%(N-1)のとき、f(n)=M%(N-(n-1))-(Nf(n-1)-1)

このルールに従って計算すると、2 回目の走査の前に得られた結果は正しいが、2 回目の走査後の結果は間違っていることがわかります。根本的な理由は、2 回目のラウンドに入った後のデータが連続しなくなることです。1 回目のトラバース中に削除されたデータは 2 回目のトラバースの結果に影響するため、このソリューションは適切ではありません。

問題を上から下まで分析し、下から上まで解決する (✅)

再帰的思考を使用してジョセフ リング問題を分析します。分析の例として、N=10、M=3 を取り上げます。

// 10 人を 0 から番号付けします (1 から番号付けできない理由は後で説明します)
0、1、2、3、4、5、6、7、8、9
//最後に列を離れた人の番号を f(10,3) として記録します。
//10人が番号を振られた後、最初の人が列を離れ、新しい列と番号を取得します
3、4、5、6、7、8、9、0、1
//新しいキューの番号を連続させるために、新しいキューをAとして記録し、次のように記述します。
3、4、5、6、7、8、9、10%10、11%10
//9人の通常のキューがBとして記録され、0、1、2、3、4、5、6、7、8を書き込んだ最終結果がf(9,3)として記録される場合、新しいキューAの結果は(f(9,3)+3)%10と表すことができます。
// 9 人待ち行列 A は、10 人待ち行列から 1 人を削除して得られます。次に、N=9、M=3、初期番号 3 のルールに従って 9 人待ち行列でゲームをプレイした結果は、N=10、M=3、初期番号 0 の待ち行列から最後に出た人と同じである必要があります。
//したがって、10人の列から最後に出た人の数と9人の列Aから出た人の数の間には関係があります。f(10,3)=(f(9,3)+3)%10

上記に基づいて、f(N,M)=(f(N-1,M)+M)%Nと結論付けることができます。最終的な番号付け結果は f(N,M)+1 です。
なぜ番号は 1 から始まらないのですか?剰余演算の戻り結果は 0 から始まるためです。

関数Josephus(num,nth){
    if(数値==1){
        0を返します。
    }それ以外{
        (Josephus(num-1,nth)+nth)%num を返す
    }
}
//Josephus(N,M)+1が最終的な数です

再帰関数を最適化する

関数JosephusR(num,nth){
    値を 0 にします。
    for(let i=1;i<=num;i++){
        //ここにはiの係数があります。上記の再帰では、numも徐々に小さくなっているので、ここではnumの代わりにiを使用します。
        値=(値+n番目)%i;
    }
    戻り値+1;
}
//JosephusR(N,M)は最終的な数値です

要約する

数学的な再帰最適化により、ジョセフ リング問題の時間計算量は元の O(mn) から O(n) に削減されます。循環リンクリストを通じて問題を解決することは確かに最も速くて簡単な方法ですが、この数学的な再帰的方法は、このようなアルゴリズムの問​​題を解決するのにさらに価値があります。

これで、Joseph リング問題を解決するための 3 つの JavaScript メソッドに関する記事は終了です。JavaScript の Joseph リングに関するその他のコンテンツについては、123WORDPRESS.COM の以前の記事を検索するか、以下の関連記事を引き続き参照してください。今後とも 123WORDPRESS.COM をよろしくお願いいたします。