前言

“我去了一家以出晦涩谜题著称的公司面试,因为上过这门课,那些谜题都不在话下。”

——鲍里斯(Boris),上过我的谜题课的纽约大学毕业生

有些人(比如我)喜欢谜题,还有些人觉得必须研究谜题才能在求职面试中取得成功。本书就是为这两种人写的。书中有一些很巧妙的题目,同时我也会教你一些解题技巧,帮助你挑战新的谜题。还有,如果你能解决最后一部分的那些超级难题,还有可能会获得奖励呢。

很多人反对在面试中采用谜题。他们反对的理由之一便是谜题的场景设置往往不合情理,例如,一个逻辑严谨的人不能发声也不愿写字。好吧,我承认,我也设计过这样的题目,但是我的大部分谜题都源自真实的问题(例如,用偶尔说谎的人来对应偶尔会发生故障的硬件)。在做研究时,我会尝试将遇到的问题抽象成一道谜题,以便认清根本问题,然后再处理表面现象。这个方法非常有效。因此,对我来说,谜题,尤其是那些恰当的好题,也算是通往科学研究和工程实践的光明之路。

那么,我为什么要编写这些谜题呢?首先,当然是因为它们非常有趣。其次,它们能有效地锻炼脑力。在鲍里斯提到的谜题课上,学生们每周都编写程序,还要比赛。这些程序每个运行两分钟,获胜者可以得到一块奇巧巧克力。我讲课的内容不多,教给他们的技巧在第二部分都能找到。在课程结束时,学生们发现他们解决实际应用问题的能力大大提高了,而这些必须要解决的现实问题往往已经被算法教授打上了“难搞”的标签。我无法明确地告诉你这个神奇的转变是由什么引起的,但是它确实发生了。

本书第一部分中的多数题目都来自我在Scientific AmericanDr. Dobb's Journal上的谜题专栏,很多读者给予了我至关重要的、充满想象的反馈。这些反馈或者谜题本身引出了一些新的变体,因此即使你曾在杂志中看过这些题目,也需要更为深入地思考。

曾经有很多次,当不知道要如何解题时(即使是我自己设计的题目也会如此),我会先在纸上打打草稿,做一些尝试。最初的尝试通常是错的,但有时它会启发我找到更好的思路。第一部分的每道题后面都有一些留白,供你打草稿用。

攻克谜题是需要一定的思维模式的,一开始要天马行空式地发散思维,然后要确定方向缜密有序地找出解决方案——整个过程神似于我们在第2章介绍的“模拟退火”技术。当然我的方法不是唯一的思维模式。其他人告诉我的更好解法,我也很乐意分享给读者。

第一部分的每一章(很短)都是一道谜题,答案在第一部分的最后。第二部分就几种类型的谜题的解答方式展开探讨,既有徒手计算的也有用计算机解答的。你会在这部分学到多种解题技巧应付那些带有约束条件的谜题,诸如数独、调度问题、数学文字游戏和概率题等。坦率地说,我觉得这些解题技巧也算是一种算法。你要善假于物,随意使用手头的工具。第三部分需要你解开一个涉及密码、银行账号和地理的谜团。数学侦探艾可博士和他的朋友们会陪你一起探险。(你以前可能已经认识了他们。)如果能解开这些谜题,就有可能获奖。

好好享受吧,祝你好运。

竞赛信息

想要参与谜题破解竞赛的读者,请把第三部分所有谜题的答案发到shasha@courant.nyu.edu。

稿件要求采用Microsoft Word或PDF格式,截止时间是2008年8月31日。本书作者丹尼斯·夏沙(Dennis E. Shasha)是唯一的裁判,他会从所有回答正确的稿件中选出10份。优胜者的奖品是一件Wrox T恤和一顶Wrox棒球帽(或其他等值商品),Wrox出版的3本书(优胜者自行挑选),还有一份“智多星”证书。为了确保收到奖品,参赛者需要在来稿中附上邮寄地址(不能是邮政信箱)。提供法定禁止投送地区的无效。一般配送时间为6到8周。Wiley出版社对于参赛稿的遗失、字迹模糊或残缺不全概不负责。Wiley出版社的员工不得参赛。

第三部分出现的所有密文可以在www.wrox.com网站上下载Microsoft Word版本。进入网站后,在搜索框内输入书名或ISBN号(978-0-470-12168-9)即可查到此书,然后在详细信息页面上单击下载链接,便能获得所有密文。

p2p.wrox.com

我们也邀请你在p2p.wrox.com网站的P2P论坛上发表书中谜题的变体,或是提供其他的解决方案。这些论坛是一个基于Web的系统,读者可以在上面发布与Wrox图书相关的消息和相关技术,与其他读者和技术用户交流心得。论坛还提供了订阅功能,只要论坛上发布了你感兴趣的新话题,我们就会发电子邮件告知你。Wrox的作者、编辑、其他业界专家和读者都会出现在这些论坛上。

http://p2p.wrox.com上,你会发现很多不同的论坛,它们不仅有助于阅读此书,还有助于你开发自己的应用程序。加入论坛的步骤如下。

  1. 登录p2p.wrox.com网站,单击“注册”(Register)链接。

  2. 阅读用户使用条款,然后单击“同意”(Agree)。

  3. 填写必要的注册信息以及愿意提供的选填信息,并单击“提交”(Submit)。

  4. 你会收到一封电子邮件,告诉你如何确认注册账户并完成注册过程。

浏览论坛无需注册,但只有注册后才能发帖。

加入论坛之后就可以发帖和回帖了,你可以随时访问站点读取信息。如果想要以邮件的形式订阅某个特定论坛的更新,可以单击论坛名旁边的“订阅此板块”(Subscribe to this Forum)的图标。

欲详细了解Wrox P2P的使用方法,一定要查看P2P FAQ,获取关于论坛软件运行方式及P2P和Wrox图书的常见问题的解答。要查看FAQ,在任意一个P2P页面上点击FAQ链接即可。

目录