フロイドのサイクル発見アルゴリズムによると、カメとウサギが出会うポイントは、リンク リストの循環的な性質を説明しています。
サイクルの開始ノードを見つけるために、亀のポインターをリストの先頭に初期化し、ウサギと亀のポインターを 1 単位ずつインクリメントし始めます。それらが出会うポイントは、サイクルの開始ノードを示します。
特定の状況でどのように機能するか教えてください。
リンク リストは次のように流れます。
1->2->3->4->5->6->7->8->3
質問する
9640 次
5 に答える
15
どれどれ。
うさぎと亀を1に配置し、それらを走らせます。うさぎは亀の2倍の速さです。
0番目のステップでは、両方とも1になります。最初のステップでは、亀が2に移動し、うさぎが3に移動します。
1 1
2 3
3 5
4 7
5 3
6 5
7 7
それで、ウサギとカメは7時に会います。
亀を最初に置き、同じ速度で再び走らせます。
1 7
2 8
3 3
したがって、彼らは確かにサイクルの最初の要素で会いました。
そして、それは与えられた状況でそれがどのように機能するかです。
于 2012-06-04T14:06:10.630 に答える
14
わかりました、シンプルにしましょう。
A と B の 2 つのランナーがあるとします。A は各ステップで 1 ノードずつ前進し、B は 2 ノードずつ前進します。
それが巡回リストであれば、最終的にはお互いに出会うでしょう。
その時
A がこれまでに移動した距離がmであるとすると、B の場合は2m
また、
m = a + b
2m = a + b + k * lengthOfLoop
Bの場合、Aが移動した距離に加えてk（気にしない数）ループを移動したためです。aはループ ポイントの前の距離、bはループ ポイントの後に移動した距離 A です。
次に、（いくつかの数学の後）
a = k * lengthOfLoop - b
ここで、B をリストの先頭に戻し、速度を 1 に下げます。
B の場合a、ループ ポイントから離れたノードです。A の場合、彼はすでにループ ポイントをbで通過しており、上記の式によると、彼はaループ ポイントから離れたノードでもあります。
そのため、aさらにステップを進めると、A と B がループ ポイントで再び出会います。
于 2012-06-04T18:31:14.560 に答える
5
わかりました、直接的な答え: あなたが与えた [編集: リンクされたリストであり、シーケンスではありません] にはサイクルが含まれていません。これが何が起こるかです。アルゴリズムの最初の部分では、亀と髪はそれぞれ x1=2 と x2=3 から始まります。その後、x2=3 と x4=5 に進みます。次に x3=4 と x6=7 です。次に、x4=5 と x8=3 にします。その後、x8 を超えるものは何もないため、うさぎは前進を停止し、アルゴリズムはサイクルが見つからなかったと判断します。
以下に、サイクルを含む別のシーケンスに適用されたフロイドのサイクル検出を示す小さな GIF をまとめました。
于 2012-06-04T14:04:24.637 に答える
0
fast pointer(一度に 2 つのノードを移動する) と(一度に 1 つのノードを移動する) の 2つのポインターを考えてみましょうslow pointer。どちらも連結リストの先頭から移動を開始します。
しばらくすると、は先頭からkノードslow pointer移動するループに入ります。その時点で、リストの先頭から2kノード移動していることになります。したがって、これは、 がからk番目のノードを指すことを意味します。fast pointerfast pointerslow pointer
今、彼らはループのどこかで出会うまで動き続けます。それらが出会うとき、それらは、ループの開始時とまったく同じ数のノードだけループの開始fast pointerからslow pointer離れます(つまり、ループの開始ノードからノードとの距離fast pointer はslow pointerk個の要素(またはノード). また、kは、リンクされたリストの先頭からループの開始ノードまでの距離でもあります。
そのため、頭からポインタを移動し始め、 と の交点からポインタを 1 つ移動しfast pointerますslow pointer。ループの開始ノードの距離はこれらの両方のポイントからkであるため、それらはループの開始ノードでk番目のステップで出会います。
于 2017-01-05T19:39:29.097 に答える