12. 两个机器人，初始时位于数轴上的不同位置。给这两个机器人输入一段相同的程序，使得这两个机器人保证可以相遇。程序只能包含“左移n个单位”、“右移n个单位”，条件判断语句If，循环语句while，以及两个返回Boolean值的函数“在自己的起点处”和“在对方的起点处”。你不能使用其它的变量和计数器。
    答案：两个机器人同时开始以单位速度右移，直到一个机器人走到另外一个机器人的起点处。然后，该机器人以双倍速度追赶对方。程序如下。

while(!at_other_robots_start) {
  move_right 1
}
while(true) {
  move_right 2
}

    13. 如果叫你从下面两种游戏中选择一种，你选择哪一种？为什么？
      a. 写下一句话。如果这句话为真，你将获得10美元；如果这句话为假，你获得的金钱将少于10美元或多于10美元（但不能恰好为10美元）。
      b. 写下一句话。不管这句话的真假，你都会得到多于10美元的钱。
    答案：选择第一种游戏，并写下“我既不会得到10美元，也不会得到10000000美元”。

Read more…

    偶然进了这个页面，看到几个原来没见过的面试智力题。顺带也翻译一些比较少见、可能有人没见过的题目写在这里。有几个题目在国内流传相当广，什么n个人怎么分饼最公平，屋里的三个灯泡分别由哪个开关控制，三架飞机环游世界，用火柴和两根绳子测量45分钟之类的题目，火星得已经可以考古了，这里就不再说了。个别题目本Blog原来有过详细的介绍，这里也不再提了。

    1. 考虑一个双人游戏。游戏在一个圆桌上进行。每个游戏者都有足够多的硬币。他们需要在桌子上轮流放置硬币，每次必需且只能放置一枚硬币，要求硬币完全置于桌面内（不能有一部分悬在桌子外面），并且不能与原来放过的硬币重叠。谁没有地方放置新的硬币，谁就输了。游戏的先行者还是后行者有必胜策略？这种策略是什么？
    答案：先行者在桌子中心放置一枚硬币，以后的硬币总是放在与后行者刚才放的地方相对称的位置。这样，只要后行者能放，先行者一定也有地方放。先行者必胜。

    2. 用线性时间和常数附加空间将一篇文章的单词（不是字符）倒序。
    答案：先将整篇文章的所有字符逆序（从两头起不断交换位置相对称的字符）；然后用同样的办法将每个单词内部的字符逆序。这样，整篇文章的单词顺序颠倒了，但单词本身又被转回来了。

    3. 用线性时间和常数附加空间将一个长度为n的字符串向左循环移动m位（例如，”abcdefg”移动3位就变成了”defgabc”）。
    答案：把字符串切成长为m和n-m的两半。将这两个部分分别逆序，再对整个字符串逆序。

    4. 一个矩形蛋糕，蛋糕内部有一块矩形的空洞。只用一刀，如何将蛋糕切成大小相等的两块？
    答案：注意到平分矩形面积的线都经过矩形的中心。过大矩形和空心矩形各自的中心画一条线，这条线显然把两个矩形都分成了一半，它们的差当然也是相等的。

    5. 一块矩形的巧克力，初始时由N x M个小块组成。每一次你只能把一块巧克力掰成两个小矩形。最少需要几次才能把它们掰成N x M块1×1的小巧克力？
    答案：N x M – 1次显然足够了。这个数目也是必需的，因为每掰一次后当前巧克力的块数只能增加一，把巧克力分成N x M块当然需要至少掰N x M – 1次。
Read more…

    从古至今，尺规作图一直是数学中备受关注的一个问题。到现在，数学家们已经比较完美的解决了尺规作图的问题，指出哪些图形可以用尺规作图完成，哪些问题不能用尺规作图解决。Mohr-Mascheroni定理告诉了我们一个非常令人吃惊的事实：所有用直尺和圆规可以解决的作图问题，只用圆规也能完成。当然，只用圆规是画不出直线的；但我们可以认为，一条直线已经由两点确定，并不需要画在图上。数学家们向我们展示了：给定四个点，如何用单规找出它们所确定的两条直线的交点；给定一段圆弧和两个点，如何找出两点确定的直线与圆弧的交点。注意到这是直尺仅有的功用，用单规全部解决了后直尺也就不需要了。数学家们还研究过单尺作图：只拿一块直尺到处作直线交过来交过去的又能完成哪些作图问题。显然，只用直尺是不能开平方的，解析几何告诉我们直线与直线的交点只可能是各系数的一个有理表达，这决定了单尺作图不能替代尺规作图。Poncelet-Steiner定理告诉我们，假如事先给定了一个圆和它的圆心，以后只用直尺足以完成任何尺规作图能够解决的问题。这些将在我今后的《什么是数学》笔记中提到。
    昨天，网友浅海里的鱼跟我提到了锈规作图问题，这是我第一次听到这个神奇的东西。现在，假设我们没有直尺，只有一把生锈的圆规。圆规已经被卡住了，只能画出单位半径的圆。在这样的条件下，哪些作图问题仍然能够被解决？锈规作图相当的困难，但并不是没有可能。1983年，D. Pedoe教授惊奇地发现，给定两个点A和B，如果它们的距离小于2，我们可以非常简单地作出点C，使得AC = BC = AB（即△ABC为等边三角形）。

    
    先以A、B为圆心分别作圆。由于它们之间的距离小于2，因此两圆必然相交。以其中一个交点P为圆心作圆，分别交圆A、圆B于点M、N。最后，圆M和圆N的交点即为所求点C。由对称性，△CAB一定是一个等腰三角形。另外，由对称性可知∠ACB=2∠BCP，而圆周角∠BCP的角度又是圆心角∠BNP的一半。由于△BNP是等边三角形，我们可以立即得到∠ACB=∠BNP=60°，△ABC是一个等边三角形。
    D. Pedoe受到启发，提出了以下问题：任给A、B两点，只用锈规是否都能作出C使得AC = BC = AB？若干年后，侯晓荣等人巧妙地解决了这个问题，并以此为基础，借用复数运算等理论，得到了一个出人意料的结论：从给定两点出发，任何尺规作图能够完成的构造，只用锈规也能完成。只用锈规作等边三角形的方法相当精彩，我在这里详细地说一下。觉得牛B的话就在下面叫个“好”。
