我把今天一下午加上一晚上的时间都花在了这个 Flash 小游戏上。这是我所见过的程序设计类 Puzzle 游戏中最好玩的一个。它是真正意义上的程序设计游戏，游戏不但提供了完备的读写和流程控制功能，甚至还引入了随机测试数据。游戏很快就会引入算法的思想，因为玩家渐渐会发现，这些谜题并不是单靠模拟就能解决的；后面的谜题则越发困难，需要相当有技巧性的算法设计，对脑力绝对是一个大挑战。如果你热爱算法与程序设计，你一定会爱上这个游戏的。
编程语言
假如P=NP，世界将会怎样？
在计算机复杂度理论中，P问题指的是能够在多项式的时间里得到解决的问题，NP问题指的是能够在多项式的时间里验证一个解是否正确的问题。虽然人们大多相信P问题不等于NP问题，但人们目前既不能证明它，也不能推翻它。P是否等于NP是计算机科学领域中最突出的问题，在千禧年七大难题中排在首位。科学家们普遍认为P≠NP是有原因的。让我们来看一看，如果哪一天科学家证明了P=NP，寻找一个解和验证一个解变得同样容易，那这个世界将会变得怎样？
已知的NPC难题将全部获解，这将瞬间给各个科学领域都带来革命性的进展。整数规划、01规划、背包问题全部获解，运筹学将登上一个全新的高度；数据库的串行化、多处理器调度等问题也随之解决，大大提高了计算机的性能。同时，空当接龙、扫雷、数独等经典游戏也由于获得了多项式的算法而在很大程度上失去了意义。
算法研究方向将发生全面转移。对算法的研究可能会转向围棋等NP-Hard问题。算法设计的学问与“NP问题统一解”的关系正如小学应用题与列方程解题的关系一样，将成为一种纯粹锻炼思维的游戏。
一些新型的自动编程语言将出现，并将逐渐取代传统的编程语言。这种新型编程语言扮演着一个“判定性/最优化问题万能解决器”的角色。在新的编程语言中，你只需要用代码指明输入数据与输出数据的关系，而无需关心计算输出数据的步骤。只要这种关系是多项式时间内可计算的，编译器将自动找到解法。在新型编程语言的支持下，人们唯一需要考虑的是，如何把实际问题转化成数学模型。
Code Golf：比比谁写的代码最短
在网上闲逛时发现了这么一个有趣的网站。Code Golf是一个另类的编程挑战网站。这个网站定期发布一个编程题目，你所提交的代码越短越好（keystroke越少越好，就像Golf一样要求尽可能少的stroke）。目前网站支持Perl、PHP、Python和Ruby语言。
Light-Bot：一个编程启蒙游戏
Stetson MM给我推荐的一个Flash小游戏。挺适合给完全没有学过编程的人了解一下什么是“程序设计”。
给个链接：http://armorgames.com/play/2205/light-bot
趣题：量子计算机、另类编程语言和幂函数的解释
很久没有更新和信息学有关的东西了。今天和大家分享一个非常有趣的题目，我已经很久没看见如此精彩有趣的题目了。为了引入这个问题，我们先来介绍一个假想的编程语言QCPL。就像LISP一样，它是一个基于函数的语言：没有变量，没有for循环，一切东西都是用函数来表示的。另外，就像FORTRAN一样，QCPL语言不支持递归，也就是说一个函数不能递归地调用自己。QCPL的另一个有趣的特点是，所有的函数都只能返回一个Boolean值。比如说，下面这个函数的作用就是判断x+2和y+2的乘积是否等于z：MULT_PLUS_TWO(x,y,z): (x+2)*(y+2)=z
QCPL也有逻辑运算符。事实上，QCPL里的合法运算符一共只有8个，其中6个分别如下：
运算符 | 作用 | 输入 | 输出
——-+——–+—————+—————
+ | 相加 | 两个自然数 | 一个自然数
* | 相乘 | 两个自然数 | 一个自然数
= | 等于 | 两个自然数 | 一个Boolean值
& | 逻辑和 | 两个Boolean值 | 一个Boolean值
| | 逻辑或 | 两个Boolean值 | 一个Boolean值
! | 逻辑非 | 一个Boolean值 | 一个Boolean值
另外两个运算符就要重点介绍了。这是QCPL语言真正牛B的地方——它是专门为量子计算机设计的！你可以让这台计算机平行地穷尽完某些变量所有可能的取值，这一切仅仅在一瞬间内就可以完成。这两个特殊的运算符（以后我们管它们叫做“定量运算符”）就是专门用来干这件牛B事的："Ex"是“存在性定量运算符”，表示让计算机找出是否存在一个满足表达式的自然数x；"Ax"是“通用性定量运算符”，用于询问计算机该表达式是否对所有的自然数x均成立。比如，运用定量运算符，我们可以立即写出素数/合数判断函数：COMPOSITE(n): Ex,Ey,MULT_PLUS_TWO(x,y,n)
PRIME(n): !(COMPOSITE(n)|n=0|n=1)
其中，Ex,Ey,MULT_PLUS_TWO(x,y,n)的意思就是说，是否存在某一对x和y，使得MULT_PLUS_TWO(x,y,n)为真。只要（某一个平行世界里的）计算机找到了任何一对满足条件的x和y，整个COMPOSITE(n)立即返回True。如果对于所有的自然数x和y，MULT_PLUS_TWO(x,y,n)都不可能为真时，整个函数才返回False。别忘了这是一台量子计算机，穷举的过程可以在一瞬间内完成。
好了，下面我们再给出几个基本的函数。函数SUM用于计算x加y是否等于z，而函数PRODUCT则用于检验x乘以y是否等于z：SUM(x,y,z): x+y=z
PRODUCT(x,y,z): x*y=z
现在，你的任务就是写出一个函数POWER(x,y,z)，当且仅当x的y次方等于z时函数才返回True。相信我，这道题没有那么容易。
Read more…