Function

「函數」這個翻譯非常不直覺。函數其實是「對應」與「變換」兩種概念的結合。

對應，就是一個東西對應一個東西。變換，就是從一個東西，按照對應關係，變成另一個東西。

函數的規定

輸入都是同一類的東西。輸出都是同一類的東西。輸入與輸出可以同類、也可以不同類。輸入數量和輸出數量沒有任何限制。

相異輸入可以對應到相同輸出，但是相同輸入不可以對應到相異輸出。

必須用到每個輸入，但是不一定要用到每個輸出。被用到的輸出們，稱作「像image」。

顯然，用到的輸入數量大於等於用到的輸出數量。

這些刁鑽古怪的規定，讓函數獨樹一格。宛如中醫利用藥的偏性來治病，數學家利用函數的特性來解題。

反函數（inverse）

一個函數的「反函數」，就是對調輸入輸出、反轉對應方向所形成的函數。反函數必須符合函數的規定。也就是說，必須用到每個輸出，而且相同輸出不可以對應到相異輸入。也就是說，輸入數量與輸出數量必須相等，而且恰好一一對應。

顯然，當f的反函數是g，則g的反函數是f。

想要表達反過來對應這件事，竟然還得符合函數的規定，實在很莫名其妙。直接發明一個「反對應」的概念不就好了？當然可以呀！只是數學家鮮少討論這件事而已。

函數的用法

函數可以描述兩件事物的關聯。例如三角函數就是三角形內角與邊長的關聯。半徑與圓周長、整數和質因數分解，通通可以寫成函數。

令x代表一個圓的半徑
perimeter(x) = 2πx

函數可以描述一件事物具有附屬屬性。例如一個人具有身高、具有體重。概念類似於中文的「的」、英文的「of」。

令x代表一個人
height(x)  一個人的身高
weight(x)  一個人的體重

函數可以描述從事一件事情的結果。

令x代表移動的方向，令f(x)代表移動的距離
f(east) = (+1,0)  往東，則x座標多一
f(west) = (-1,0)  往西，則x座標少一

函數可以描述圖形。函數的輸入和輸出必須是數值，當作是座標。例如愛心方程式。

函數還有各式各樣的用法，族繁不及備載。

Self-mapped Function in a Finite Set

此處我們討論電腦運算經常遭遇的一種函數：輸入與輸出完全相同、數量有限個（離散可數）的函數。

簡單的解讀方式：一群點，每一點只有一條出路，通往別人、亦得通往自己。

這種函數有著非常重要的特性：從任何一點出發，不斷往前走，最後必定繞圈、循環！

Cycle Finding

給定出發起點，請找到循環起點、循環長度。

應用廣泛，儘管外表看不出端倪。考驗你看穿事情本質的能力。

一、檢查一條list是否接錯而造成無限循環，並且找出接錯位置。
二、檢查兩條獨立的list是否接錯而牽連作伙，並且找出接錯位置。
三、一條陣列緊密放著n+1個數，數值皆介於1到n，
　　其中恰有兩數相同，請找出此數及此數位置。
四、整數除法，商數的循環節。
五、餘數次方，次方值的模數。
六、檢查自動機是否有無窮迴圈。

演算法（Memoization）

建立一條陣列，記錄各個元素是否拜訪過了。當遇到拜訪過的元素，就是循環起點。

int step[1000]; // 步數 void cycle_finding(int x) // x是給定的出發起點 { memset(step, -1, sizeof(step)); int c = 0; do { step[x] = c++; x = f(x); // 走一步 } while (step[x] == -1); cout << "循環起點" << x; cout << "循環長度" << c - step[x]; }

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

UVa 202 275 517 11549 12442 11607

龜兔賽跑演算法

以龜兔兩個變數就能找到循環，相當節省記憶體。

一、尋找循環長度的倍數：

龜兔從起點同時出發，龜走一步、兔就走兩步。由於兔比龜快，當龜兔皆進入循環之中，兔必然領先數圈、從後方追上龜。

當龜兔相遇，龜兔的行走距離差，即是循環長度的倍數。龜一倍速、兔兩倍速，龜兔的行走距離差，剛好是龜的行進距離。龜的行進距離即是循環長度的倍數。

二、尋找循環起點：

龜退回起點，兔原地待命，龜兔同時出發，龜走一步、兔走一步。龜兔相遇之處即是循環起點。

三、尋找循環長度：

從循環之中任意一處出發，一次走一步，繞一圈回到原處，即得循環長度。

void floyd(int x) { // 尋找循環長度的倍數。 // tortoise是龜，hare是兔。龜一倍速，兔兩倍速。 int tortoise = f(x), hare = f(f(x)); while (tortoise != hare) { tortoise = f(tortoise); hare = f(f(hare)); } // 尋找循環起點。 // 龜退回起點。龜兔皆一倍速。 hare = tortoise; tortoise = x; while (tortoise != hare) { tortoise = f(tortoise); hare = f(hare); } cout << "循環起點" << tortoise; // 尋找循環長度。 // 龜不動，兔一倍速。 int period = 1; hare = f(tortoise); while (tortoise != hare) { hare = f(hare); period++; } cout << "循環長度" << period; } int floyd(int x) { int a = 0, b = 0, period = 0; do { a = f(a); b = f(f(b)); } while (a != b); do { b = f(b); period++; } while (a != b); return period; }

時間複雜度

最佳情況是：當龜進入循環，正好龜兔相遇。

最差情況是：當龜進入循環，此時兔恰好在龜前方一步之距，兔得再繞兩圈才能追上龜。

令μ是出發起點到循環起點的距離，λ是循環長度。龜最多走μ + λ步，兔最多走2μ + 2λ步，時間複雜度3μ + 3λ = O(μ + λ)。

UVa 350 11053

演算法

一、尋找循環長度：

龜兔位於起點，龜保持不動，兔一步一步走。如果龜位於循環之中，那麼兔便可從後方追上龜，測量出循環長度。概念跟Floyd's Algorithm完全相同。

因為不知道龜是否位於循環之中，龜必須不時移動到兔的當前位置，讓龜有機會進入循環之中、讓兔有機會從後方追上龜。此處採用倍增法，每當兔走1步、續走2步、續走4步、……，龜會瞬間出現在兔的當前位置。

最差情況是出發起點與循環起點相距很遠，龜在進入循環前一刻，兔將多繞許多圈。然而多繞的步數其實小於等於μ（以倍增法推導），又由於龜不必移動，因而效率較佳。

二、尋找循環起點：

龜兔退回出發點。兔先走循環長度步，之後就跟Floyd's Algorithm完全相同。

由於兔額外移動，因而效率較差。

void brent(int x) { // 尋找循環長度 int power = 1, period = 1; int tortoise = x, hare = f(x); while (tortoise != hare) { if (power == period) { tortoise = hare; power *= 2; period = 0; } hare = f(hare); period++; } cout << "循環長度" << period; // 尋找循環起點 tortoise = hare = x; for (int i=0; i<period; ++i) hare = f(hare); while (tortoise != hare) { tortoise = f(tortoise); hare = f(hare); } cout << "循環起點" << tortoise; }