第一次呼吸这个世界的空气。
体验一次溺水濒死的感觉。
目睹一次大自然未解之谜。
第一次看到雪景。
第一次与父亲争辩并取胜。
参加一次集体舞比赛。
用两位数的加法鄙视一个同班的孩子。
用三位数的乘法鄙视一个同班的孩子。
用速算诀窍鄙视一个老师。
赢得一个实习老师的喜爱（她送了我一个纸折的鸽子）。
在语文考试中获得唯一一个满分。
第一次发现软盘的写保护位置。
学习使用一个操作系统。
学习使用另一个操作系统。
写一个VB程序。
做一个网页放在网上。
查看更多 »

这是Takeshi Miyakawa工作室设计的一款抽屉式储物柜，有一种分形的感觉，颇具Geek的味道。
图片来源：http://ffffound.com/image/36beab19234c8db955a7843f2712e8e2b3996f40

只要有足够的想象力，你也能亲手制作一个生活中的分形小玩意儿。之前本Blog曾经介绍过分形小饰物和分形饼干。

上个月Erich Friedman的Math Magic提出了这样的问题：
给定一个指定形状的棋盘，给定一个大于2的整数n，找出一个面积最大的图形S使得n个S能够不重叠地装进这个棋盘里。
问题提出之后得到了不少有趣的构造，这些构造是否为最优解还有待进一步证明。

 
由三个格子组成的棋盘共有两种本质不同的形状。“长条形”已经不用多考虑，“拐角形”中n=2, 3, 6时的最优解也是非常显然的。拐角形棋盘是可以分成四等分的。但是，在这个棋盘中放置5个相同的图形就没那么容易了。已知的最优方案占据了整个棋盘约0.959的面积。放置7个相同的图形研究起来更困难一些。已知最优解为0.956。

查看更多 »

    蛋白质结构一直是透析人体、了解病毒、制造药物的关键。然而，从无数多种可能的蛋白质结构中寻找最佳结构是一个相当困难的问题，即使利用高性能的计算机也需要耗费大量的时间和资金。受到SETI@home计划的启发，一些科学小组建立了Rosetta@home计划，让分布在世界各地的个人计算机一起来参与蛋白质三维形状的计算。对于千变万化的蛋白质形状来说，这仍然是一个相当庞大的工程。一些科学家注意到，在某些最优化问题上，人类的直觉远远强于一大堆计算机算法。Foldit就是这样一个程序，它打算用人类的解谜思维来代替计算机算法中的一部分决策，把确定蛋白质的最佳三维形状设计成一个游戏，使得人们在游戏过程中也能对生物科学做出贡献。在这个游戏中你可以不断调整蛋白质的三维形状，上传最高分和所得的三维体，参与世界排名，并且还能与游戏参与者进行即时聊天。

    游戏的规则很简单。一个谜题由一个方阵和周围给出的数字组成。方阵中有的地方放有镜子，有的地方是空地。方阵外的数字表示站在这个地方的人可以看到多少个鬼怪。你需要把指定数量的幽灵、吸血鬼和僵尸放到空格中，每个空地必须且只能放一个鬼怪，并且要求最终的布局与方阵外的数字相符。这个游戏真正好玩的地方在于它的一个机智而有趣的设定：吸血鬼在镜子里看不到，幽灵只能从镜子里才能看到；而无论是直接看还是通过镜子看，僵尸都能被看到。看了上面这句话，喜欢看恐怖电影的网友多半都会会心一笑。这些设定大大增加了游戏的乐趣，也给推理解谜带来比数独更多的变化。比如，同样都是只能看到最左上角的那一个格子，直接看的人能看到鬼怪，透过镜子看的人什么也看不到，于是我们可以立即判断出最左上角的空地只能是吸血鬼。再比如，左下角有两个被镜子分开的格子，从两种方向看过去都只能看到一个鬼，于是这两个格子要么都是幽灵，要么都是吸血鬼。
    这个网页（德文）里给了20个谜题，有兴趣的话可以去试一试。

1. 给你n个数，其中有且仅有一个数出现了奇数次，其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那一个数。
2. 给你n个数，其中有且仅有两个数出现了奇数次，其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那两个数。

1. 从头到尾异或一遍，最后得到的那个数就是出现了奇数次的数。这是因为异或有一个神奇的性质：两次异或同一个数，结果不变。再考虑到异或运算满足交换律，先异或和后异或都是一样的，因此这个算法显然正确。

