《啊哈!灵机一动》：程序游戏――关于常规的迷题

小学教育网

　　自从计算机革命开始以来，“算法”一词已成为数学词典中一个熟知的词汇。它就是指一种由一系列限定好的步骤组成的、能够解决问题的程序。当你用一个数字去除另一个大的数字时，你就是用的除法。由于计算机在没有被准确告知如何运行的情况下不能解决问题，因此计算机程序设计技艺主要是编制高效的算法的技艺。我们称“技艺”而不是“技术”，是因为在发现好的算法中，奇妙的“啊哈(AHA)”起着主要的、创造性的作用。
　　“妙”是指一种算法能在最短的时间内解决问题。使用计算机需要花钱，就像雇工干活需要花钱一样。因此，具有高效(好)的算法，就具有很大的实际优势。一种被称为“操作研究”的数学热门分科，就是开发解决复杂问题的最高效方法。
　　尽管本部分的程序问题出于娱乐而作了选择，你还是可以很容易地了解许多深奥的数学概念。如第一个谜题，生动地表明数学家们把两个看似不相关的问题称为“同型”的含义。游艺活动中有关数字的打赌比赛实际上含有与玩“划井游戏”相同的计谋。这与由加拿大数学家利奥?摩瑟发明的聪明的数学游戏以及用于网络系统的游戏是“同型的”。这些游戏的计谋都是基于3―3数字魔方，这是一种最古老的奇妙组合之一。
　　其它包含重要概念的谜题有：解决了河马称重问题的阿基米德浮体定律；在决策理论中尚未解决的诸如分配家务劳动的问题；一些由窃贼或强盗提起的组合问题；一个由“懒惰的情人”提起的重要的曲线理论问题。
　　“曲线理论”是关于曲线连接的一系列点的研究。许多操作研究中的实际问题都可以用曲线表示出来，有些可有简洁的结果。如我们知道的如何用“克拉斯考运算法”排列树的最小间隔。另一个与此密切相关的问题，即“斯坦纳的树排问题”在总体上尚未解决。由于“斯坦纳树”问题有许多实际应用，关于开发解决这一问题的高效计算机运算法的大量研究工作正在进行。
　　斯坦纳的问题属于所谓NP―Complete的一类奇妙问题。这是一些在一定程度上尚未解决的问题。没有已知的好的算法，如果有也还不知道。发现n个点的斯坦纳树的已知最佳算法是这样的，随着n的增加，发现树所需要时间也是呈指数增加。实际上，它增加得如此之快，以致对于一个相对较小数的点(如几百个)，计算机需要用数万年的时间才能得到最佳答案。这类问题以奇妙的方式相互联系，如果发现其中一个问题的高效计算机算法，就可以迅速应用到其它问题上。而且如果算法中的任何一种表明不存在有高效算法，也就为其它算法得出了同样的结论。数学家们认为后者是正确的，大量开发高效算法的工作将发现，没有最佳的“斯坦纳树”，但有接近最佳的。
　　本部分比本书的其它部分要多，其中揭示出了现代数学中某些尖端数学家目前正在研究的许多问题。