0

関数 f があるとします。

f(0) = 0
f(i) = (i - 1) % 4

f(0..12):

0 0 1 2 3 0 1 2 3 0 1 2 3

それぞれ 1 と 4 であるサイクルの開始とサイクルの長さを見つけたいと思います。カメとウサギのアルゴリズムは反復関数で機能しますが、反復関数はありません。反復されない関数で動作する他のアルゴリズムはありますか、またはこのために亀とウサギのアルゴリズムを変更できますか?

編集：

Jason S's answer を使用して、私はこれを思い付くことができました。これはうまくいっているようです:

public static Tuple<int, int> ModifiedTortoiseHare(Func<int, int> f, int x0 = 0, int checks = 4)
{
    for (; ; x0++)
    {
        int lam = 0, tortoise, hare;

        do
        {
            lam++;
            tortoise = f(x0 + lam);
            hare = f(x0 + 2 * lam);
        } while (tortoise != hare);

        int mu = -1;

        do
        {
            mu++;
            tortoise = f(x0 + mu);
            hare = f(x0 + mu + lam);
        } while (tortoise != hare);

        if (mu != 0) continue;

        bool correct = true;
        int lamCheckMax = lam * checks;

        for (int x = 0; x < lamCheckMax; x++)
        {
            if (f(x0 + x + mu) != f(x0 + x + mu + lam))
            {
                correct = false;
                if (mu != 0) x0 += mu - 1;
                break;
            }
        }

        if (correct) return Tuple.Create(x0 + mu, lam);
    }
}
4

2 に答える 2

7

関数が「ブラック ボックス」であり、任意の個々の x に対して f(x) を見つける機能 (実数または整数のみに有効かどうか) を持っているが、他に何も知らない場合、一般的な方法はありません。サイクルの開始と長さを見つける。たとえば、関数を考えてみましょう

f(k) = (k - 1) % 4 + g(k)
g(k) = max(0, k-1000000)

f(k) は 4 つの整数ごとに繰り返されるように見えますが、k = 1000000 になるとパターンが停止します。

関数に有限の範囲があり、すべての整数をテストできる場合は、カメ/ウサギのアルゴリズム (=フロイドのサイクル検出アルゴリズム)を使用できます。

関数の評価を繰り返す代わりに、一致するまで f(k0 + k) と f(k0 + 2*k) を計算します。一致する時点で疑わしい期間が k になり、サイクルが継続していることを確認するためにすべての値を繰り返す必要があります。 .

あなたの質問は、 「繰り返される単語シーケンスを見つけるにはどうすればよいですか?」と同等の問題のようです。いくつかの答えがあります。

于 2011-06-18T16:43:36.933 に答える
0

4 で除算してから指定した fn の長さは 4 であり、値が追加されていないため、実際には 0 がサイクルの開始点であり、1 ではありません。グラフを使用して実装すると、実際にこれを観察できます。と指摘されています。これらは fn 値であるため、代わりにリンクされたリストを使用できます。また、fn が返すすべての値で、まだ存在しない場合はリストに追加します。そうでない場合は、サイクルを 1 つだけ持つことができます。

于 2011-06-18T16:48:08.083 に答える