想像一个圆盘在地面上滚动一周，那么圆周上一点所形成的轨迹就叫做旋轮线（或者摆线）。旋轮线下方的面积是多少，这是一个非常有趣的问题。据说， Galileo 曾经用一种非常流氓的方法，推测出了旋轮线下方的面积。他在金属板上切出一块圆片，再在金属板边缘剪下这个圆形所对应的旋轮线，把它们拿到秤上一称，发现后者的重量正好是前者的三倍。于是，他推测，半径为 r 的滚轮所产生的旋轮线，其下方的面积就是 3πr² 。

    不过，今天我第一次知道，这个结论对于正多边形是同样成立的。

查看更多 »

    昨天终于读完了《The Annotated Turing》一书，第一次完整地阅读了 Turing 最经典的那篇论文，理解了 Turing 机提出的动机和由此带来的一系列结论。不过，这本书的最大价值，则是让我开始重新认识和思考这个世界。在这里，我想把我以前积累的哲学观点和最近一些新的思考记下来，与大家一同分享。《The Annotated Turing》一书中的一些学术内容，留待以后几篇日志与大家分享。今年是 Alan Turing 诞辰 100 周年，图灵公司将推出这本书的中译本《图灵的秘密》，现在正在紧张的编辑排版中，不久之后就能和大家见面。

    1928 年， David Hilbert 提出了一个著名的问题：是否存在一系列有限的步骤，它能判定任意一个给定的数学命题的真假？这个问题就叫做 Entscheidungsproblem ，德语“判定性问题”的意思。大家普遍认为，这样的一套步骤是不存在的，也就是说我们没有一种判断一个数学命题是否为真的通用方法。为了证明这一点，真正的难题是将问题形式化：什么叫做“一系列有限的步骤”？当然，现在大家知道，这里所说的“有限的步骤”指的就是由条件语句、循环语句等元素搭建而成的一个机械过程，也就是我们常说的“算法”。不过，在没有计算机的时代，人们只能模模糊糊地体会“一个机械过程”的意思。 1936 年，Alan Turing 在著名的论文《On computable numbers, with an application to the Entscheidungsproblem》中提出了一种假想的机器，第一次给了“机械过程”一个确凿的含义。

查看更多 »

    英语当中有一种笑话类型。第一次看到的是：

- What's the difference between a girl in church and a girl in the bathtub?
- One has hope in her soul, one has soap in her hole.

    把我给笑坏了。在说这种笑话的时候，只说一半的效果往往更好。又比如：

- What's the difference between a midget magician and a female jogger?
- One is a cunning runt...

    我想，汉语当中应该也有不少这样的词语对吧。于是，我找来了一份汉语常用词拼音的数据，从中搜索出了一大堆声母颠倒的词语对。喜欢给别人出谜题的我自然没有放过这一机会。请你在下面每句话的两个空格中分别填入两个声母颠倒的双字词，使得整个句子通顺完整。每个小题都有至少一个由常用词构成的解。比如，第一小题的答案就是“宝地”和“倒闭”。

      1. 虽然公司位于一块 _____ ，但最后还是 _____ 了。
      2. 魔术师熟练地从 _____ 里变出了一只 _____ 。
      3. 他知道好几种 _____ 翻新机的 _____ 方法。
      4. 为了磨炼意志，他常常赤身睡在 _____ 铁钉的 _____ 上。
      5. 这种机械化的 _____ 严重 _____ 了学生的创造思维。
      6. 《阿凡达》电影票一票难求，排队买票的 _____ _____ 超过了春运。
      7. 使用过期的 _____ 会 _____ 检测结果有误差。
      8. 前线发来 _____ 称他们已经发现了敌方 _____ 部队。
      9. _____ 的领导者不应该与员工之间有任何 _____ 。
      10. 各个主要 _____ 都有专职护林防火人员 _____ 。
      11. _____ 功能衰退不影响学生正常 _____ 。
      12. 目前，各地塑料 _____ 市场现状一片 _____ 。
      13. 服用戒烟 _____ 药物最好听从医师的 _____ 。
      14. 人体内脏 _____ 业正在美国悄悄 _____ 。
      15. 与 _____ 关系不融洽终会让你逐渐 _____ 对工作的热情。
      16. “民工潮” _____ 的人口 _____ 将不断推进户籍制度的改革。
      17. 表盘上的 6 点钟位置附有非常 ______ 的 _____ 显示。
      18. 她那半月形的银质发箍卡在金色的头发上，远远看去就像是 _____ 时期的 _____ 。
      19. _____ 设计的一个重要应用就是 _____ 设计。
      20. 人们在工地里挖出了那次 _____ 中留下来的一颗 _____ 。

