Cycle Finding: a self-mapped function in a finite set

尋找有限集自身映射函數的循環週期：給定一個有限集中的元素做為起點，不斷映射，必會循環，找出此循環的起始點元素、此循環的最小週期、進入此循環前的映射次數。

應用

1. 檢查一條singly linked list是否因接錯而造成無限循環，並找出接錯位置。
2. 檢查兩條獨立的singly linked list是否因接錯而牽連作伙，並找出接錯位置。
3. 一條陣列連續放著n+1個數，數值皆介於1到n，
   其中恰有兩數相同，請找出此數及此數位置。
4. 檢查自動機是否有無窮迴圈。
5. 兩整數相除得到之無限小數，請找出其循環節。

一個簡單的演算法（Memoization）

開一個陣列，記錄每個元素是否拜訪過，如果又遇到已拜訪過的元素，那就表示有循環了。

int step[1000]; // 到達各個元素，所需的映射次數 void cycle_finding(int x) // x是給定的起點 { memset(step, -1, sizeof(step)); // 初始化為-1 for (int i=0; ; ++i) { step[x] = i; if (step[x = f(x)] != -1) { cout << "循環的起始點元素是" << x; cout << "循環的最小週期是" << i - step[x]; cout << "進入循環前的映射次數是" << step[x]; return; } } }

這個方法簡單又有效率，不過缺點就是記憶體用很兇。時間複雜度O(N)，空間複雜度O(N)，N為集合大小。

UVa 202 275 517

龜兔賽跑演算法

void TortoiseHare(int x) { int s = 0, p = 1; // i是龜，至起點下一步，j是兔，至起點下兩步。 int i = f(x), j = f(f(x)); // 龜一倍速，兔兩倍速。嘗試隨便找個循環。 while (i != j) i = f(i), j = f(f(j)); // 龜至起點，兔至原龜處。 j = i; i = x; // 龜兔皆一倍速。開始找循環起點。 while (i != j) i = f(i), j = f(j), s++; // 兔至龜下一步。 j = f(i); // 龜不動，兔一倍速。開始找最小週期。 while (i != j) j = f(j), p++; cout << "循環的起始點元素是" << i; cout << "循環的最小週期是" << p; cout << "進入循環前的映射次數是" << s; }

這個演算法的好處是空間很省，僅僅以龜兔兩個變數就能找出循環。時間複雜度是O(s+p)，s為進入此循環前的映射次數，p為循環的最小週期。空間複雜度為O(1)。

UVa 350

Brent's Algorithm