最近在看Pólya的《数学与猜想》，读到了一些很有意思的东西，在这里和大家分享。
    我们首先来看一道很火星的题目：A、B两点在已知直线的同侧，请在直线上找出一点C使得∠ACB最大。可能大家都知道这个该怎么做，但这个解法到底是怎么想到的呢？《数学与猜想》提到了这样一种看法：
      
    首先，我们需要确定，这条直线上的确存在一点，使得这个角度达到最大。我们很容易观察到，这个动点往左移（可以一直移动到BA的延长线与直线的交点），这个角度会慢慢变小；同时，动点不断往右移时角度也会慢慢变小（在无穷远处角度为0）。可以想到，角度大小的变化可以用一个凸函数来表示，这段函数上一定存在一个最大点。现在任意在直线上取一点C，你怎么才能说明∠ACB是最大或者不是最大？一个比较直观的方法是，如果你取的C点不能使角度达到最大，那么这条直线上一定存在另一个点C'，使得∠ACB=∠AC'B。分析到这一步，问题终于有了眉目，因为有一个大家都很熟悉的东西恰好与角度相等有关——同一段弧所对的圆周角总是相等。过点AB作一系列的圆，那么同一个圆周上的所有点对AB的张角都是一样大的。我们看到，这些蓝色的线条与直线的交点都是成对出现，换句话说ABC三点确定的圆与直线的另一个交点就是那个C'。但有那么一个点非常例外：在这无穷多个圆中，有一个圆恰好与直线相切。这个切点只出现了一次，它就是角度大小的极大值。

    真正的数学家会从这个简单的题目里看到一些更深的思想。我们可以把这个图任意的扭曲，从而得到这样一个有趣的结论。假设我和MM在野外探险，地形是任意给定的，我们的行动路线也是任意给定的。现在我有一张非常精确的等高线地图，我把我们的路线画在地图上，那么整个旅途中所到达的最高点和最低点在地图上的什么位置？仔细思考等高线的定义，我们立即想到：路径穿过等高线的地方肯定不会是最高点或最低点，因为穿过一条等高线即表明你正在爬上爬下。因此，达到最高点或最低点的地方只能是等高线与我的路线相切的地方。这给我们一个启发：我们可以用这种模式来解决很多极大极小问题。我们把所有可能的结果的分布情况用等高线表示，而实际允许的初始条件则被限制在了一条路径上，那么最优解必然是这条路径与某条等高线的切点。用等高线模式来解释刚才的问题将变得非常简单：图中的蓝色线条就是角度大小的“等高线”，在直线上取得极值的时候，等高线恰与直线相切，其它情况下角度大小都在“变化进行时”。
    我们再来看三个有趣的例子。在第一个例子中我们将解释为什么点到直线的距离以垂线段最短，第二个例子则将探究为什么所有的圆内接n边形以正n边形最大。在第三个例子里我们将提到一个与椭圆有关的神奇性质。

    上面这个图就是到定点距离大小的等高线图。我们可以立即看到，等高线就是一个个的同心圆。与已知直线相切的那个同心圆确定了直线到给定点距离最短的位置，而圆的半径与对应位置上的切线垂直，这就说明了点到直线的距离以垂线段最短。

      
    下面我们考虑圆内接多边形的某个顶点X。这个顶点两旁的点分别是A和B。那么整个多边形被分成了两部分：三角形AXB，和剩下的那一大块多边形。如果我们只移动点X，这只会影响三角形AXB的面积，对剩下的部分没有影响。X在不同位置所得到的三角形面积不同，在图中我们用蓝色的等高线来表示这个面积值的分布情况。由于等底等高的三角形面积相同，因此我们的等高线是一系列互相平行的直线。点X只能在一段圆弧上取，当△AXB达到最大时X必然落在圆弧与某条直线相切的地方，显然此时AX=BX。换句话说，只要圆内接多边形里有长度不等的邻边，那么这个多边形的面积一定可以变得更大。再换句话说，只有所有边都相等了，面积才可能达到最大。这就说明了，所有的圆内接n边形以正n边形最大。

    我相信你已经对这个方法非常熟悉了，因此最后这个例子我就不画图了。在第三个例子中，我们将考虑一个和光学有关的性质。给定一条直线和直线同侧的两点A、B，那么直线上一定有一点C使得AC+BC达到最小。这个点C是一个以A、B为焦点的椭圆形等高线与直线的切点。固定点A和点B，适当调整直线的位置，结论始终成立。还记得Fermat原理吗，光从一点到另一点总是沿着光程最短的路径来传播。仅考虑反射定律，这个结论很显然。也就是说，A->C->B这样的光线传播路径完全遵循光的反射规律。嘿！我证明了这样一个富有传奇色彩的结论：椭圆形从一个焦点发射出来的光线总会反射到另一个焦点。

