問題タブ [floyd-cycle-finding]

私はFloyd's Cycle Findingアルゴリズムを試していましたが、疑問がありました。

高速ポインターを 2 だけ増やしますか?

これに最適な他の値はありますか?

次の Haskell コードを Agda に変換したい:

これにより、リストを効率的に 2 つに分割できます。

そこで、このコードを Agda に変換しようとしました。

唯一の問題は、Agda が のケースが見つからないと不平を言うことですfloyd [] (y :: ys)。ただし、このケースは決して発生してはなりません。このケースが決して起こらないことをアグダにどのように証明できますか?

このアルゴリズムがどのように機能するかの視覚的な例を次に示します。

別の例を次に示します。

ウサギ ( の 2 番目の引数floyd) がリストの最後に到達すると、カメ ( の最初の引数floyd) がリストの中央に到達します。したがって、2 つのポインター (2 番目のポインターは最初のポインターの 2 倍の速度で移動する) を使用することで、リストを効率的に 2 つに分割できます。

あるインタビューで、リンク リスト内のループ ノードを検出し、ループ内のノードの数をカウントするように依頼されました。flyod アルゴリズムを知らなかったので、独自のアプローチを見つけようとしました。

このシナリオでは、2 つのノードのアドレスが同じノード (ループ ノード) を指します。

例えば。

1-->2-->4-->5-->7-->3-->4

ここで 2->next と 3->next は同じで、これは 4 のアドレスです。これは、リンクされたリストにループがあり、4 がループ ノードであることを意味します。また、4 から 4 にトラバースすると、ループ内のノードの数が得られます。

このアプローチを進める方法はありますか????

今、スタック オーバーフローの回答を読んだことを覚えています。速いランナーと遅いランナーは常にリンクされたリスト ループで衝突し、速度の 2 の差は任意であるということです。

速いランナーと遅いランナーの差が 2 の場合、反例を思いつくことができませんでしたが、ランナーの差が 3 の場合、次の例ではランナーを衝突させることができないようです。 .

リンクされたリスト ループ内に、低速と高速の 2 つのランナーがあるとします。ループには 8 つのノードがあり、1 番目のノードは 0、2 番目のノードは 1 というようにラベル付けされています。Slow はインデックス 0 で Fast は 1 で、衝突することはありません。

この例と、ループ内のランナーが常に衝突するというステートメントは、速いランナーが遅いランナーを飛び越え続けることができるため、矛盾しています。

私はまだアルゴリズムのコースを受講していないので、何が間違っているのかをできるだけ簡単に説明してください。