程序员面试逻辑题解析

章节摘录

版权页：   插图：   3.如果你可以参加5局，“不总说实话”的顾问5次中必须有4次说实话，另外3位顾问可以随意说谎，在这种情况下，你能保证最后至少还有150美元吗？ 即使是5局，顾问们依然可以让你赢不了多少。他们的策略一开始跟4局时的策略相似。 第一局：A和B说是0，C和D说是1。 结果：纸上的数字是1，A和B说了一次谎。 第二局：A和C说是0，B和D说是1。 结果：纸上的数字是1，A已经说过两次谎了，A肯定是“可以随意说谎”的顾问之一。B和C各说过一次谎。D还没有说过谎。 第三局：B和C说是0，A和D说是1。 现在我们来分情况讨论。 第一种情况 假设第三局你不下注。如果纸上的数字是1，那么你可以推断出D是“不总说实话”的顾问，因为其余的顾问都已经说过两次谎了。然而，D还有可能说一次谎。如果在第四局，D的建议是1，那么押x美元在1上，如果x

前言

　　“我去了一家以出晦涩谜题著称的公司面试，因为上过这门课，那些谜题都不在话下。”　　——鲍里斯（Boris），上过我的谜题课的纽约大学毕业生　　有些人（比如我）喜欢谜题，还有些人觉得必须研究谜题才能在求职面试中取得成功。本书就是为这两种人写的。书中有一些很巧妙的题目，同时我也会教你一些解题技巧，帮助你挑战新的谜题。还有，如果你能解决最后一部分的那些超级难题，还有可能会获得奖励呢。　　很多人反对在面试中采用谜题。他们反对的理由之一便是谜题的场景设置往往不合情理，例如，一个逻辑严谨的人不能发声也不愿写字。好吧，我承认，我也设计过这样的题目，但是我的大部分谜题都源自真实的问题（例如，用偶尔说谎的人来对应偶尔会发生故障的硬件）。在做研究时，我会尝试将遇到的问题抽象成一道谜题，以便认清根本问题，然后再处理表面现象。这个方法非常有效。因此，对我来说，谜题，尤其是那些恰当的好题，也算是通往科学研究和工程实践的光明之路。　　那么，我为什么要编写这些谜题呢？首先，当然是因为它们非常有趣。其次，它们能有效地锻炼脑力。在鲍里斯提到的谜题课上，学生们每周都编写程序，还要比赛。这些程序每个运行两分钟，获胜者可以得到一块奇巧巧克力。我讲课的内容不多，教给他们的技巧在第二部分都能找到。在课程结束时，学生们发现他们解决实际应用问题的能力大大提高了，而这些必须要解决的现实问题往往已经被算法教授打上了“难搞”的标签。我无法明确地告诉你这个神奇的转变是由什么引起的，但是它确实发生了。　　本书第一部分中的多数题目都来自我在Scientific American和Dr. Dobb’s Journal上的谜题专栏，很多读者给予了我至关重要的、充满想象的反馈。这些反馈或者谜题本身引出了一些新的变体，因此即使你曾在杂志中看过这些题目，也需要更为深入地思考。　　曾经有很多次，当不知道要如何解题时（即使是我自己设计的题目也会如此），我会先在纸上打打草稿，做一些尝试。最初的尝试通常是错的，但有时它会启发我找到更好的思路。第一部分的每道题后面都有一些留白，供你打草稿用。　　攻克谜题是需要一定的思维模式的，一开始要天马行空式地发散思维，然后要确定方向缜密有序地找出解决方案——整个过程神似于我们在第2章介绍的“模拟退火”技术。当然我的方法不是唯一的思维模式。其他人告诉我的更好解法，我也很乐意分享给读者。　　第一部分的每一章（很短）都是一道谜题，答案在第一部分的最后。第二部分就几种类型的谜题的解答方式展开探讨，既有徒手计算的也有用计算机解答的。你会在这部分学到多种解题技巧应付那些带有约束条件的谜题，诸如数独、调度问题、数学文字游戏和概率题等。坦率地说，我觉得这些解题技巧也算是一种算法。你要善假于物，随意使用手头的工具。第三部分需要你解开一个涉及密码、银行账号和地理的谜团。数学侦探艾可博士和他的朋友们会陪你一起探险。（你以前可能已经认识了他们。）如果能解开这些谜题，就有可能获奖。　　好好享受吧，祝你好运。　　竞赛信息　　想要参与谜题破解竞赛的读者，请把第三部分所有谜题的答案发到邮箱。　　稿件要求采用Microsoft Word或PDF格式，截止时间是2008年8月31日。本书作者丹尼斯·夏沙（Dennis E. Shasha）是唯一的裁判，他会从所有回答正确的稿件中选出10份。优胜者的奖品是一件Wrox T恤和一顶Wrox棒球帽（或其他等值商品），Wrox出版的3本书（优胜者自行挑选），还有一份“智多星”证书。为了确保收到奖品，参赛者需要在来稿中附上邮寄地址（不能是邮政信箱）。提供法定禁止投送地区的无效。一般配送时间为6到8周。Wiley出版社对于参赛稿的遗失、字迹模糊或残缺不全概不负责。Wiley出版社的员工不得参赛。　　第三部分出现的所有密文可以在网站上下载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链接即可。

