昨天我突发奇想，写了几段Mathematica代码，生成了各种排序算法的内存变化图。图中每一个新的横行都表示数组的一次更新，数字大小用颜色来表示。你可以直观地看到这些算法是如何把乱序数组一点一点变为有序的。效果还是很令人满意的，不少算法的内存轨迹都相当美观，相当有艺术性。
图很大，我就不在首页上显示了，大家点“查看更多”看图吧。
算法
IBM Ponder This史上最难谜题：给出谜底猜谜面
2009年2月份IBM Ponder This的谜题可能是从98年谜题月赛开办以来最难的谜题。谜题发布一个月之后仍然没有任何人答对，主办人不得不宣布延迟一个月，并再三增加提示。最终，答对此题的仍然只有7个人。很久没有看到如此精彩的谜题了，有兴趣的网友不妨试一试。
题目非常有趣。传统的谜题是给出谜面求解谜底，但这个谜题则恰恰相反：下面这一串数字是某个问题的答案，你能猜出这个问题是什么吗？这串数字里有一个错误在哪里？
900F 80F0 8F00 80CA BE12 AA90 9400 0048 3E5B 8AC0
3400 00CB BC81 8A08 3C00 0050 BE43 00C0 3E00 A019
8059 BE13 2000 0092 BE9B 2A0B 2A00 8052 8841 04C0
3E00 840B 084B 0098 E000 8819 845A 8012 0300 0050
826F 0500 0600 846E 8264 0900 0A00 8065 0C00 0072
A054 8368 8569 4800 4400 8573 4200 4100 8349 8542
2800 2400 854D 2200 2100 9F00 E000 8888 8444 8000
0030 0DED 8222 0050 0060 8444 8222 0090 00A0 8000
00C0 0DED A000 8333 8555 4080 4040 8555 4020 4010
8333 8555 2080 2040 8555 2020 2010 8300 8500 8030
8050 0880 0840 8050 0820 0810 8030 8050 0480 0440
8050 0420 0410 8500 8030 8050 0280 0240 8050 0220
0210 8030 8050 0180 0140 8050 0120 0110 90F0 9F00
E000 8888 8444 8000 0003 0DED 8222 0005 0006 8444
8222 0009 000A 8000 000C 0DED A000 8333 8555 4008
4004 8555 4002 4001 8333 8555 2008 2004 8555 2002
2001 8300 8500 8003 8005 0808 0804 8005 0802 0801
8003 8005 0408 0404 8005 0402 0401 8500 8003 8005
0208 0204 8005 0202 0201 8003 8005 0108 0104 8005
0102 0101 9F00 8030 8050 8003 8005 0088 0084 8005
0082 0081 8003 8005 0048 0044 8005 0042 0041 8050
8003 8005 0028 0024 8005 0022 0021 8003 8005 0018
0014 8005 0012 0011 80FF 8F0F A333 8000 5000 0DED
8000 3000 0DED A333 C555 1800 1400 C555 1200 1100
8F0F A333 A555 1080 1040 A555 1020 1010 A333 A555
1008 1004 A555 1002 1001
趣题：对全体正整数红蓝二着色使之不含单色无穷等差数列
你认为，是否有可能把全体正整数染成红蓝二色，使得不存在无穷等差数列，数列中的所有数都是一种颜色？如果你认为存在这样的染色方案，请给出一个构造方法；如果你认为不存在，证明之。在看下面的答案之前，不妨先仔细思考一下。
事实上，满足题意的染色方案是存在的，构造方法非常简单，非常直接，非常暴力。显然，无穷等差数列只有可数个，不妨把它们分别叫做A_1, A_2, A_3, …。现在，如果我们能够构造两个数列r_1, r_2, r_3, …和b_1, b_2, b_3…，使得对于每一个i，r_i和b_i都在数列A_i中，并且r数列中的每个数都和b数列中的所有数都不相同。这样，把r数列中的所有数染成红色，把b数列中的所有数染成蓝色（其它未出现的数随意染色），就能保证每个无穷等差数列都包含了至少两种颜色。
而这样的r数列和b数列显然存在，因为每一次选择新的r_i和b_i时，无穷数列A_i中都只有有限个数不能选，因此r_i和b_i永远都有选的。
Update: 地基层网友给出了一个更巧妙、更简单的构造方法：对全体正整数倍长间隔染色，即把1染成红色，2和3染成蓝色，4到7染成红色，8到15染成蓝色……。显然，当染色区间的长度大于公差时，等差数列最终都将一截一截地落在不同的染色区间中。
趣题：理想模型下的排序算法（下）
上次我们谈到，我们考虑时间复杂度时往往假设任意大的整数运算（赋值、四则运算、取余运算、比较运算、位运算包括左移右移）都可以在常数时间内完成，殊不知这留下了一个非常具有研究价值的漏洞：能否利用计算机理想模型中的整数运算，把问题打包成超大整数后并行计算，从而办到一些在普通计算机上无法办到的事情？我们在上一次的文章中介绍了利用“大整数随便算”的漏洞“耍赖”得到了一个线性时间的排序算法。这个漏洞真的已经被充分利用了吗？我们还能从里面榨出多少汁水来？令人无法想象的是，线性时间的排序算法远远没有挖掘到理想大整数运算的巨大潜力，事实上我们能做到常数时间的排序！问题和解答仍然来自Using your Head is Permitted，在这里向Michael Brand表示深深的膜拜。
自然，说“常数时间排序”是有前提条件的，否则即使读入输出也得耗费线性的时间。不过，我们可以假设所有待排序的数都已经打包进一个大整数里，输出时也无需解包，直接返回另一个大整数即可。在这样的情况下，我们完全可以用常数时间完成排序。换句话说，我可以用O(1)的时间，“一下子”就把0100 0111 0001 0010变成0001 0010 0100 0111，不管这个大整数里面装了多少个数。为了方便大家阅读和思考，我们再取一些名字，方便描述。我们把由多个数构成的大整数叫做“整数串”。整数串中所含的数都是二进制，它们用空格隔开。整数串中每个数的位数都必须相等，位数不够用零补足。我们把这个位数叫做“定宽”，本文例子的定宽都是4。
随记：普遍性验证、数学思维、代数基本定理及其它
大学生活的乐趣不光体现在吃喝玩乐上，更重要的是它所提供的自由学习的场所。你可以在网上搜索课表，看看什么时候什么教室有什么牛B课，记在手机中的待办事项中，到时候到那个教室去旁听。旁听的乐趣就在于，你可以去学任何你想学的东西，不用交作业，不用怕点你名，不用记笔记，不用考试，只需要挂个耳朵在那儿听牛B东西就行了。前天一大早就被兔子叫起来，跟着一起去旁听了一节数理逻辑。
课程内容很简单，毕竟也才只讲了两周，一切都是很基础的。老师讲得很好，对联结词、命题公式、真值表等概念都说得很细致，即使完全没接触过这方面东西的人也能弄明白。作为信科的专业课，老师也简单提到了SAT问题：给定一串由AND, OR, NOT, 逻辑变量和括号组成的表达式，是否能给变量取值使得整个表达式为真？如果存在这样的“成真赋值”，我们就称表达式是一个“可满足式”。最简单的例子，p∧q就是可满足的，把p、q都取真即可；p∧(¬p)就不可满足，该式无论如何都为假。判断一个逻辑表达式是否可满足是一个经典的NPC问题，目前除了枚举之外还没有更好的算法。
还有一种逻辑表达式，不管初始值是什么，整个式子恒为真。例如，p∨(¬p)就是永真式。看起来，判定一个式子永真比判定一个式子可满足似乎要困难得多，因为前者比后者要强得多。而事实却是，这两个问题可以（在多项式的时间内）相互转化，它们在复杂程度上并无区别。如果你找到了一种可满足式判定算法，你便立即拥有了永真式判定算法。换句话说，你的算法若能找出一个成真赋值，你就能利用该算法立即得出该式所有赋值结果是否都为真。这个问题的问法很有艺术性，它有意屏蔽掉了永假式判定这一桥梁。事实上，一个表达式要么可满足要么永假，而从永假到永真只有一步之遥——只需要在最前面加一个“非”即可。也就是说，如果有一个程序，它能告诉我逻辑表达式A是否可满足，那么我就把¬A输进去：如果它说¬A不可满足，意即¬A的任何赋值结果均为假，反过来A就是永真的；如果它说¬A可以满足，意即程序找到了¬A的一个成真赋值，反过来便成为了A永真的一个反例。