程序员面试逻辑题解析.pdf

程序员面试逻辑题解析.pdf
 

书籍描述

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

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

作者简介
作者:(美国)萨沙(Dennis E.Shasha) 译者:费若愚 朱学武

萨沙(shasha D.E.),纽约大学柯朗数学研究所计算机科学教授。先后获得耶鲁大学理学学士、雪城大学理学硕士和哈佛大学哲学博士学位。《科学美国人》网站和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 Sman Machines和Acodes,Puzzles,and conspiracy等书。

目录
第一部分智力游戏
第1章竞赛——不可能都是赢家
1.1甜食爱好者
1.2拜占庭赌徒
1.3"碰碰"运气
1.4信息增益
1.5直冲云霄!
1.6政治分肥
1.7社会博弈
1.8猫鼠游戏
1.9流感中的数学
第2章设计——想象力决定一切
2.1冰上历险
2.2最佳术语
2.3巧分弹珠
2.4颜色反转
2.5赛程编排
2.6生物中的分形学
2.7轻松分馅饼
第3章运气——获得幸运之神的垂青
3.1幸运轮盘赌
3.2法律逻辑
3.3筹码盒游戏
3.4反馈系数
第4章推理——你在想什么
4.1数字线索
4.2智力游戏
4.3“拒”中生智
4.4棘手的迷宫
4.5疯狂配比
第5章优化——达到事半功倍
5.1寻找地道
5.2天生一对
5.3概不找零
5.4寂静深海
第6章前5章难题解答
6.1甜食爱好者
6.2拜占庭赌徒
6.3“碰碰”运气
6.4信息增益
6.5直冲云霄!
6.6政治分肥
6.7社会博弈
6.8猫鼠游戏
6.9流感中的数学
6.10冰上历险
6.11最佳术语
6.12巧分弹珠
6.13颜色反转
6.14赛程编排
6.15生物中的分形学
6.16轻松分馅饼
6.17幸运轮盘赌
6.18法律逻辑
6.19筹码盒游戏
6.20反馈系数
6.21数字线索
6.22智力游戏
6.23"拒"中生智
6.24棘手的迷宫
6.25疯狂配比
6.26寻找地道
6.27天生一对
6.28概不找零
6.29寂静深海
第二部分解题密钥
第7章谜题
7.1年龄排位
7.2城市规划
7.3任务调度
7.4海底寻宝
7.5数独
7.6数字编码
7.7选择性贪心
7.8最优包装
7.9重温旅行推销员问题
7.10超载系统的任务调度与冻结晶体
7.11单词接龙
7.12同盟最大化
7.13决胜老虎机
7.14骰子的奥秘
7.15西瓜还是芝麻
第三部分冒险故事
第8章忠诚的敌人

文摘
版权页:

程序员面试逻辑题解析

插图:

程序员面试逻辑题解析

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<50并且D在第四局中说的是实话,那么第五局D就可以说谎,你就无法下注。如果x≥50,那么如果D在第四局中说谎,就算你第五局赢了,也无法恢复到你的起始资金了。因此,如果第三局不下注,你是没办法得到150美元的。
第二种情况假设第三局你押点钱在。上。这样,你的处境就跟第一种情况一样,而且只会更糟。
第三种情况假设第三局你押x美元在1上。我们先考虑x<12.50美元的情况。假设纸上的数字确实是1,并且你在第四局听从了D的建议押上了y美元且x+),<50。那么,假如第四局你赢了,第五局你就不能下注(那时D可以说谎)。反之,如果x+y>50,则y>37.50美元,那么假如第四局你输了,你的钱将少于75美元,就算赢了第五局也得不到l50美元。综上所述,只有x≥12.50,才有可能得到150美元。
假设第三局你押x美元在1上,但是纸上的数字是0。那么你的余额是100—x,并且你推断出B、C和D已经都说过了一次谎。在第四局,B、C和D给出的建议必然是二对一。你赌2美元押在两个顾问说的数字上。那么可以得出x+z≤25;否则,如果第三局和第四局都输了,你的钱将不到75美元,那么在第五局中你不可能拥有150美元了。但这意味着z≤12.50美元,如果第四局你赢了,那时你最多也就有100美元,并且D在第五局还可以说谎。假设第四局你押在一个顾问建议的数字上,其实另外两个顾问倒有可能说的是实话,这样一来,还是有两个顾问只说了一次谎。
因此,你无法保证最后还有150美元。如果更深入地分析,事实上可以推出甚至都不能保证最后还有134美元。伊万·热赞卡(Ivan Rezanka)推导出的结论是可以保证赢133.33美元,但是此题目前还没有任何简洁优美的证明。

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

购买书籍

当当网购书 京东购书 卓越购书

PDF电子书下载地址

相关书籍

搜索更多