blog IV | 循环节，龟兔赛跑算法

· · 个人记录

通常我们讨论函数的“循环节”时，往往指的是迭代函数（即连续地应用 f，比如构造序列

x_0,x_1=f(x_0),x_2=f(x_1),\dots

）时，这个序列是否最终进入循环，以及循环部分的长度是多少。如果函数的定义域是有限集（或者你只关注迭代轨迹），那么必然会出现循环。

一个常用且高效的方法是弗洛伊德判圈算法（Floyd’s Cycle Detection，也叫龟兔赛跑算法）。它的基本思路如下：

  1. 检测循环
    定义两个指针：

    • 慢指针（tortoise） 每次移动一步：x_{k+1} = f(x_k)。
    • 快指针（hare） 每次移动两步：x_{k+1} = f(f(x_k))。

    从某个初始值 x_0 开始，同时移动两个指针，直到两者相遇为止。相遇时可以证明序列已经进入了循环状态。

  2. 求循环长度 \lambda
    当慢指针和快指针第一次相遇后，固定其中一个指针，再沿着序列走一圈（即不断调用 f），直到再次回到相遇点。计数所走的步数，这个数即为循环长度。

  3. 求循环前的非循环部分长度 \mu
    将其中一个指针重置到起始点 x_0，然后两个指针都每次走一步，直到它们再次相遇。它们相遇的位置就是循环开始的位置，移动的步数就是 \mu，即序列进入循环前的步数。

这种方法的时间复杂度是 O(\mu+\lambda)，而且只需要常数级别的额外空间，非常适合用于大规模问题。

此外，还有另一种算法叫 Brent 算法，它的时间复杂度与弗洛伊德算法相当，有时在函数调用代价较高时能减少函数调用次数。

总结来说：

这种方法既简单又高效，是判断函数迭代是否有循环及其周期长度的常用快速方法。

下面是一份使用 C++ 实现弗洛伊德判圈算法（龟兔赛跑算法）的示例代码，该代码演示了如何判断一个函数迭代序列是否存在循环，并求出循环前的非循环部分长度（\mu）以及循环长度（\lambda）。

下面代码中，我们定义了一个示例函数

f(x) = (x \times x + 1) \mod 255

并从初始值 x_0=2 开始进行迭代。

#include <iostream>
using namespace std;

// 示例函数 f: f(x) = (x*x + 1) mod 255
int f(int x) {
    return (x * x + 1) % 255;
}

int main(){
    // 初始值
    int x0 = 2;

    // Phase 1: 使用快慢指针查找循环
    int tortoise = f(x0);      // 慢指针走一步
    int hare = f(f(x0));       // 快指针走两步
    while(tortoise != hare) {
        tortoise = f(tortoise);
        hare = f(f(hare));
    }

    // Phase 2: 查找循环起始位置 mu
    int mu = 0;
    tortoise = x0;
    while(tortoise != hare) {
        tortoise = f(tortoise);
        hare = f(hare);
        mu++;
    }

    // Phase 3: 求循环长度 lambda
    int lambda = 1;
    hare = f(tortoise);
    while(tortoise != hare) {
        hare = f(hare);
        lambda++;
    }

    cout << "循环前的非循环部分长度 mu = " << mu << "\n";
    cout << "循环长度 lambda = " << lambda << "\n";

    return 0;
}

代码说明

  1. 循环检测（Phase 1）：

    • 我们定义两个指针：tortoise 每次走一步，hare 每次走两步。
    • 当两者相遇时，证明迭代序列中存在循环。

  2. 求非循环部分长度 \mu（Phase 2）：

    • 将其中一个指针重置到起始值，然后两个指针同步前进，当它们再次相遇时，相遇位置即为循环开始的位置，前进的步数就是 \mu。

  3. 求循环长度 \lambda（Phase 3）：

    • 从相遇点出发，固定该点，再沿着序列走一圈，直到再次回到该点，所走的步数即为 \lambda。

这种方法时间复杂度为 O(\mu+\lambda)，且只使用常数级别的额外空间，是判断函数迭代是否存在循环以及求循环长度的高效方法。

以上内容由 GPT-o3-mini 生成