循环检测算法

Question

假设我有一个函数 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 的答案，我设法想出了这个，这似乎有效：

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);
    }
}

Answer 1

如果函数是一个“黑匣子”，并且您有能力为任何单个 x 找到 f(x)（无论对实数有效还是仅对整数有效），但您不知道其他任何内容，则没有通用方法找到循环的起点和长度。例如，考虑函数

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

f(k) 看起来每 4 个整数重复一次，但当达到 k = 1000000 时，该模式就会停止。

---

如果函数的范围有限，并且您可以测试所有整数，则龟兔算法 (= Floyd 的循环查找算法）可以提供帮助。

不用迭代函数求值，而是计算 f(k0 + k) 和 f(k0 + 2*k) 直到它们匹配，此时可疑周期为 k，只需重复所有值即可验证循环是否继续。

您的问题似乎与 “我应该如何找到重复的单词序列？” 其中有很多答案。

Answer 2

对于你给出的 fn，因为它除以 4，所以长度是 4，并且由于没有添加任何值，所以 0 实际上是循环的开始，而不是 1。如果你确实使用图表实现它，你实际上可以观察到这一点已被指出。
由于这些是 fn 值，您可以使用链接列表来代替，并且对于 fn 返回的每个值，如果列表中尚不存在，则将其添加到列表中，否则您可以有一个循环。假设只有 1 个循环。