媒体关注与评论

"与其他谜题类图书不同，本书独具一格，专为程序员量身打造。个人认为经常做谜题能够改善大脑功能。"                                           --亚马逊读者评论 "阅读本书之前，我真的不知道如何使用动态规划算法。'最优包装'仅用两页纸的篇幅就教会了我。简单而优雅的解答方案让我一年后仍记忆犹新。"         --亚马逊读者评

内容概要

Dennis E. Shasha

纽约大学柯朗数学研究所计算机科学教授，先后获得耶鲁大学理学学士、雪城大学理学硕士和哈佛大学哲学博士学位。《科学美国人》网站和Dr. Dobb’s Journal的谜题专栏作家。除本书外，还著有《奇思妙想：15位计算机天才及其重大发现》、Database Tuning: A Principled Approach、The Puzzling Adventures of Dr. Ecco、Natural Computing: DNA, Quantum Bits, and the Future of Smart Machines 和Codes, Puzzles, and Conspiracy等书。

书籍目录

目 　 　录

第一部分 　智力游戏

第1章 　竞赛——不可能都是赢家　　2

1.1 　甜食爱好者　　3

1.2 　拜占庭赌徒　　5

1.3 “碰碰”运气　　7

1.4 　信息增益　　9

1.5 　直冲云霄！　　11

1.6 　政治分肥　　13

1.7 　社会博弈　　14

1.8 　猫鼠游戏　　17

1.9 　流感中的数学　　19

第2章 　设计——想象力决定一切　　21

2.1 　冰上历险　　22

2.2 　最佳术语　　26

2.3 　巧分弹珠　　28

2.4 　颜色反转　　30

2.5 　赛程编排　　31

2.6 　生物中的分形学　　32

2.7 　轻松分馅饼　　34

第3章 　运气——获得幸运之神的垂青　　36

3.1 　幸运轮盘赌 　　37

3.2 　法律逻辑　　39

3.3 　筹码盒游戏　　42

3.4 　反馈系数　　44

第4章 　推理——你在想什么　　46

4.1 　数字线索　　47

4.2 　智力游戏　　49

4.3 　“拒”中生智　　52

4.4 　棘手的迷宫　　55

4.5 　疯狂配比　　57

第5章 　优化——达到事半功倍　　59

5.1 　寻找地道　　60

5.2 　天生一对　　62

5.3 　概不找零　　65

5.4 　寂静深海　　67

第6章 　前5章难题解答　　68

6.1 　甜食爱好者　　70

6.2 　拜占庭赌徒　　71

6.3 　“碰碰”运气　　73

6.4 　信息增益　　75

6.5 　直冲云霄！　　76

6.6 　政治分肥　　77

6.7 　社会博弈　　78

6.8 　猫鼠游戏　　80

6.9 　流感中的数学　　82

6.10 　冰上历险　　83

6.11 　最佳术语　　85

6.12 　巧分弹珠　　87

6.13 　颜色反转　　89

6.14 　赛程编排　　90

6.15 　生物中的分形学　　91

6.16 　轻松分馅饼　　94

6.17 　幸运轮盘赌　　96

6.18 　法律逻辑　　97

6.19 　筹码盒游戏　　98

6.20 　反馈系数　　103

6.21 　数字线索　　104

6.22 　智力游戏　　105

6.23 　“拒”中生智　　109

6.24 　棘手的迷宫　　111

6.25 　疯狂配比　　112

6.26 　寻找地道　　114

6.27 　天生一对　　117

6.28 　概不找零　　118

6.29 　寂静深海　　119

第二部分 　解题密钥

第7章 　谜题　　124

7.1 　年龄排位　　125

7.2 　城市规划　　127

7.3 　任务调度　　129

7.4 　海底寻宝　　131

7.5 　数独　　136

7.6 　数字编码　　143

7.7 　选择性贪心　　146

7.8 　最优包装　　151

7.9 　重温旅行推销员问题　　154

7.10 　超载系统的任务调度与冻结晶体　　159

7.11 　单词接龙　　165

7.12 　同盟最大化　　168

7.13 　决胜老虎机　　171

7.14 　骰子的奥秘　　174

7.15 　西瓜还是芝麻　　177

第三部分 　冒险故事

第8章 　忠诚的敌人　　182

编辑推荐

知名谜题作家力作，程序员面试题必备.书中从不同角度阐释了各种类型谜题的解题技巧，从广为人知的数独，幸运轮盘，赛程编排，旅行推销员问题到猫鼠游戏，同盟最大化及选择性贪心等。

作者简介

《程序员面试逻辑题解析》共分为3个部分。第一部分从有趣且锻炼头脑的谜题入手，继而给出解题思路和详细答案，更有“热身问题”给大家提供充分的思考空间。第二部分综合了不同类型的谜题，如数独、调度问题及概率题等。神秘的第三部分带领大家不断历险，开动脑筋，解决大量密码及银行账户等方面的问题。几十道简洁的小谜题不仅充分锻炼了我们的思维方式，更为提高面试成功率奠定了基础。《程序员面试逻辑题解析》不仅适合程序员阅读，更是谜题爱好者的饕餮盛宴。

---

 程序员面试逻辑题解析下载 精选章节试读 更多精彩书评

---