今天是10月25日。祝古汉MM生日快乐。
曾经有一段时间这个Blog的访问量和订阅量剧增，后来才知道因为这个Blog上的一道牛B题目被出成POJ的月赛题了。那道题目真的很好玩，题目和解答都很简单有趣。其实我挺喜欢这种“给出一个算法并证明该算法最优”类型的数学题目。这里再和大家分享一个类似的比较老的题目，有兴趣的话不妨先想想再看答案。
一次“交换”操作是指将数列中的两个数位置对换。我们假设，互不相交的若干个交换操作可以一次同时进行；换句话说，如果k个交换中任两个都不会对同一个数进行操作，那么这k个操作可以并行完成。例如，在数列
10, 6, 8, 5, 2, 3, 1, 4, 7, 9
中，我们可以同时交换第4个数和第6个数，第8个数和第9个数，以及第3个数和第7个数。经过这一次“并行交换”后，数列变为：
10, 6, 1, 3, 2, 5, 8, 7, 4, 9
任意给定一个长度为n的全排列，请问对该序列进行排序最坏情况下需要多少次并行交换？给出一种具体的算法，说明这个次数足够了；并且给出一种最坏情况，证明这个次数是必需的。
上周六的离散数学课上，我学到了一个比较有趣的东西：有序对的定义。在引入有序对之前，所有的东西都是以集合为基础的；因此当我们讨论到有序对的概念时，我们只能用集合的语言去描述它。如何用集合来叙述有序对<a,b>，使得<a,b>=<c,d>当且仅当a=c且b=d呢？集合本身的无序性给我们带来了相当大的困难。比如，大多数人可能会想到<a,b>:={a,{b}}。可惜这种定义方法是错误的。考虑集合{ {1}, {2} }，则它既可以是<{1},2>，又可以表示<{2},1>。那么定义<a,b>:={a,{b,Ø}}呢？这样也不行，道理是一样的，{{1,Ø}, {2,Ø}}既可能是<{1,Ø},2>，又可能是<{2,Ø},1>。那么，到底应该怎样定义有序对呢？如何定义最简单呢？
高中一次英语课上，英语老师问我们，如果你有机会乘坐时光机回到过去，你想利用这次机会来干啥。“人上一百，形形色色”这句老话得到了完美的验证。什么“回去看看四大美女”呀、“看看金字塔是怎么建造的”呀、“回到三年前的那个风雨交加的夜晚握住她的手深情地告诉她其实我不想让你离开我你知道你走了之后我有多么痛苦吗”之类的东西，各种稀奇古怪的想法都被我们说了个遍。我还记得当时我说的啥——一个无比实用的雕虫小技。我说，我就想回到一个星期前，然后去买彩票。发明一个新东西并不是关键，关键是你怎么去使用它。
最奇怪的幻想总是来自于最奇怪的需求。大家有过这种经历吗？看到自己写的程序运行了半天都还没有任何结果，于是开始纠结，到底是再等一会儿呢还是强行终止了检查一下看程序写错没；犹豫了半天决定杀掉进程后，检查了半天又发现程序没有写错。于是开始怨念，早知道程序没有死循环的话刚才就多等一会儿了。此时，你会突然开始幻想，有没有什么编译器能够事先告诉你你的程序是否会无限运行下去？虽然编程判断一段代码是否会无限执行下去很可能会相当的困难，但我们仍然不排除会有某个天才程序员想出了一个比三角恋爱更加复杂的算法，花它五年的功夫为他心爱的编译器写出了这样一个强大的插件。为什么不可能呢？这个东西看上去似乎比时光旅行机更现实一些。或许我们会在某个科幻电影中看到，一个程序员在黑黢黢的屏幕上输入了几个数，敲了一下回车，然后屏幕上立即用高亮加粗字体显示“警告：该输入数据会导致程序无限运行下去，确定执行？(Y/N)”。如果有一天，这一切真的成为了现实，那么你能利用这个玩意儿来做些什么实用的、有价值的事情？如果我说你能靠这玩意儿发大财你相信么？
有时候，一个看似更加复杂的问题反而有一个更简单的解答。
四色问题是说，对一个平面地图进行染色，要想用不同的颜色来区别相邻的区域，最少需要多少种颜色。在很长一段时间里，人们猜想，只要四种颜色就足够了；但这个“四色猜想”却怎么也证不出来。直到上世纪70年代，“四色猜想”才在计算机的帮助下获得证明。在《从一到无穷大》一书中，作者提到了这样一个有趣的事实：平面上的四色问题一直是一个相当复杂的难题，然而有意思的是，在环面上的染色问题却只需要短短十几行文字就能得出一个完美的结论。下面我们来说明，给一个游泳圈上任意划分出来的区域进行染色，为了使相邻区域不同色，只需要7种颜色就够了。
为了证明这一点，我们只需要说明，在一个环面图中总能找到一块区域，它的邻域不超过6块。如果真是这样的话，余下的部分用数学归纳法就直接证到了：对于一个有n个区域的图，我们找出它的一个邻域数量不超过6的区域，然后把这块区域缩小为一个点，使整个图的区域个数减少到n-1。按照我们的数学归纳，这个有n-1个区域的图是可以7染色的；并且显然地，把第n个区域添加回去后所产生的图仍然可以7染色，因为我的邻域不超过6个，我总能找一个和这些邻域都不一样的颜色。
现在的问题就是，为什么总存在邻域数量不超过6的区域呢？注意到在环面上，有V+F-E=0，其中V表示顶点数，F表示区域数，E表示边的总条数。注意到每个顶点都发射出了至少三条边，即所有顶点引出的边数至少为3V；但每条边都被重复计算了一次（因为一条边有两个端点），因此3V/2≤E，即3V≤2E。代入V+F-E=0，得到E≤3F。假设每个区域都有7个或7个以上的邻域，那么它们将产生至少7F条边；但每条边都被重复计算了一次（因为每条边都为两块区域共享），因此7F/2≤E，即7F≤2E。于是，2E≥7F>6F≥2E，矛盾。
记得当年搞NOIp时，我犯过一个相当严重的错误：错误地把Floyd算法的i, j, k三层循环的位置顺序搞颠倒了。直到准备省选时我才突然意识到，Floyd算法应该最先枚举用于松驰操作的那个“中间变量”k，表示只经过从1到k的顶点的最短路；而我却一直习惯性地以为i, j, k应该顺次枚举。令人惊讶的是，这个错误跟了我那么久我居然从来都没有注意到过。后来，我发现有我这种经历的人不止一个。惯性思维很可能会让你接受一些明显错误的算法，并且让你用得坦坦荡荡，一辈子也发觉不了。
假使你需要把一个数组随机打乱顺序进行重排。你需要保证重排后的结果是概率均等、完全随机的。下面两种算法哪一种是正确的？其中，random(a,b)函数用于返回一个从a到b（包括a和b）的随机整数。
1. for i:=1 to n do swap(a[i], a[random(1,n)]);
2. for i:=1 to n do swap(a[i], a[random(i,n)]);