做人要厚道
转贴请注明出处

    Anagram是一个比较流行的英文文字游戏，本Blog之前曾经介绍过，这里我再提一下。Anagram就是把一个词或者一句话里的字母重新排列，组成一个新的单词或句子，通常前后两者有一种讽刺的意味。比如，Dormitory = Dirty Room，或者Desperation = A Rope Ends It。创作一个有意思的Anagram并不是一件容易的事，你很可能需要计算机的帮助才能找到合适的词。例如，我们可以利用Hash表瞬间找出与给定单词所使用的字母完全相同的单词。我们可以把字典中每个单词的字母按照字母顺序重新排列，于是对单词dame和made操作后的结果都是adem，这样的话使用字母完全相同的单词就对应了一个唯一的Hash值，我们就可以方便地把它们归在一起。
    而实际上，这个Hash表往往没什么用。一个Anagram很可能是由多个单词构成的，因此我们更希望知道，使用某个单词中的字母（不一定全部使用）可以构造出哪些新的单词。例如，我输入单词dormitory，则程序可以输出dirty, motor, trim, dry, room等单词。很多Anagram辅助程序都有这样的功能，并且这也单独作为一个文字游戏存在。我们称这种只用到一部分给定字母的单词叫做不完全Anagram。假如字典里共有n个单词，输入数据长度为l，那么你怎样才能找出所有的不完全Anagram？一种方法是遍历所有n个单词，依次判断每个单词是否合法；另一种方法则是枚举输入数据的2^l子集，对每个子集在之前建立的Hash表中查询一次。现在，你能否想出一个数据结构，使得你的Anagram辅助程序能够以最快的速度输出任何一个给定单词的不完全Anagram？

  
    答案比你想像的更简单，这是一个非常简单的数据结构。我们建立一棵高度为26的树，按照每个字母出现的次数像Trie一样插入到树中。比如，abacus有2个a，于是插入到根的第二个子树里，接下来数出字母b的个数为1，并继续沿标号为1的边往下走，依此类推。最后，所有的数据都存放在对应的叶子节点上。查询时，在每个节点上只需数一数输入数据中对应字母的个数N，沿着标号小于等于N的边往下走就行了。
    下面是一个非常有趣的问题：这个数据结构还有什么优化的余地？比如，单词在树中是按照从A到Z的顺序依次分类，但实际上我们可以任意调整这个顺序。那么，你觉得建这棵树时是先按E、T等常用字母的个数分类好，还是先按照Q、Z等不常用字母的个数分类好？这个问题很简单，留给大家思考吧。
    另一个比较类似的东西是用于拼写检查的数据结构。这两个有趣的数据结构都是我在这里看到的。

做人要厚道
转贴请注明出处

    除了字符串匹配、查找回文串、查找重复子串等经典问题以外，日常生活中我们还会遇到其它一些怪异的字符串问题。比如，有时我们需要知道给定的两个字符串“有多像”，换句话说两个字符串的相似度是多少。1965年，俄国科学家Vladimir Levenshtein给字符串相似度做出了一个明确的定义叫做Levenshtein距离，我们通常叫它“编辑距离”。字符串A到B的编辑距离是指，只用插入、删除和替换三种操作，最少需要多少步可以把A变成B。例如，从FAME到GATE需要两步（两次替换），从GAME到ACM则需要三步（删除G和E再添加C）。Levenshtein给出了编辑距离的一般求法，就是大家都非常熟悉的经典动态规划问题。
    在自然语言处理中，这个概念非常重要，例如我们可以根据这个定义开发出一套半自动的校对系统：查找出一篇文章里所有不在字典里的单词，然后对于每个单词，列出字典里与它的Levenshtein距离小于某个数n的单词，让用户选择正确的那一个。n通常取到2或者3，或者更好地，取该单词长度的1/4等等。这个想法倒不错，但算法的效率成了新的难题：查字典好办，建一个Trie树即可；但怎样才能快速在字典里找出最相近的单词呢？这个问题难就难在，Levenshtein的定义可以是单词任意位置上的操作，似乎不遍历字典是不可能完成的。现在很多软件都有拼写检查的功能，提出更正建议的速度是很快的。它们到底是怎么做的呢？1973年，Burkhard和Keller提出的BK树有效地解决了这个问题。这个数据结构强就强在，它初步解决了一个看似不可能的问题，而其原理非常简单。

    首先，我们观察Levenshtein距离的性质。令d(x,y)表示字符串x到y的Levenshtein距离，那么显然：