Read more…

    如果你经常使用“file5.txt”、“梁静茹23.mp3”、“AdultVideo153.avi”一类的文件名，你会发现在给文件名排序时，这种命名方式存在很大的弊端。很大一部分程序直接用字典序给文件名排序，因此file10.txt会排到file2.txt前面，尽管事实上10比2大。你是否想过，有没有什么办法能给数字编码，使得它们按字典序排序后仍然保持原有的大小顺序，并且编码的方法足够简单，编码之后原来的数字仍可以一目了然？一种简单的方法就是加前缀0，这样就保证了002在010前面，file005.txt也不会排到file100.txt的后面。它有一个缺点就是，你必须预先知道需要编码的数字最多有多少位，否则一旦新添进一个位数更多的数，前面所有的数必需要全部重新编码（加更多的前缀0）。另一个比较明显的缺点就是，这种编码方式过于冗长，添加进去的数字0最多可能与最大数的位数相当，多数情况下都远远超过了待编码的数自身的长度。我们更希望，编码时添加进去的“辅助码”不要超过这个数字本身的长度。由于数字n本身的长度是log(n)，因此我们需要保证冗余部分不超过log(n)。你能找到满足这些条件的一种编码方式吗？

    注意到，当数字位数相同时，数值小的数按字典序排列时也排在前面。问题的关键就是，你需要找到一种编码方式，它可以标识出数字的位数，并且这种标识可以保证数字按位数从小到大排序。于是我们想到用“一进制编码”为每一个数加上一个“位数标识”。我们在每个数前面加上和这个数字本身的位数一样多的”1″，中间用一个”0″隔开。这样，所有三位数都是1110???的形式，所有四位数都是11110????的形式，这样按字典序排序时，三位数一定都排在四位数的前面。对应的解码方法也相当简单，只需要取第一个”0″后面的数字就行了。忽略常数的话，这种编码方式的冗余长度为log(n)，和数字本身的长度相当，基本上符合我们的要求。

   Read more…

    很久没有更新和信息学有关的东西了。今天和大家分享一个非常有趣的题目，我已经很久没看见如此精彩有趣的题目了。为了引入这个问题，我们先来介绍一个假想的编程语言QCPL。就像LISP一样，它是一个基于函数的语言：没有变量，没有for循环，一切东西都是用函数来表示的。另外，就像FORTRAN一样，QCPL语言不支持递归，也就是说一个函数不能递归地调用自己。QCPL的另一个有趣的特点是，所有的函数都只能返回一个Boolean值。比如说，下面这个函数的作用就是判断x+2和y+2的乘积是否等于z：
MULT_PLUS_TWO(x,y,z): (x+2)*(y+2)=z

    QCPL也有逻辑运算符。事实上，QCPL里的合法运算符一共只有8个，其中6个分别如下：

运算符 |  作用  |     输入      |     输出
——-+——–+—————+—————
  +    |  相加  |  两个自然数   |  一个自然数
  *    |  相乘  |  两个自然数   |  一个自然数
  =    |  等于  |  两个自然数   | 一个Boolean值
  &    | 逻辑和 | 两个Boolean值 | 一个Boolean值
  |    | 逻辑或 | 两个Boolean值 | 一个Boolean值
  !    | 逻辑非 | 一个Boolean值 | 一个Boolean值

    另外两个运算符就要重点介绍了。这是QCPL语言真正牛B的地方——它是专门为量子计算机设计的！你可以让这台计算机平行地穷尽完某些变量所有可能的取值，这一切仅仅在一瞬间内就可以完成。这两个特殊的运算符（以后我们管它们叫做“定量运算符”）就是专门用来干这件牛B事的："Ex"是“存在性定量运算符”，表示让计算机找出是否存在一个满足表达式的自然数x；"Ax"是“通用性定量运算符”，用于询问计算机该表达式是否对所有的自然数x均成立。比如，运用定量运算符，我们可以立即写出素数/合数判断函数：
COMPOSITE(n): Ex,Ey,MULT_PLUS_TWO(x,y,n)
PRIME(n): !(COMPOSITE(n)|n=0|n=1)
    其中，Ex,Ey,MULT_PLUS_TWO(x,y,n)的意思就是说，是否存在某一对x和y，使得MULT_PLUS_TWO(x,y,n)为真。只要（某一个平行世界里的）计算机找到了任何一对满足条件的x和y，整个COMPOSITE(n)立即返回True。如果对于所有的自然数x和y，MULT_PLUS_TWO(x,y,n)都不可能为真时，整个函数才返回False。别忘了这是一台量子计算机，穷举的过程可以在一瞬间内完成。

    好了，下面我们再给出几个基本的函数。函数SUM用于计算x加y是否等于z，而函数PRODUCT则用于检验x乘以y是否等于z：
SUM(x,y,z): x+y=z
PRODUCT(x,y,z): x*y=z
    现在，你的任务就是写出一个函数POWER(x,y,z)，当且仅当x的y次方等于z时函数才返回True。相信我，这道题没有那么容易。
Read more…