查看更多 »

    今天看到这里给出了一个“星际争霸是 NP-hard 问题”的一个证明。具体地说，给定一个初始布局（包括地图、双方已有资源、双方已有建筑、双方已有兵力），判断其中一方是否能获胜，这个问题是 NP-hard 的。当然，考虑到即时战略游戏的复杂性，这个结论并不出人意料；真正有趣的，则是如何巧妙地利用游戏中的元素，构造出极其精巧的初始局面，从而转化成某个已知的 NP-complete 问题。下面是原文中给出的证明。这个证明有没有什么漏洞？你还能想到哪些别的证明方法？欢迎在下面留言一同分享。

查看更多 »

    数列 1, 1, 2, 3, 5, 8, 13, 21, 34, … 叫做 Fibonacci 数列。这个数列有很多神奇的性质，其中一个性质是，每一个 Fibonacci 数的平方与它前后两个 Fibonacci 数的乘积一定正好相差 1 。具体地说，如果把第 n 个 Fibonacci 数记做 F_n ，那么有：

      F_n+1 · F_n+1 - F_n · F_n+2 = (-1)ⁿ

    今天看到了这个定理的一个组合数学证明，觉得非常有意思，在这里和大家分享。

查看更多 »

    无论是小学奥数，还是公务员考试，还是公司的笔试面试题，似乎都少不了行程问题——题目门槛低，人人都能看懂；但思路奇巧，的确会难住不少人。平时看书上网与人聊天和最近与小学奥数打交道的过程中，我收集到很多简单有趣而又颇具启发性的行程问题，在这里整理成一篇文章，和大家一同分享。这些题目都已经非常经典了，绝大多数可能大家都见过；希望这里能有至少一个你没见过的题目，也欢迎大家来信提供更多类似的问题。

    让我们先从一些最经典最经典的问题说起吧。选中空白部分显示答案。

    甲、乙两人分别从相距 100 米的 A 、B 两地出发，相向而行，其中甲的速度是 2 米每秒，乙的速度是 3 米每秒。一只狗从 A 地出发，先以 6 米每秒的速度奔向乙，碰到乙后再掉头冲向甲，碰到甲之后再跑向乙，如此反复，直到甲、乙两人相遇。问在此过程中狗一共跑了多少米？

查看更多 »

    这篇文章是漫话中文分词算法的续篇。在这里，我们将紧接着上一篇文章的内容继续探讨下去：如果计算机可以对一句话进行自动分词，它还能进一步整理句子的结构，甚至理解句子的意思吗？这两篇文章的关系十分紧密，因此，我把前一篇文章改名为了《漫话中文自动分词和语义识别（上）》，这篇文章自然就是它的下篇。我已经在很多不同的地方做过与这个话题有关的演讲了，在这里我想把它们写下来，和更多的人一同分享。

    什么叫做句法结构呢？让我们来看一些例子。“白天鹅在水中游”，这句话是有歧义的，它可能指的是“白天有一只鹅在水中游”，也可能指的是“有一只白天鹅在水中游”。不同的分词方案，产生了不同的意义。有没有什么句子，它的分词方案是唯一的，但也会产生不同的意思呢？有。比如“门没有锁”，它可能是指的“门没有被锁上”，也有可能是指的“门上根本就没有挂锁”。这个句子虽然只能切分成“门／没有／锁”，但由于“锁”这个词既有可能是动词，也有可能是名词，因而让整句话产生了不同的意思。有没有什么句子，它的分词方案是唯一的，并且每个词的词义也都不再变化，但整个句子仍然有歧义呢？有可能。看看这句话：“咬死了猎人的狗”。这句话有可能指的是“把猎人的狗咬死了”，也有可能指的是“一只咬死了猎人的狗”。这个歧义是怎么产生的呢？仔细体会两种不同的意思后，你会发现，句子中最底层的成分可以以不同的顺序组合起来，歧义由此产生。

查看更多 »