1. d(x,y) = 0 当且仅当 x=y  （Levenshtein距离为0 <==> 字符串相等）
2. d(x,y) = d(y,x)     （从x变到y的最少步数就是从y变到x的最少步数）
3. d(x,y) + d(y,z) >= d(x,z)  （从x变到z所需的步数不会超过x先变成y再变成z的步数）

    最后这一个性质叫做三角形不等式。就好像一个三角形一样，两边之和必然大于第三边。给某个集合内的元素定义一个二元的“距离函数”，如果这个距离函数同时满足上面说的三个性质，我们就称它为“度量空间”。我们的三维空间就是一个典型的度量空间，它的距离函数就是点对的直线距离。度量空间还有很多，比如Manhattan距离，图论中的最短路，当然还有这里提到的Levenshtein距离。就好像并查集对所有等价关系都适用一样，BK树可以用于任何一个度量空间。

    建树的过程有些类似于Trie。首先我们随便找一个单词作为根（比如GAME）。以后插入一个单词时首先计算单词与根的Levenshtein距离：如果这个距离值是该节点处头一次出现，建立一个新的儿子节点；否则沿着对应的边递归下去。例如，我们插入单词FAME，它与GAME的距离为1，于是新建一个儿子，连一条标号为1的边；下一次插入GAIN，算得它与GAME的距离为2，于是放在编号为2的边下。再下次我们插入GATE，它与GAME距离为1，于是沿着那条编号为1的边下去，递归地插入到FAME所在子树；GATE与FAME的距离为2，于是把GATE放在FAME节点下，边的编号为2。
      
    查询操作异常方便。如果我们需要返回与错误单词距离不超过n的单词，这个错误单词与树根所对应的单词距离为d，那么接下来我们只需要递归地考虑编号在d-n到d+n范围内的边所连接的子树。由于n通常很小，因此每次与某个节点进行比较时都可以排除很多子树。
    举个例子，假如我们输入一个GAIE，程序发现它不在字典中。现在，我们想返回字典中所有与GAIE距离为1的单词。我们首先将GAIE与树根进行比较，得到的距离d=1。由于Levenshtein距离满足三角形不等式，因此现在所有离GAME距离超过2的单词全部可以排除了。比如，以AIM为根的子树到GAME的距离都是3，而GAME和GAIE之间的距离是1，那么AIM及其子树到GAIE的距离至少都是2。于是，现在程序只需要沿着标号范围在1-1到1+1里的边继续走下去。我们继续计算GAIE和FAME的距离，发现它为2，于是继续沿标号在1和3之间的边前进。遍历结束后回到GAME的第二个节点，发现GAIE和GAIN距离为1，输出GAIN并继续沿编号为1或2的边递归下去（那条编号为4的边连接的子树又被排除掉了）……
    实践表明，一次查询所遍历的节点不会超过所有节点的5%到8%，两次查询则一般不会17-25%，效率远远超过暴力枚举。适当进行缓存，减小Levenshtein距离常数n可以使算法效率更高。

Matrix67原创
做人要厚道 转贴请注明出处

http://www.ocf.berkeley.edu/~wwu/riddles/cs.shtml

一些很另类的信息学问题，比如：用常数空间线性时间找链表中的一个环，只用NAND实现XOR门，不用乘法和加法把一个数乘以7，常数时间无附加空间交换两变量，写一个输出自己代码的程序，用n + O(log n)次比较查找第二小的元素，写一个程序用C编译时输出“C”而用C++编译时输出“C++”……

另外，不要找我要答案，我这里没有答案