Question

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 座标少一

函数可以描述图形。函数的输入和输出必须是数值，当作是座标。例如爱心方程式。

函数还有各式各样的用法，族繁不及备载。

Cycle Finding

Self-mapped Function in a Finite Set

此处我们讨论电脑运算经常遭遇的一种函数：输入与输出完全相同、数量有限个（离散可数）的函数。

简单的解读方式：一群点，每一点只有一条出路，通往别人、亦得通往自己。

这种函数有著非常重要的特性：从任何一点出发，不断往前走，最后必定绕圈、循环！

Cycle Finding

给定出发起点，请找到循环起点、循环长度。

应用广泛，儘管外表看不出端倪。考验你看穿事情本质的能力。

一、检查一条 list 是否接错而造成无限循环，并且找出接错位置。
二、检查两条独立的 list 是否接错而牵连作伙，并且找出接错位置。
三、一条阵列紧密放著 n+1 个数，数值皆介于 1 到 n，
　　其中恰有两数相同，请找出此数及此数位置。
四、整数除法，商数的循环节。
五、馀数次方，次方值的模数。
六、检查自动机是否有无穷迴圈。

Cycle Finding: Memoization

演算法（Memoization）

建立一条阵列，记录各个元素是否拜访过了。当遇到拜访过的元素，就是循环起点。

这个方法既简单又快，不过缺点就是记忆体用很凶。时间複杂度为 O(N)，空间複杂度为 O(N)，N 为集合大小。

UVa 202 275 517 11549 12442 11607

Cycle Finding: Floyd's Algorithm（Tortoise and Hare Algorithm）

龟兔赛跑演算法

以龟兔两个变数就能找到循环，相当节省记忆体。

一、寻找循环长度的倍数：

龟兔从起点同时出发，龟走一步、兔就走两步。由于兔比龟快，当龟兔皆进入循环之中，兔必然领先数圈、从后方追上龟。

当龟兔相遇，龟兔的行走距离差，即是循环长度的倍数。龟一倍速、兔两倍速，龟兔的行走距离差，刚好是龟的行进距离。龟的行进距离即是循环长度的倍数。

二、寻找循环起点：

龟退回起点，兔原地待命，龟兔同时出发，龟走一步、兔走一步。龟兔相遇之处即是循环起点。

三、寻找循环长度：

从循环之中任意一处出发，一次走一步，绕一圈回到原处，即得循环长度。

时间複杂度

最佳情况是：当龟进入循环，正好龟兔相遇。

最差情况是：当龟进入循环，此时兔恰好在龟前方一步之距，兔得再绕两圈才能追上龟。

令μ是出发起点到循环起点的距离，λ是循环长度。龟最多走μ + λ步，兔最多走 2μ + 2λ步，时间複杂度为 3μ + 3λ = O(μ + λ)。

UVa 350 11053

Cycle Finding: Brent's Algorithm

演算法

一、寻找循环长度：

龟兔位于起点，龟保持不动，兔一步一步走。如果龟位于循环之中，那麽兔便可从后方追上龟，测量出循环长度。概念跟 Floyd's Algorithm 完全相同。

因为不知道龟是否位于循环之中，龟必须不时移动到兔的当前位置，让龟有机会进入循环之中、让兔有机会从后方追上龟。此处採用倍增法，每当兔走 1 步、续走 2 步、续走 4 步、……，龟会瞬间出现在兔的当前位置。

最差情况是出发起点与循环起点相距很远，龟在进入循环前一刻，兔将多绕许多圈。然而多绕的步数其实小于等于μ（以倍增法推导），又由于龟不必移动，因而效率较佳。

二、寻找循环起点：

龟兔退回出发点。兔先走循环长度步，之后就跟 Floyd's Algorithm 完全相同。

由于兔额外移动，因而效率较差。