蛋白质结构一直是透析人体、了解病毒、制造药物的关键。然而，从无数多种可能的蛋白质结构中寻找最佳结构是一个相当困难的问题，即使利用高性能的计算机也需要耗费大量的时间和资金。受到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的么？这怎么可能呢？

查看更多 »

    今年年初就有写这篇文章的打算，但迟迟未动键盘。我一直想给大家介绍一下北大中文系的应用语言学专业，与大家分享一下自己的亲身经历和切身体会，让更多理科生关注这个新兴专业，顺便也骗一些理科小loli到我们专业来（我喜欢的类型）。现在离高考越来越近了，再不写就不行了。其它一些废话我就不多说了，关于北大中文系应用语言学专业到底是咋回事，包括它的定位和出路，网上到处都有介绍。你可以在这里看到一些比较正式的专业介绍，以及一份详细的课程表。其它一些如志愿填报、学习生活之类的比较杂的问题我也不谈了，王婵娟师姐的文章已经写的很详细了。这里主要侃一下我目前所学到的几门课程。

    考虑到这篇文章可能会被到处转载，首先告诉大家，我的Blog是matrix67.com。你可以从这个Blog的内容里看到，我的思维是非常纯的理科思维，除了科幻小说和文字游戏以外，对语言文字提不起任何兴趣。因此，这里你可以看一看，一个对传统文学甚至有些抵触心理的应用语言学学生是如何看这个专业的。
    大一的专业课主要是现代汉语、古代汉语、现代文学史、计算概论和高等数学(C)。计算概论说穿了就是学C语言，高等数学说穿了就是微积分。这两个我都不说了。这里主要说一下前面三个和中文相关的专业课程。

现代汉语

    现代汉语是所有中文的专业课中最科学的课程之一，说穿了就是现代汉语语言学。我是相当喜欢这门课程的，希望你读到下面这段文字后也会对这门课产生一些兴趣。之前写了这篇日志，讲了汉语中某些词类的个别词语的特殊语法现象，想不到真的有人感兴趣，并期待我更新更多类似的东西。我们继续那篇日志，再选一些现代汉语课上学到的有趣的东西说说，希望大家能喜欢。

查看更多 »

    多年以前，要想进入莫斯科国立大学的数学系，你必须通过四项入学考试；头两个都是数学考试，一个笔试，一个面试。在面试中，学生和考官都是一对一的，考官可以自由向学生提出任何他喜欢的问题。那时，为了筛选出他们不想要的应试者（主要是犹太人），很多考官都会出一些题目描述简单有趣、解答过程极其巧妙而又出人意料的问题。这些问题极具杀伤力，民间戏称其为“棺材问题”(coffin problems)。下面这个问题就是其中一个“棺材问题”：
    考虑一个空间四边形A1A2A3A4，它的四条边A1A2, A2A3, A3A4, A4A1都与一个给定的球相切。求证，这四个切点共面。
    为了更好地理解这个问题，考虑一个菱形的钢架沿对角线折叠，或者一个正四面体钢架去掉相对的两条棱。把这个空间四边形当成一个碗去接一个球，你会发现这个球卡在空间四边形中掉不下去了，此时它与四条边都相切。凭借我们的生活经验，我们很容易提出这个猜想：四个切点是共面的。

查看更多 »

查看更多：http://www1-c703.uibk.ac.at/mathematik/project/bildergalerie/gallery.html
（德语，Stetson MM快来翻译）