Matrix67 |
2010-02-24 20:09 | 
给大家看一个好玩儿的东西。在不同的显示器上，下面这张图片的显示效果可能大不相同。如果你用的是 TFT 屏幕，上下移动你的脑袋，调整你的视角，你也会看到不同的色彩。从低处往上看，你会看到一个白色的 MM 站在蓝色背景中；从高处往低看，你会看到一个黑色的 MM 站在黄色背景中。
现在，把上面这幅图片保存下来，用你最爱的图象处理软件打开，然后缩放到原图的 50% 。左图是图片缩小后理应得到的结果，但你会发现，你得到的结果是右边的这个图——一片灰色。
Jan
31
数学、物理、化学、生物等基础学科虽然对人类的生产生活贡献很大，但并不是每个人每一天都会用到。另一些学科则与每个人的生活都有着密切的联系，但人们往往并没有意识到。其中有三门学科尤其贴近人们的生活：经济学、统计学和信息学。这三门学科从不同的角度解析生活中的种种现象，代表了三种不同的科学思维方式，是人生中的三门必修课。很可惜，并不是所有人都有机会一睹这三门学科的风采，即使理解它们并不需要太多的基础知识。
我很高兴地看到，最近市面上出现了一些与统计学和经济学相关的普及读物。它们以浅显易懂的文字向读者揭示事物背后的科学道理，让每个人都有机会领略到统计学和经济学的魅力。但是，我目前还没找到任何一本与信息学相关的普及读物。于是，我萌生了自己写一本信息学普及读物的念头。我想把自己近几年来对算法的感悟写下来，让越来越多的人体会到算法的科学性、趣味性和实用价值。
这里特别要感谢周筠老师和徐定翔老师，是你们的支持和鼓励才让我真正下定了写书的决心。当然，还要感谢长期支持这个网站的网友们。在以后的写作过程中，我可能会有偿向大家征集好的建议和主意，希望能够靠众人的力量收获最巧妙、最有趣、具原创性的点子。
Dec
7
IBM Ponder This上个月的题目比较有趣：我在心里面想一个2到166之间的整数（包括2和166），你的任务是用尽可能少的是非问句（我只能回答是或者否）猜出这个数除1以外的最小约数是多少。
(1) 寻找一种策略使得在最坏情况下猜到答案的询问次数最少。
(2) 寻找一种策略使得在平均情况下猜到答案的期望询问次数最少。
第一个问题很容易回答。虽然2到166之间的整数一共有165个，但它们的最小约数（以后我们说的“最小约数”都是指的不包括1的最小约数）只有38种。因此，事实上你只需要用二分法在38个可能的答案当中找出一个就可以了。由于2^5=32，2^6=64，因此最坏情况下需要6次询问才能保证猜到。
真正困难的是后面一个问题：要想让平均猜测次数尽可能少，我们该从哪里入手呢？
Nov
17
在计算机复杂度理论中，P问题指的是能够在多项式的时间里得到解决的问题，NP问题指的是能够在多项式的时间里验证一个解是否正确的问题。虽然人们大多相信P问题不等于NP问题，但人们目前既不能证明它，也不能推翻它。P是否等于NP是计算机科学领域中最突出的问题，在千禧年七大难题中排在首位。科学家们普遍认为P≠NP是有原因的。让我们来看一看，如果哪一天科学家证明了P=NP，寻找一个解和验证一个解变得同样容易，那这个世界将会变得怎样？
已知的NPC难题将全部获解，这将瞬间给各个科学领域都带来革命性的进展。整数规划、01规划、背包问题全部获解，运筹学将登上一个全新的高度；数据库的串行化、多处理器调度等问题也随之解决，大大提高了计算机的性能。同时，空当接龙、扫雷、数独等经典游戏也由于获得了多项式的算法而在很大程度上失去了意义。
算法研究方向将发生全面转移。对算法的研究可能会转向围棋等NP-Hard问题。算法设计的学问与“NP问题统一解”的关系正如小学应用题与列方程解题的关系一样，将成为一种纯粹锻炼思维的游戏。
一些新型的自动编程语言将出现，并将逐渐取代传统的编程语言。这种新型编程语言扮演着一个“判定性/最优化问题万能解决器”的角色。在新的编程语言中，你只需要用代码指明输入数据与输出数据的关系，而无需关心计算输出数据的步骤。只要这种关系是多项式时间内可计算的，编译器将自动找到解法。在新型编程语言的支持下，人们唯一需要考虑的是，如何把实际问题转化成数学模型。
Aug
27
Aug
18
在网上偶然看到这篇文章，决定把之前创作排序算法内存状态演示图所用的Mathematica程序修改一下，于是搞出来5个midi音乐。这些midi文件用音高来表示内存状态，初始时的音都是乱的，然后声音渐渐变得有序，最后就成了从低到高的一串音符。
http://www.matrix67.com/data/bubble_8_elements.mid
http://www.matrix67.com/data/insert_8_elements.mid
http://www.matrix67.com/data/select_8_elements.mid
http://www.matrix67.com/data/quick_12_elements.mid
http://www.matrix67.com/data/bogo_6_elements.mid
哪位兄弟能推荐一个在线放midi文件的好方法？
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)的组合数预处理，不过这个复杂度完全可以承受。
May
10
昨天和老朋友BY一起吃饭时又一次不可避免地谈到了算法问题。一个有趣的话题是：提起那些最巧妙的、最离奇的牛B算法时，你想到的第一个算法题是什么？
我第一想到的算法题是那道经典问题：n个数中有且仅有一个数出现了奇数次（其它数都出现了偶数次），如何用线性时间常数空间找出这个数。解法也只有一句话：从头到尾异或一遍，结果就是要求的那个数。该问题的加强版也异常牛B，我曾经在这里介绍过。不过，这个算法我在茶余饭后已经聊过无数次了……
脑海中出现的另一个牛B算法题则是POJ3318：给你三个n*n的矩阵A、B、C，问你A*B是不是等于C。数据保证O(n^3)铁定超时，因此你需要想一个不用把A和B乘起来就可以验证的算法。一个基于概率的算法是随机生成一个n乘1的矩阵R，然后判断A*B*R是否等于C*R，而前者相当于A*(B*R)，与后者一样都可以在O(n^2)的时间里算出来。如果算出来的结果相等，几乎可以肯定A*B和C也是相等的。
