Matrix67 |
2009-05-30 1:49 | 
网上有各种直观的排序算法图形化演示（见这里和这里），我自己也曾经做过一个。
今天我看到了一个我所见过的最酷的、最可爱的排序算法演示。
某网站被干掉了后，大家会错过很多精彩的视频。我注册了一个土豆网的帐号，把一些精彩的视频搬过来与大家分享。
May
30
May
28
May
27
May
27
一条直径可以把圆面积二等分。两条互相垂直的直径可以把圆面积四等分。不过，对于任意的N，将圆面积等分为N个部分并不容易，因为圆周上的N等分点并不总是能用圆规和直尺做出来。1801年，Gauss证明了当n为2的幂和若干Fermat素数的乘积时，正n边形可以用尺规作出图来，同时他猜想这也是必要条件。1837年，Pierre Wantzel证明了这个条件的必要性。第一个无法用尺规完成作图的正多边形是正七边形，也就是说你永远无法仅用直尺和圆规找出圆周上的七等分点。
不过，这并不意味着我们不能将圆面积分成面积相等的七份。事实上，有一种方法可以将圆分成N个面积相等的部分，其中N可以为任意正整数。你能想到这种方法吗？如果我们还要求各部分周长也相等呢？
May
25
阴阳图是由两个半圆弧相接组成的曲线把整个圆平分为黑白二色而成。1958年，英国数学家Henry Dudeney在他的著作Amusements in Mathematics中曾经提出了这样一个问题：如何用尺规作出一条同时平分阴阳两部分的曲线？他给出了两种不同的答案。
第一种方法是非常完美的，它不但同时平分了阴阳两部分的面积，连分出来的形状也完全相同。另一种办法也非常简单，仅用一条45度倾斜的直线即可同时平分阴阳两部分。为了证明这一点，我们只需要计算一下白色的半圆形和45度扇形的面积和即可。二者的面积恰好都等于πR^2/8，其总和为πR^2/4，恰为整个白色区域的一半。由对称性，黑色面积也被平分。除此之外，你还能想到多少种平分方法呢？
May
23
转眼间又到期末了，各科的课程都差不多结束了。回顾这个学期的课程，音韵学毫无疑问成为了最不科学的课，而语义学和虚词研究则成为了本学期最具科学性的两门课。这学期我在沈阳老师的语义学课程中学到了不少东西，有几节课尤其精彩，以至于当时我就拍案叫绝，发誓一定要把它们写到Blog上。最精彩的一节课是关于“把”字句分析的专题讲解，其科学性、趣味性和大众性远远超过了这里和这里的例子，成为了我向别人介绍语言学时引入的最佳例子。从对“把”字句的分析中我们可以看到更多语言学研究方法，其论证思想绝不亚于数理学科。
小学语文变“把”字句“被”字句时无外乎“风把小树刮倒了”、“解放军把敌人打败了”、“大水把铁牛冲走了”，这无形之中给人带来了这样一种错觉：“把”字后面的名词是动词的宾语。例如，“小树”就是“刮”的宾语，“敌人”就是“打”的对象，“水”冲走的当然也就是“铁牛”。事实上，确实也有很多学术文章指出，“把”后名词就是动词的宾语。“宾语说”的支持者们提出了一个直观的、强有力的证据：你可以把“把”字句重新还原回主动宾结构。例如，“风把小树刮倒了”的意思就是“风刮倒了小树”，“解放军把敌人打败了”就相当于“解放军打败了敌人”，“大水把铁牛冲走了”无异于“大水冲走了铁牛”。这种说法虽然适用于绝大多数“把”字句，但也并非毫无破绽。例如，“妈妈把钱存在银行里”怎么还原为主动宾结构？妈妈存钱在银行里？妈妈存在银行里钱？都不对。这一反例足以对“宾语说”构成威胁。事实上，我们能举出很多例子来驳斥“宾语说”。一种听来奇怪但我们日常生活里常常使用的句子就是“别把自己病倒了”，这里“自己”明显只能是“病”的主语。类似的句子不止一个，像“他把老伴儿死了”、“把犯人跑了”等等，感觉虽然奇怪，但实际生活中用得不少。另一类句子更奇怪，动词和“把”后名词间根本没有直接联系，像“把肚子笑疼了”，“肚子”一词既不是“笑”的主语，也不是“笑”的宾语，事实上它与“笑”没有任何关系。“把眼睛哭肿了”、“把手帕哭湿了”也是如此，“眼睛”和“手帕”与动作“哭”没有任何结构上的联系。“宾语说”至此已完全破产。
May
22
这里有一个有趣的问题：在集合{1, 2, ..., n}中选取尽可能多的子集，使得任意两个子集的交集有且仅有一个元素。例如，当n=7时，选取{1,2,3,4}、{4,5,6,7}、{1,7}这3个集合可以满足条件。子集数还可以更大一点吗？最大是多少？给出一种构造，然后证明这个数目不可能更大了。
当n=7时，仅仅取3个子集实在是太弱了。一种最简单的办法就可以让子集数达到6，只需取{1,2}、{1,3}、{1,4}、{1,5}、{1,6}、{1,7}即可。再仔细观察，我们发现这个结果还可以进一步改进：我们还可以再往里面添加进一个子集{1}，使得这7个子集两两间仍然恰有一个公共元素。这下我们似乎不能再往里面添加任何新子集了。我们还可以做得更好吗？一个新的思路是在{1,2}、{1,3}、{1,4}、{1,5}、{1,6}、{1,7}里面加上{2,3,4,5,6,7}，这同样可以让子集数达到7个，可惜我们仍然无法再往里面添加新的子集了。经过若干次尝试后，我们逐渐开始确信，在集合{1, 2, ..., n}里面最多只能选出n个两两恰有一个公共元素的子集，并且构造方法无外乎上面两种。这一猜想不但与直觉相符，而且貌似也很好证明。你或许会从一些看似很直观的结论出发开始证明：“显然不可能有两个大小为1的子集”，“选取多个元素个数大于2的子集显然不划算”……但牛B就牛B在，偏偏就有这样一种子集数为n的取法，每个子集里都有不止两个元素，但仍然保证任意两个子集间恰有一个公共元素：
{1,2,3}、{1,4,5}、{1,6,7}、{2,4,7}、{3,4,6}、{3,5,7}、{2,5,6}
这一个例子对我们的猜想足以构成威胁：子集数为n真的已经到极限了吗？证明结论有那么容易吗？看来，情况貌似比我们想象中的要复杂得多。
May
18
大学生活混起来很快，不知不觉又是一年过去了。去年5月10日的ACM校内赛给我留下了许多美好的回忆，因此今年我主动去报了名（上次是被人给拖去的）。今年有点装怪，题目数量不变，但时间缩短为4个小时。原计划是从8:00做到12:00，结果可能是因为我们所在的7号机房迟迟没有开门，时间临时改成了8:15到12:15。总的来说，今年的题目比去年要糟糕得多，但也不乏一些精彩的题目。
和去年一样，第一题依旧是所有题目中最科学的一道。题目给定一个不超过2000*2000的网格，你在最左下角的位置（即(0,0)点），你的目的地在(x,y)。要求你的路线不得经过同一个交叉点两次，且不允许左转（题目背景让这个条件顺理成章：街道靠右行，左转不方便），问合法的路线共有多少种。题目难点就是你不一定要走最近的路，完全允许你绕上一大圈；这破坏了有序性，很难构造出递推公式或动态规划模型。稍微画一下图，我们发现了一些显然但很有启发性的规律：每一次右转后，你左手边方向的所有区域都不能再走了，这很可能产生出规模更小的子问题来。另外，所有合法路线必然是有如螺旋线一样的一圈一圈绕着终点走，这种隐藏的有序性也为动态规划提供了可能。但顺着这个思路想下去屡屡碰壁，我猜不少队伍都卡在这儿了吧。
后来我完全打翻前面的全部思路，猛然想到了一个具有决定意义的想法：街道的选取唯一地决定了整个路线。例如，假设我想计算转弯恰好11次的路线有多少条。这样的路线一定含有三条向上走的路、三条向右走的路、三条向下走的路和三条向左走的路。除去第一条路和最后一条路的位置都是确定的，其它的路选在哪一行或者哪一列唯一地决定了整个路线。因此，我们可以用排列组合直接计算出答案来。向上走的路是五选二，向右走的路是七选三，向下走的路是四选三，向左走的路是三选二。把它们各自的选取方案数乘起来就得到了拐弯11次的合法路径。于是，计算所有的路线数只需要从小到大枚举拐弯的次数，每一次计算都是常数的，总复杂度是O(n)的；整个算法的瓶颈反倒是O(n^2)的组合数预处理，不过这个复杂度完全可以承受。