2. 从头到尾异或一遍，你就得到了需要求的两个数异或后的值。这两个数显然不相等，异或出来的结果不为0。我们可以据此找出两个数的二进制表达中不同的一位，然后把所有这n个数分成两类，在那一位上是0的分成一类，在那一位上是1的分到另一类。对每一类分别使用前一个问题的算法。

题目来源：http://groups.google.com/group/pongba/browse_frm/thread/f4a080edbe3ce0e1

查看更多 »

    早晨7:40的闹铃。到36楼下面见到了我的两个队友后，随便吃了点东西就出发了。
    计算中心门前特别热闹，N多人围在一张大桌子前，好像是在签到。我挤进去找了半天发现没我的名字，名单上全是信科的人。我抬头问，中文的在哪儿呢。一个美女姐姐用手指了远处的一个几乎没人的地方说“中文的在那边”，并说了一句“哇，中文的呀，太牛B了”。我顺着她手指的方向望过去，另一张小桌子前面贴了“中文”二字，桌子后面没有人，估计是交给了旁边负责数院和元培的人，让他们顺便管一下。从我目前所了解的情况来看，那张桌子应该是特别为我准备的，它在历史上很可能是第一次出现。

      
    第四题是做得最顺利的一道题。我把所有题粗略看了一遍后，首先决定就想这道题。题目描述巨简单，就是问你沿对角线把一个正n边形剖分成三角形和四边形有多少种方法。上图显示了n=5时所有的10种方法。熟悉组合数学的人都知道，三角形剖分方案对应的是Catalan数列，其递推公式的推导相当经典。设C(n)表示凸n+2边形的剖分方案数，枚举底边和哪一个点相连（下图左），容易看出C(n) = C(0)*C(n-1) + C(1)*C(n-2) + … + C(n-1)*C(0)。
    
    现在，如果剖分中允许有四边形的出现，又该怎么办呢？看看数据规模n≤5000，估计应该是叫我们寻找类似的递推公式。容易想到，我们可以枚举底边与哪一个点相连构成三角形，统计出底边属于某个三角形的剖分方案T(n)=ΣC(i)C(j), i+j=n-1；再枚举底边和哪两个点相连构成四边形，统计底边在一个四边形上的剖分数Q(n)=ΣC(i)C(j)C(k), i+j+k=n-2。但是，枚举四边形需要O(n^2)的时间，这样的话整个程序就是O(n^3)的了，n=5000绝对超时。那怎么办呢？两分钟后，我想到了一个具有决定意义的点子：计算Q(n)可以直接利用以前算过的T(i)。枚举四边形的两个顶点时，固定四边形的左边那个顶点，你会惊奇地发现右半部分的所有情况加起来正好就是一个T(i) （上图右）。因此，ΣC(i)T(n-i-1)就是我们所需要的Q(n)。
    一个有趣的细节是，这道题要求选手输出结果除以2^64的余数，不知道会不会有人想不到这个该怎么处理；事实上只需要直接用64位无符号类型来运算就可以了，超界了后计算机储存的本来就已经是2^64的余数了。

查看更多 »

    我们想要计算无穷级数Σ(1/n)*(-1)^(n+1) = 1 - 1/2 + 1/3 - 1/4 + 1/5 - 1/6 …。首先我们需要说明，这个无穷级数是收敛的。注意到，从1的后面开始，每减去一个数后紧接着都会加上一个比它小的数，因此不管你加到哪儿，它的和始终不会超过1；另外，从1-1/2之后开始，每加一个数紧接着都会减去一个比它小的数，因此无论加到什么位置，整个和始终大于1/2。这说明，这个级数是收敛的，并且它收敛到1/2和1之间的某个数（事实上这个数是ln(2) ）。

    好了，令这个无穷级数为S，现在对S进行这样的变换：

S = 1 - 1/2 + 1/3 - 1/4 + 1/5 - 1/6 + …
  = (1 + 1/3 + 1/5 + 1/7 + …) - (1/2 + 1/4 + 1/6 + 1/8 + …)
  = (1 + 1/3 + 1/5 + 1/7 + …) - (1/2 + 1/4 + 1/6 + 1/8 + …) + (1/2 + 1/4 + 1/6 + 1/8 + …) - (1/2 + 1/4 + 1/6 + 1/8 + …)
  = (1 + 1/2 + 1/3 + 1/4 + …) - 2 * (1/2 + 1/4 + 1/6 + 1/8 + …)
  = (1 + 1/2 + 1/3 + 1/4 + …) - (1 + 1/2 + 1/3 + 1/4 + …)
  = 0

    但刚才不是说了S是大于1/2的么？这怎么可能呢？

查看更多 »