书名:像程序员一样思考(修订版)
ISBN:978-7-115-38339-6
本书由人民邮电出版社发行数字版。版权所有,侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用,未经授权,不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟,与我们共同保护知识产权。
如果购买者有侵权行为,我们可能对该用户实施包括但不限于关闭该帐号等维权措施,并可能追究法律责任。
V. Anton Spraul讲授入门级编程和计算机科学已经超过15年。本书凝聚了他在多年的开发经历中所提炼的经验和技巧,并在面向许多遭遇瓶颈的程序员的一对一指导中收到了良好的效果。他还是《Computer Science Made Simple》(Broadway)的作者。
徐波,浙江宁波人,熟悉C和C++、Java等语言。2002年开始从事计算机技术图书翻译。徐波技术视野广阔,翻译文笔优美。翻译有《C专家编程》、《C和指针》等。
Simplified Chinese-language edition copyright © 2015 by Posts and Telecom Press.
Copyright © 2012 by V.Anton Spraul. Title of English-language original: THINK LIKE APROGRA MMER,ISBN-13:978-1-59327-424-5, published by No Starch Press.
All rights reserved.
本书中文简体字版由美国No Starch 出版社授权人民邮电出版社出版。未经出版者书面许可,对本书任何部分不得以任何方式复制或抄袭。
版权所有,侵权必究。
编程的真正挑战不是学习一种语言的语法,而是学习创造性地解决问题,从而构建美妙的应用。本书分析了程序员解决问题的方法,并且教授你其他图书所忽略的一种能力,即如何像程序员一样思考。
全书分为8章。第1章通对几个经典的算法问题切入,概括了问题解决的基本技巧和步骤。第2章通过实际编写C++代码来解决几个简单的问题,从而让读者进一步体会到问题解决的思路和应用。第3到7章是本书的主体部分,分别探讨了用数组、指针和动态内存、类、递归和代码复用来解决问题的途径和实际应用。最后,第8章从培养程序员思维的角度,进行了总结和概括,告诉读者如何才能像程序员一样思考。
本书选取的话题切中程序员的痛点,针对他们最容易陷入挣扎的领域展开讨论,引发思考。每章后面都给出一些编程习题,使得读者能够应用该章所讨论的概念,训练和提升问题解决的能力。
本书适合初级到中级的程序员用来提升自己的问题解决能力和应用编程技能的能力,也适合计算机相关专业的学生作为参考书阅读。
没有一本书只通过一位作者就可以完成,在本书的写作中,我得到了很多人的帮助。
我非常感谢No Starch出版社的每位工作人员,尤其是Keith Fancher和Alison Law,他们在本书的出版过程中担任了编辑、策划和指导工作。我还必须感谢Bill Pollock,正是他与我签订了本书的合同,我希望他能够像我一样对本书的质量感到满意。No Starch出版社的伙计们与我交流时表现出了从不消减的热心和诚恳。我希望有朝一日能够在私下里与他们会面,看看他们把公司网站上的卡通阿凡达装配成什么样了。
Dan Randall作为技术编辑,他的工作非常出色。他还提出了大量技术之外的意见,帮助我在许多地方完善了手稿的质量。
在我的家庭里,生命中最重要的人Mary Beth和Madeline让我感受到爱、支持和热情,特别是为我提供了充足的写作时间。
最后,我还要感谢多年以来曾经听我讲授编程的学生们:感谢让我成为你们的老师。本书所描述的技巧和策略是在我们共同努力的过程中发展成型的。我希望我们能够让下一代程序员的学习旅程变得轻松一些。
你是否在编写程序时感受到挣扎,即使觉得已经理解了自己所使用的编程语言?你是否阅读了一本编程书籍的某一章并能够顺利理解,却无法把自己所读到的东西应用于程序中?你是否能够理解自己在线所阅读的一个程序,甚至能够把每行代码所完成的任务告诉其他人,但是自己在接到一个编程任务后,却面对文本编辑器的空白屏幕大脑一片空白?
并不是只有你才这样。我从事编程教学已经超过15年,几乎所有的学生都在某种程度上符合上面的描述。我们称之为缺乏问题解决能力。所谓问题解决能力,就是根据问题描述编写一个原创程序来解决这个问题。并不是所有的编程任务都需要深入的问题解决能力。如果只是对一个现有的程序进行微小的修改、调试或添加测试代码,这类编程在本质上是机械的,不会对我们的创造力提出多大的挑战。但是,所有的程序总会在某个时刻需要解决问题,所有优秀的程序员都需要具备解决问题的能力。
解决问题是非常困难的。但有些人确实使它变得非常轻松,因为他们天赋异禀,就像迈克尔 • 乔丹这样的体育天才一样。对于这帮天才,高级的思路几乎可以毫不费力地转换为源代码。用Java的一个比喻来说,他们的脑子天生就像能执行Java代码一样,而绝大多数人只能通过虚拟机来解释代码。
没有超常天赋对于成为程序员而言并不是致命的。如果真是如此,世界上也就没有多少程序员了。但是,我看到过许多值得尊重的学习者却在挫折面前挣扎太久。最坏的情况是,他们完全放弃了编程,认为自己永远成不了程序员,觉得只有天赋异禀的人才能成为优秀的程序员。
学习解决编程问题为什么这么困难呢?
部分原因是解决问题是一种与学习编程语言不同的活动,它使用了一组不同能力的“肌肉”。学习编程的语法、阅读程序、记忆应用程序编程接口的元素,这些都是分析性的“左脑”活动。使用以前所学会的工具和技巧编写一个原创程序却是创造性的“右脑”活动。
假设我们想拿走掉落在自家房顶上的其中一条雨槽内的一根树枝,但是自家的梯子却不够长,够不着那根树枝。我们会跑到自己家的车库,寻找某样东西来帮助我们拿走雨槽上的树枝。有没有办法使梯子加长呢?我们站在梯子上时能不能手持某样东西来抓住或拔掉树枝?或许我们可以从某个位置爬上屋顶拿走树枝。解决问题是一种创造性的活动。不管你是否相信,在设计自己的原创程序时,我们的智力活动过程与想方设法从雨槽中拿走树枝的过程非常相似,但与调试一个现有的for循环的过程却截然不同。
但是,绝大多数编程书籍却把重点放在语法和语义上。学习编程语言的语法和语义是极为重要的,但这只是学会用这种语言进行编程的第一个步骤。在本质上,大多数面向新手的编程书籍所讲述的是怎样阅读程序而不是怎样编写程序。把重点放在怎样编写代码上的书籍常常是有效的“烹调书”,因为它们讲述在特定情况下所使用的特定“菜谱”。这种书籍对于节省时间而言是极有价值的,但它们并不是通往学会编写原创代码的正确道路。考虑原始意义上的烹调书。尽管优秀的厨师拥有自己的烹调书,但没人依靠烹调书就能成为优秀的厨师。优秀的厨师理解配料、备菜方法和烹饪方法,并知道怎样把它们组合在一起烹制美味佳肴。优秀的厨师在烹制美味时所需要的只是工具完备的厨房。同理,优秀的程序员理解语言的语法、应用程序框架、算法和软件工程原则,并知道怎样把它们结合起来创建优秀的程序。为优秀的程序员准备一个需求规范列表,给他一个功能齐全的开发环境,他就能创造优秀的程序。
一般而言,当前的编程教育并没有在解决问题这个领域提供太多的指导。相反,如果程序员可以使用所有的编程工具并按要求编写足够的程序,最终他们将学会编写这些程序并且完成得很好。这种说法并没有错,但是“最终”可能意味着相当长的时间。从蹒跚学步到初窥门径的道路上可能充满挫折,有太多的人信心满满地开始了旅程,却倒在了半途中。
我们并不一定要饱经磨难才能获得成功,而是可以用一种系统的方式来学习怎样解决问题,这正是本书的核心所在。我们可以学习对自己的想法进行组织的技巧、解决方案的发现过程以及对某些类型的问题所实行的策略。通过研究这些方法,我们可以释放自己的创造力。不要弄错了:编程,尤其是解决问题,是一种创造性的活动。创造性是神秘的,没人能够准确地说出创造性是怎样发挥作用的。但是,如果我们能够学会怎样作曲、能够领会别人所提出的有关写作创造能力的建议或者能够学会绘画,我们也可以学会怎样有创造力地解决编程问题。本书并不是讲述具体的做法,而是帮助读者开发属于自己的问题解决天赋,明白自己应该怎么做。本书的目的是帮助读者成为自己心目中的程序员。
我的目标是让本书的读者学会怎样用系统性的方法完成每个编程任务,并坚信自己最终能够解决一个特定的问题。当读者完成本书的学习时,我希望你能够像程序员一样思考,并坚信自己已经是个程序员。
在解释了本书的必要性之后,我还需要对本书将讨论的内容和不会讨论的内容进行一些说明。
预备条件
本书假设读者已经熟悉了C++的基本语法和语义,并且已经编写过一些程序。本书的大部分章节将预计读者已经了解了特定的C++基础知识。这些章节将从对这些基础知识的回顾开始讨论。如果读者还在学习语言的基础知识阶段,也不必担心。关于C++的语法有大量优秀的书籍可供参考,在学习解决问题的同时学习语法也是没有问题的。在尝试解决每章后面的习题之前,要保证自己已经学会了相关的语法。
所选择的话题
本书所覆盖的话题代表了我所看到的程序员新手最容易陷入挣扎的领域。它们还代表了初级和中级编程中许多跨领域的话题。
但是,我应该强调,这并不是一本用于解决特定问题的算法或模式的“烹调书”。尽管后面的章节讨论了怎样使用广为人知的算法或模式,但这本书并不适合作为解决特定问题的参考书,所以读者不应该只把注意力集中在直接与自己当前所面临的问题相关的章节中。反之,读者应该从头研读全书,暂时只跳过那些由于缺乏预备知识而无法直接学习的内容。
编程风格
这里简单概述一下本书所使用的编程风格:本书并不追求高性能的编程,并不苛求产生最紧凑、最高效的代码。我为源代码例子所选择的风格是把容易理解作为首要的考虑因素。在有些情况下,我会采用多个步骤完成那些实际上只用一个步骤就可以完成的任务,其原则就是为了进行清晰的说明。
本书也会讨论编程风格的相关内容,但只是比较宽泛的问题,例如类里面应该包含什么或者不包含什么,而不会讨论细节的问题,例如代码应该怎样缩进。作为学习中的程序员,读者当然想要在自己的所有工作中采用一致的、容易阅读的风格。
习题
本书包含了一些编程习题,但本书并不是教科书,因此读者不会在书末找到这些习题的答案。这些习题为读者提供机会应用当前章节所讨论的概念。尝试完成哪些习题当然是由读者自行决定的,但是把书中所讨论的概念应用于实践是至关重要的。简单地完成全书的阅读并不能让自己的水平得到长进。记住,本书并不是告诉读者在每个解决方案中应该怎样做。在应用本书所展示的技巧时,读者能够通过拓展自己的能力来发现需要完成什么任务。而且,成功地完成这些习题也能促进本书的另一个基本目标,就是增加读者的自信心。事实上,有一种很好的方法能够知道读者是否充分地完成了一个特定问题领域的习题,那就是当读者对解决这个领域的其他问题充满信心之时。最后,编程习题应该是充满乐趣的。虽然有时候读者可能觉得辛苦而想做些其他事情,但是完成编程习题应该是一项充满回报的挑战。
读者应该把本书看成是大脑的一项障碍训练。障碍训练可以增强力量、毅力和敏捷性,为训练者培养信心。通过阅读全书并把书中所讨论的概念应用于尽可能多的习题中,可以增强信心并培养能够用于任何编程情况的问题解决技巧。在未来,当读者面临一个难题时,就会知道应该怎样克服它。
为什么用C++
本书的编程例子是用C++编写的。由于本书的主题是怎样解决编程问题而不是专门讨论C++的,因此书中不会出现关于C++特定的提示或技巧,并且本书所讨论的基本概念也适用于任何编程语言。然而,我们无法在不讨论具体程序的情况下讨论编程,因此必须选择一种特定的语言。
选择C++的原因有几方面。首先,它在许多问题领域都是非常流行的一种语言。其次,它的来源是严格的过程性语言C,因此C++的代码既可以采用过程性的惯用法,也可以采用面向对象的惯用法。面向对象编程现在已经极为常见,在讨论解决问题时不可能忽略它,但是许多基本的问题解决方案可以用严格的过程性编程术语来讨论,这样不仅能简化代码,而且能简化具体的讨论。第三,作为一种具有高级程序库的低层语言,C++允许我们讨论不同层次的编程。最优秀的程序员可以在需要的时候“手工编写”解决方案,并利用高级程序库和应用程序编程接口来减少开发时间。选择C++的最后一个原因是一旦学会了怎样用C++解决问题,就很容易学会用其他任何语言来解决问题。许多程序员发现在一种语言中所学会的技巧可以很轻松地应用于另一种语言,尤其是当前者是C++语言的时候,这是由于它的惯用法跨度广泛,或者坦率地说,是由于它的难度所决定的。C++是真正的实用型语言,它并不是面向教学而设计的。虽然初看上去有些吓人,但一旦取得进展之后,就会觉得自己不再只是会一点点编程的人了,而是将成长为一名真正的程序员。
“作者在向初学者阐述困难概念方面显然具有广博的知识和丰富的经验。本书显示了他脚踏实地、一丝不苟却又令人愉悦的写作风格。”
—Adrian Woodhead, Slashdot
“本书所提供的习题类似于我在接受Google和Facebook的软件工程面试时所遇到的问题,因此对于打算通过面试寻找新工作的专业程序员,本书是极好的复习材料。”
—Ariane Coffin, Wired.com's GeekMom
“这是我所阅读过的收获最大的书籍之一,因为它指导我们设计一个属于自己的系统,而不是把思维固化为只能采取一种正确的方法才能达到目的。”
—Lucas Westermann, Full Circle Magazine
“如果读者能够认真研读本书,我保证它可以极大地拓展您的思维。”
—David Bolton, About.com C/C++/C#
“不管使用什么教材向新学生讲授编程和程序逻辑,我建议一定要把本书作为重要的参考书。”
—Joe Saur, The ACM's Software Engineering Notes Magazine
“V. Anton Spraul所提供的建议简单、直观并且实用。本书的阅读是一个既轻松又极有价值的过程。”
—James Powell, Enterprise Systems
“对于所有想要培养创造性的解决问题能力的人以及已经学习了编程但觉得没有完全理解概念的人,我向他们强烈推荐本书。”
—Robert Perkins, Game Vortex
“如果我教其他人学习编程,这肯定是我将要选择的教材。”
—Stephen Chapman, Ask Felgall
本书的主题是怎样解决问题,但“解决问题”的确切定义是什么呢?当人们在日常谈话中提到这个术语时,所表达的意思往往与我们这里所讨论的含义截然不同。如果一辆1997年生产的本田思域轿车的排气管直冒蓝烟,怠速时震颤明显,并且油耗明显上升,说明它出现了问题。为了解决这个问题,必须具备相关的汽车知识和诊断故障的能力,并配备相应的替换部件,另外还需要一些常用的维修工具。如果把这个问题告诉朋友,可能会得到这样的建议:“嗨!你应该卖掉这辆旧本田车,然后换辆新的,问题就解决了”。但是,这位朋友的建议并不是这个问题的真正解决方案,它只是逃避这个问题的一种方法而已。
我们所说的“问题”其实包含了约束条件。约束条件就是与问题本身或者它的解决方法相关的、不能被违反的规则。以这台出了故障的思域轿车为例,其中一个约束条件就是需要修理这辆汽车,而不是购买一辆新车。其他的约束条件可能还包括修理成本、修理时限或者在修理的时候不能购买新的修理工具。
在解决程序中的问题时,也存在约束条件。常见的约束条件包括编程语言、平台(它在PC、iPhone还是其他平台上运行)、性能(有些游戏程序要求图形每秒至少刷新30次,而商业应用程序可能要求对用户输入的响应时间设置上限)或内存需求。有时候,约束条件还涉及到可供参考的其他代码,例如程序中不能包含有开源代码,或者正好相反,它只能使用开源代码。
因此,作为程序员,我们可以把“解决问题”定义为编写一个原创程序,使它执行一组特定的任务,并满足所有预先声明的约束条件。
程序员新手常常能够非常热切地完成这个定义的第一部分,也就是编写一个程序,执行一个特定的任务。但是,他们常常受挫于这个定义的第二部分,也就是无法满足预先声明的约束条件。我把类似这样的程序(即看上去能够产生正确的结果,但是违背了一个或多个预先声明的规则)称为小林丸号(Kobayashi Maru)。如果读者对这个名称感到陌生,说明对作为极克文化试金石之一的电影《星际迷航II:可汗怒吼》还不够熟悉。这部电影里面有一段情节,描述了星际学院中充满热情的学员们所经受的一场训练:学员们被放在一艘模拟的星舰桥上,以船长的身份接受一个不可能完成的任务。无辜的人们在一条受伤的船(小林丸号)上等待死亡。为了靠近他们,必须与克林贡战舰一战。这场战斗只可能导致船长的星舰被摧毁。这场训练是为了测试军校学生面临战火时的勇气。没有获胜的方法,所有的选择都会导致悲剧性的结果。当电影临近结束时,我们发现柯克船长更改了模拟训练装置,使它实际上可以获胜。柯克非常聪明,但他并没有解决小林丸号的困境,只是避开了它而已。
所幸的是,程序员所面临的问题通常是可以解决的,但许多程序员仍然采取了柯克船长的方法。在有些情况下,他们是不小心才这样的。(“噢!天哪,我的解决方案只有在数据项的数量不大于100的时候才行得通,但它必须能够处理数量不受限制的数据集,看来我必须重新加以考虑了。”)但在有些情况下,他们是有意去掉约束条件的,这是为了能够赶上老板或导师所施加的最后期限。还有一些情况,程序员只是不知道怎样满足所有的约束条件。在我所见到过的最坏的例子中,负责编程的学生花钱请人编写程序。不管出于什么动机,我们必须要想方设法避免小林丸号。
当读者深入学习本书的时候,将会注意到尽管源代码的特定细节可能因不同的问题而异,但有些模式会一直在我们所采取的方法中出现。这是非常重要的,因为它使我们最终能够充满自信地解决任何问题,而不管我们对于当前的问题领域是否拥有丰富的经验。专家级的问题解决者能够迅速发现类比关系,认识到一个已解决的问题和一个未解决的问题之间可供利用的相似之处。如果我们发现问题A的一个特性与已经解决的问题B的一个特性具有相似之处,就为解决问题A奠定了良好的基础。
在本节中,我们将讨论编程世界之外的一些经典问题,把其中的经验和教训应用于我们的编程问题。
我们将要讨论的第一个经典问题是一位需要过河的农夫所面临的难题。读者以前可能已经遇到过类似性质的问题。
怎样过河
一位农夫带着一只狐狸、一只鹅和一袋玉米过河。农夫有一条划艇,只能容纳他自己加上其中一件物品。遗憾的是,狐狸和鹅都饥肠辘辘。狐狸和鹅不能单独待在一起,因为狐狸会吃了鹅。同样,也不能单独把鹅和那袋玉米放在一起,因为鹅会吃了玉米。农夫怎样才能把所有东西都送过河呢?
图1.1展示了这个问题的场景。如果读者以前从来没有遇到过这样的问题,可以花几分钟的时间认真研究一下怎样解决这个问题。如果以前曾经遇到过这样的问题,也可以回忆一下它的解决方案,看看自己有没有办法独立解决。
图1.1 狐狸、鹅和一袋玉米。船一次只能载一样物品。
狐狸不能单独和鹅待在同一岸边,鹅不能单独和玉米待在同一岸边
在没有任何提示的情况下,很少有人能够解出这个难题。作者也自认没有这个能耐。下面是人们解决这个问题时的通常思路。由于农夫一次只能携带一样物品,因此他需要往返多次才能把所有物品送到对岸。在第一趟过河的时候,如果农夫带走狐狸,鹅就会单独和那袋玉米待在一起,肯定会吃了玉米。类似地,如果农夫选择带走那袋玉米,狐狸就会和鹅单独呆在一起,鹅也难逃被吃的厄运。因此,农夫第一趟必须带鹅过河,从而出现如图1.2所示的场景。
图1.2 解决狐狸、鹅和玉米问题必然采取的第一步。
但是,从这一步开始,所有后续的步骤看上去都将以失败告终
到目前为止,一切正常。但在第二趟过河时,农夫必须带走狐狸或玉米。但是,不管这次农夫带走什么,当农夫从对岸返回取最后一件物品时,第二趟所带去的物品必须在对岸与鹅单独待在一起。这意味着,要么是狐狸和鹅独处,要么鹅和玉米独处。由于这两种情况都是无法接受的,因此问题看上去似乎是无法解决的。
如果读者以前曾经看到过这个问题,很可能还记得解决方案的关键要素。如前所述,农夫在第一趟时必须带走鹅。在第二趟时,我们假设农夫带走了狐狸。但是,他并不是让狐狸和鹅一起待在对岸,而是在返回时把鹅带回近岸。然后,农夫把玉米带到对岸,将狐狸和玉米放在一起后返回。在第四趟过河时,农夫最后把鹅带走。图1.3展示了完整的解决方案。
这个问题很难,因此大多数人从来不会想到把物品再从对岸带回近岸。有些人甚至觉得这个问题是不公平的,表示:“你并没有说我可以把物品带回来!”确实如此,但是在描述问题的时候,题目也没有说禁止从对岸把物品带回来。
图1.3 狐狸、鹅和玉米难题的一步步解决方案
可以想象一下,如果事先明确说明可以把物品从对岸带回来,这个问题就会相当容易解决:
农夫有一条划艇,可以来回搬运物品,但小艇每次只能容纳农夫自身再加上他的三件物品之一。
有了这个说明之后,很多人都能解决这个问题了。这说明了解决问题的一个重要原则:如果没有意识到所有可以采取的动作,很可能无法解决问题。我们可以把这些动作称为操作。通过列举所有可能的操作,可以解决许多问题。我们只要测试这些操作的每种组合,直到发现可行的方案。概括地说,就是用更加形式化的术语重新陈述一个问题,常常可以发现此前被我们所忽略的解决方案。
我们先把这个问题的解决方案抛之脑后,然后用更形式化的方式陈述这个特定的难题。首先,我们列出了约束条件。这个问题的关键约束条件如下。
1.农夫在船中一次只能放一件物品。
2.狐狸和鹅不能单独放在同一岸边。
3.鹅和玉米不能单独放在同一岸边。
这个问题是说明约束条件重要性的一个很好的例子。如果我们去除所有的约束条件,这个问题就毫无难度。如果我们去除第一个约束条件,可以简单地一次携带全部3件物品过河。即使一次只能在船上放两件物品,也可以让狐狸和玉米先过河,然后再带鹅过河。如果我们去掉第二个约束条件(但保留另两个约束条件),就必须小心谨慎了。首先要带鹅过河,然后带狐狸过河,最后带玉米过河。因此,如果我们忘了或忽略了任何一个约束条件,就相当于遇到了小林丸号这样的情况。
接着,我们列出所有的操作。陈述这个问题的操作可以采用多种不同的方式。我们可以创建一个特定的列表,列出所有可以采取的操作。
1.操作:把狐狸带到河的对岸。
2.操作:把鹅带到河的对岸。
3.操作:把玉米带到河的对岸。
但是必须谨记,以形式化的方式重新陈述问题的目标是为了能够更好地发现解决方案。除非我们已经解决了问题并发现了“被隐藏的”可能操作(也就是把鹅带回到近岸),否则我们是无法通过上面所列出的这些操作方式发现这个操作的。因此,我们应该设法列出更基本(或参数化)的操作。
1.操作:把船从岸的一边划到另一边。
2.操作:如果船为空,从岸上装载一件物品。
3.操作:如果船不为空,把物品卸到岸上。
通过用最基本的术语来考虑问题,上面的操作列表可以让我们轻松地解决这个问题,就不会把“把鹅从对岸带回近岸”看成是什么奇思妙想了。如果我们枚举所有可能的移动序列,当每个序列违反了其中一个约束条件或重复了此前已经看到过的一个配置时就终止该序列,最终能够得到图1.3所描述的序列并解决这个问题。通过形式化地重新陈述这个问题的约束条件和操作,就成功地避开了它内在的困难性。
经验和教训
我们可以从狐狸、鹅和玉米的问题中学到什么呢?
用更形式化的方式重新陈述问题是一种非常出色的技巧,可以让我们拥有对问题更好的洞察力。许多程序员设法与其他程序员一起讨论问题,并不仅仅因为对方可能已经有了答案,而是因为清晰地陈述问题常常会激发有用的新思路。重新陈述问题就相当于与其他程序员讨论问题,只不过现在是一人分饰两角。
更深远的意义在于,认识到思考问题很可能与思考解决方案具有相同的工作效率,甚至更胜一筹。在许多情况下,通往解决方案的正确道路本身就是解决方案。
瓷砖滑块问题存在许多不同的规格,正如我们稍后所看到的那样,它提供了一种特定的解决机制。下面是对3×3版本的瓷砖滑块问题的描述。
滑动8块
一个3×3的网格中放了8块瓷砖(编号从1~8),剩下一格为空。一开始,网格的配置很杂乱。瓷砖可以滑动到邻近的空格中,使它的原先位置为空。这个问题的目标是在网格中滑动瓷砖,使它们从左上角开始在网格中有序地排列。
图1.4展示了这个问题的目标。如果读者之前从来没有遇到过这样的问题,可以花些时间考虑怎么解决。网络上可以找到大量的滑动瓷砖问题模拟程序,但最好还是用扑克牌或索引卡在桌上试验。图1.5显示了推荐的初始配置。
图1.4 8块瓷砖版本的瓷砖滑块问题的目标配置,
空格表示邻近的瓷砖可以移动到的空间
图1.5 瓷砖滑块问题的一个特定初始配置
这个问题与前面所讨论的农夫与狐狸、鹅和玉米的问题截然不同。过河问题的难度在于可能会忽略其中一种可行的操作。在这个问题中,并不会发生这样的情况。对于任何特定的配置,空格周围最多有4块瓷砖,它们都可以移动到这个空格中。这样的描述已经枚举了所有可能的操作。
这个问题的难度在于解决方案所需的漫长的操作环节。一系列的滑动操作可能把某些瓷砖滑动到它们的目标位置,同时又把其他瓷砖移出正确位置,或者可能把某些瓷砖滑动到靠近目标位置,同时又把其他瓷砖滑动到远离目标位置。由于这个原因,很难认定任何特定的操作是否朝着最终的目标迈近了一步。因为没有办法衡量进度,所以很难形成一种策略。很多人通过随机的滑动来解决这个问题,希望恰好能够滑动到最终的目标配置。
但是,瓷砖滑块问题还是存在策略的。为了演示其中的一种方法,我们可以考虑一个更小的网络,它是长方形的,而不是正方形的。
滑动5块
有一个2×3的网格里放了5块瓷砖(编号从4~8),另外剩下1个空格。一开始,这些瓷砖排列得很混乱。瓷砖可以滑动到邻近的空格中,使自己原来的位置成为空格。这个问题的目标是使这个网格中的瓷砖排列有序,4号瓷砖出现在网格的左上角,接下来依次类推。
读者可能注意到这几块瓷砖是以4到8编号的,而不是从1到5。读者很快就能知道这样安排的原因。
尽管它是与8块的瓷砖滑块相同的基本问题,但只有5块瓷砖显然要简单得多。尝试完成如图1.6所示的配置。
如果试上几分钟,很可能会找到一种解决方案。从较小数量的瓷砖滑块问题出发,我开发了一个特定的技巧。这个技巧加上我们稍后将要进行的讨论,可以用来解决所有的瓷砖滑块问题。
图1.6 2×3版本的瓷砖滑块问题的一个特定起始配置
我把这种技巧称为“串列”,它基于对一组瓷砖位置所形成环路的观察。这些位置加上空格就构成了一个瓷砖串列,可以在这个环路中旋转,同时保持这些瓷砖的相对顺序。图1.7演示了由4个位置所组成的最小可能串列。在一开始的配置中,1可以滑动到空格中,2可以滑动到1移走后所留下的空格中,最后3可以滑动到2移走后所留下的空格中。这样,空格就与1相邻,使这个串列可以继续旋转。因此,这些瓷砖可以在这条串列路径中有效地旋转到任何位置。
图1.7 “串列”,与空格相邻的瓷砖开始形成了一条瓷砖路径,
在游戏过程中可以像一列火车一样滑动
我们可以使用串列移动一系列的瓷砖,同时保持它们之间的相对关系。现在我们回到前面的2×3的网格配置。尽管这个网格中没有任何一个瓷砖位于它最终的正确位置,但有些瓷砖却靠近它们在最终配置中需要靠近的瓷砖。例如,在最终的配置中,4将出现在7的上面,而这两块瓷砖当前是相邻的。如图1.8所示,我们可以用一个包含6个位置的串列把4和7移动到它们最终正确的位置。当我们完成这个操作时,剩余的瓷砖几乎都处于正确的位置,只需要再移动一下8就可以了。
图1.8 从配置1出发,经过2次沿规划的“串列”旋转之后来到配置2,
然后只要滑动1次就可以产生最终的配置3
这种技巧是怎么解决所有瓷砖滑块问题的呢?考虑最初的3×3配置。我们可以用包含6个位置的串列移动相邻的1和2,使2和3相邻,如图1.9所示。
图1.9 从配置1出发,瓷砖沿规定的“串列”旋转到达配置2
这样1、2和3就相邻了。在8个位置的串列中,我们就可以旋转1、2和3了,使它们到达最终的正确位置,如图1.10所示。
图1.10 从配置1出发,瓷砖经过旋转之后到达配置2,这样瓷砖1、2和
3位于正确的最终位置
注意瓷砖4~8的位置。这些瓷砖的配置正好与前面的2×3网格的例子相同。这是一个至关重要的观察。把瓷砖1~3放在正确的位置之后,我们就可以把剩余的瓷砖看成是一个更小、更容易解决的独立问题。注意,为了使这种方法可行,必须要解决一整行或一整列的瓷砖。如果我们把瓷砖1和2放在正确的位置,但3仍然置于别处,那样就无法在不移动左上角两块已经就绪的瓷砖的情况下,把任何瓷砖移动到右上角位置。
这个技巧也可以用于解决规模更大的瓷砖滑块问题。常见的最大尺寸是15块瓷砖,也就是4×4的网格。这样的问题也可以用分解法来解决:首先把瓷砖1~4移动到正确的位置,这样就只剩下一个3×4的网格,然后再完成最左列的瓷砖,这样就只剩下一个3×3的网格。此时,就只剩下8块瓷砖需要移动了。
经验和教训
我们可以从瓷砖滑块问题中学到什么呢?
由于瓷砖移动的次数相当之多,因此无法在初始配置时就规划一个完整的解决方案。但是,无法规划完整的解决方案并不意味着就无法采取策略或技巧系统性地解决问题。在解决编程问题时,有时候会出现无法看到通向解决方案的清晰道路的情况,但这绝不能成为跳过计划和采用系统性方法的借口。更好的办法是采用一种策略,而不是通过简单地反复尝试和失败来解决问题。
我是通过对较小的问题进行研究时发现这种“串列”技巧的。在编程中,我常常会使用这种类似的技巧。在面临一个复杂的问题时,我常常会对这个问题的削减版本进行试验。这些试验常常能够产生有价值的思路。
另一个经验是问题的细分通常并不是非常明显的解决之道。由于移动一块瓷砖不仅影响这块瓷砖本身,还会影响接下来可能发生的移动,人们可能觉得瓷砖滑块问题必须在一个步骤中完成,而不能分阶段解决。因此,花时间研究怎样对问题进行细分通常是非常合算的。即使无法找到一种清晰的细分,仍然有助于增强对这个问题的理解,可以促进这个问题的解决。在解决问题时,头脑里已经拥有一个特定的目标总比随机的尝试要好得多,无论最终是否能够实现这个目标。
数独游戏作为一种在报纸和杂志上出现的益智游戏,其流行程度已经达到了惊人的地步,并且已经发展成一种基于网络和手机的游戏。数独拥有许多不同的版本,但这里只简单讨论传统的版本。
完成数独方块
一个9×9的网格,其中部分方格填有数字(1~9),玩家必须填满剩余的空格,并满足下面这个约束条件:对于每一行和每一列,每个数字恰好只出现1次。而且,对于粗框内的每个3×3区域,每个数字也恰好只出现1次。
如果读者以前曾经玩过这个游戏,很可能已经知道应该采用什么策略在最短的时间内完成一个空格。我们首先观察如图1.11所示的方块,关注最关键的起始策略。
数独游戏的难度差异极大,它们的难度取决于需要填充的空格数量。按照这种衡量方法,这是一个相当容易的问题,因为已经有36个空格已经填好,只需要再填写45个空格就可以完成任务了。问题在于,我们应该首先填充哪个空格呢?
图1.11 一个很简单的数独方块问题
记住,这个问题包含了约束条件。在每一行、每一列以及粗框内的每个3×3区域中,9个数字必须都正好出现1次。这些规则决定了我们应该从哪里着手。最中间的3×3区域的9个方格已经有8个填好了数字。因此,正中心的那个空格只可能填入这个3×3区域的其他方格没有出现的那个数字。我们应该从这个空格开始解决这个问题。这个区域所缺少的数字是7,因此我们在最中间的那个空格中填入7。
填好了这个数字之后,注意最中间那列的9个值已经有7个已经填好,只剩下2个空格,必须填上这一列所缺少的两个值:3和9。与这个列有关的约束条件允许把这两个值放在任意一个位置,但是注意3已经在第三行出现过,9已经在第七行出现过。因此,我们应该把9填在中间那列的第三行,把3填在中间那列的第七行。图1.12对这些步骤进行了概括。
图1.12 解决示例数独问题的开始步骤
我们不打算完成整个方块的填写,但前面这几个步骤已经说明了重要的一点,就是搜索那些可能出现的值最少的空格。在最理想的情况,就是只剩下一个空格。
经验和教训
我们在数独问题中所学到的主要经验就是应该寻找问题约束性最强的部分。虽然约束条件往往使问题难以着手(还记得狐狸、鹅和玉米问题吗),但它们也可以简化思路,因为它们消除了很多选择。
尽管我们不会在本书中详细讨论人工智能,但还是要简单地提一下,在人工智能中解决某些类型的问题时有一个称为“最大约束变量”的规则。它表示在一个问题中,当我们向一些不同的变量赋一些不同的值来满足约束条件时,应该从约束性最强的变量开始。换用更通俗的说法,就是那些可能采用的值具有最少的变量。
下面是这种思维方式的一个例子。假设有一组工友计划一起吃午饭,并且想要找一家每个人都喜欢的餐厅。问题在于,每个工人对于整个小组的决策都会施加某种程度的影响。例如,Pam是个素食主义者,Todd不喜欢中国菜等。如果目标是最大限度地减少寻找餐厅的时间,首先应该询问对餐厅最挑剔的那个工人。例如,如果Bob对很多食物都过敏,首先列出他可以进食的餐厅列表是非常合理的。像Todd不喜欢中国菜这样的癖好应该放在最后考虑,因为这个困难是很容易克服的。
这个技巧往往也可以用于编程问题。如果问题的某个部分具有很强的约束条件,很可能应该从这一部分开始着手,这样就不必担心把时间花在将来可能会返工的任务上了。一个相关的推论是:应该从最显而易见的那部分任务开始着手。如果可以解决这个部分的问题,就可以在此基础上继续执行其他可以完成的任务。通过审视自己的代码,可能会激发自己的想象力,从而解决剩余部分的问题。
对于上面这几个问题,读者以前可能也看到过。但是对于本章的最后一个问题,除非以前曾经阅读过本书,否则绝不可能见过,因为这是我自己“发明”的。请认真阅读,因为这个问题的描述稍微有点复杂。
打开外星锁
一种敌对的外星生物Quarrasi登陆到地球上,你在战斗中被它们抓获并关押在飞船里。你设法打倒了看守,尽管它们体形庞大并且长有触角。但是,为了逃离飞船(仍然在地面上),必须打开巨大的舱门。开门的指令非常奇怪,它是用英语的形式显示的,但非常难弄。为了打开舱门,必须沿着轨道滑动3个条状的Kratzz,从右侧的接收器滑动到位于门尽头的左侧接收器,距离大约3m。
这个任务相当简单,但是必须避免触发警报。警报的工作原理如下:每个Kratzz就是一个或多个星形的水晶力量宝石,称为Quinicrys。每个接收器具有4个传感器,如果一个纵列中Quinicrys的数量为偶,它们就会被点亮。如果被点亮的传感器的数量正好为1,就会发出警报。好消息是每个警报都配备了一个抑制器,只要按下这个按钮,就可以防止警报发出声音。如果可以同时按下所有的抑制器,问题就非常简单了,但是没有办法做到这一点,因为人类的胳膊过于短小,不比长长的Quarassi触角。
根据上面的描述,怎么才能在不触发任一警报的前提下滑动Kratzz打开舱门呢?
图1.13展示了初始配置,3个Kratzz都位于右侧的接收器。为了清晰起见,图1.14展示了一种不好的思路:把最上面那个Kratzz滑动到左侧接收器会导致右侧接收器处于报警状态。你可能想到用抑制器来避免报警,但是要记住,你刚刚把最上面的Kratzz移动到左侧接收器,够不着相距3m的右侧接收器上的抑制器。
图1.13 Quarrasi锁问题的初始配置。必须滑动当前位于右侧
接收器的3个Kratzz条,在不触发任何一个警报的情况下把它们
滑动到左侧的接收器。当偶数个星形的Quinicrys出现在上面的
纵列时,就会点亮一个传感器,如果正好有一个被连接的
传感器被点亮,就会触发警报。抑制器可以防止警报
发声,但你只能控制自己所站那一侧的抑制器
图1.14 处于报警状态的Quarrasi锁。你刚刚把最上面的Kratzz滑动到
左侧的接收器,因此够不到右侧的接收器。右侧警报的第2个传感器
被点亮,因为出现在那个纵列的Quinicrys数量为偶,现在正好
是一个传感器被点亮,所以就会触发报警
在继续尝试之前,先花点时间研究这个问题,设法确定一个解决方案。这取决于看问题的着眼点,此问题并没有看上去那么难。认真地说,要在尝试之前先对它进行思考!
考虑好了吗?现在是不是能够想出一个解决方案?
为了回答这个问题,可以选择两条可能的路径。第一条路径就是不断尝试,不过它是错误的做法:尝试用各种方式移动这几个Kratzz,一旦达到警报状态时就返回到前一步骤,直到最终通过一系列的移动,成功地打开锁。
第二条路径是认识到这个问题实际上是个机关。你从前可能没看到过这种机关,它实际上就是披着伪装外衣的狐狸、鹅和玉米问题。尽管警报的规则是以通用的方式描述的,但是与这种特殊的锁有关的组合却是有限的。如果只考虑3个Kratzz,我们只需要知道接收器上的哪些Kratzz组合是可以接受的。如果我们把这3个Kratzz分别命名为top、middle和bottom,那么会触发报警的组合是“top和middle”以及“middle和bottom”。
如果我们把top重新命名为狐狸,把middle重新命名为鹅,把bottom重新命名为玉米,这样所有的麻烦组合都与狐狸、鹅和玉米问题一样了,也就是“狐狸和鹅”和“鹅和玉米”。
因此,这个问题的解决方式与狐狸、鹅和玉米问题相同。我们把middle(鹅)滑动到左侧的接收器,再把top(狐狸)滑动到左侧,当我们移动top(狐狸)时摁住左侧警报的抑制器;接着,我们把middle(鹅)滑动回右侧的接收器;然后,我们把bottom(玉米)滑动到左侧;最后,我们把middle(鹅)再次滑动到左侧,这样就打开了锁。
经验和教训
这个问题向我们提供的主要经验就是认识到类比的重要性。我们可以看到Quarrasi锁问题实际上与狐狸、鹅和玉米问题非常相似。如果我们早早就发现了这种类比,就可以根据狐狸、鹅和玉米问题直接想到解决办法,而不需要从头创建一个新的解决方案,从而大大节省了精力。在解决问题时,大多数类比并不是这样直接,但它们的出现频率却非常高。
如果读者难以发现这个问题和狐狸、鹅和玉米问题之间的联系,这只是因为我故意增加了一些多余的细节。与Quarrasi锁问题相关的背景对于解决这个问题而言是无关紧要的,那些外星术语也是如此,它们唯一的作用就是让读者感觉生疏。而且,警报的奇/偶机制使这个问题看上去比实际更为复杂。如果观察Quinicrys的实际位置,就可以看到顶部的Kratzz和底部的Kratzz正好相对,因此它们并不会与警报系统交互。但是,中间的Kratzz却与另两个发生交互。
同样,如果没有发现类比,也不必担心。对它们有了足够的警觉之后,就很容易认识到它们。
我们所讨论的这些例子说明了在解决问题时将要采用的许多关键技巧。在本书的剩余部分,我们将观察特定的编程问题,并想办法怎样解决它们。但是,我们首先需要了解一组基本的技巧和原则。有些问题领域需要使用特定的技巧,但下面这些规则几乎适用于所有的场合。如果把它们作为自己的问题解决方法的常规武器,就能想出办法解决任何特定问题。
这也许是最重要的规则。我们事先必须要制订计划,而不是直接进行漫无方向的尝试。
根据这个观点,我们应该理解事先制订计划总是可能的。如果在头脑里还不知道怎么解决问题,就不可以制订计划编写代码实现一个解决方案。这个任务是在以后完成的。但是,即使是在开始阶段,还是应该为怎样寻找解决方案制订一个计划。
平心而论,这样的计划可能需要在其他阶段进行修改,或者必须抛弃原先的计划并制订一个新计划。既然如此,为什么这个规则仍然非常重要呢?艾森豪威尔将军有句名言:“我总是发现计划没什么用处,但计划仍然是必不可少的。”他的意思是战争是极为混乱的,事先预测将要发生的每件事情并为每种结果准备预定的方案是不可能的。从这个意义上说,计划在战场上是没有用处的(普鲁士军事领袖赫尔默特·冯·毛奇曾有名言“一旦与敌人交上火,所有计划都不再有效”)。但是,如果没有计划和组织,任何军队都不可能取得胜利。通过精心制订计划,将军能够了解敌军的战斗力、部队中不同部门的配合方式等重要信息。
同样,我们在解决一个问题时必须要制订一个计划。也许这个计划一旦与敌人交上火就不再有效,也许我们在源代码编辑器中开始输入代码时就会抛弃这个计划,但我们还是必须制订计划。
如果没有计划,我们只能简单地希望“摔出好运气”,相当于在键盘上随意输入却产生了莎士比亚的伟大作品。“摔出好运气”是极为罕见的,而且就算如此可能仍然需要计划。很多人听说过青霉素的发现过程:一位名叫亚历山大·弗莱明的研究人员在一个晚上忘了盖上一个培养皿,第二天早上他发现霉菌抑制了培养皿上细菌的生长。但是,弗莱明并不是干坐在那里等待摔出好运气,他已经按照一种精心可控的方式进行了试验,因此能够认识到他在培养皿上所看到的事实的重要性。(如果我发现前一天晚上所放置的某样东西上长了霉菌,肯定不会对科学产生重大的贡献。)
计划还允许我们设置中期目标并实现它们。如果没有计划,我们就只有一个目标:解决整个问题。在解决了整个问题之前,我们不会感觉自己实现了什么目标。我们很可能有过这样的经验,许多程序在接近完成前没有实现任何实用的功能。因此,只朝着主要目标努力会不可避免地遭受挫折,因为在工作结束之前,不会有正面的推动力激励自己。反之,如果我们创建了一个具有一系列分阶段目标的计划,虽然看上去与主要的问题不是非常密切,仍然可以朝着解决方案取得可衡量的进展,并感觉自己的时间被合理地使用了。在每个工作阶段完成时,我们就可以检查计划所制订的各个事项,更有信心找到解决方案,而不是被日益加重的挫折感所笼罩。
狐狸、鹅和玉米的问题鲜活地证明了重新陈述问题可能会产生非常有价值的结果。在某些情况下,一个看上去非常困难的问题如果用一种不同的方式或术语进行阐述,就会变得非常容易。重新陈述问题就像是在登山之前寻找一个不同的出发地点。在登山之前,为什么不从每个角度进行观察,确定最容易攀登的路线呢?
重新陈述问题有时候可以向我们展示此前没有想到的目标。我曾经看过一个故事,一位祖母一边编着毛衣一边照看孙女。为了在织毛衣时不受干扰,祖母把婴儿放在她旁边的一个可移动游戏围栏中,但她的孙女不喜欢待在里面,不停地哭泣。祖母尝试了把所有各种类型的玩具放在围栏里都没有收到效果。最终,她才意识到把孙女放在围栏里只是实现目标的一种方法,她的真正目标是能够安静地织毛衣。解决方案是:让孙女在地毯上自由自在地玩耍,祖母则坐在围栏里面专心织毛衣。重新陈述可以成为一种威力强大的技巧,但很多程序员会忽略它,因为它并不直接与编写代码有关,甚至和解决方案的设计也没什么关联。这是制订计划之所以重要的另一个原因。如果没有计划,我们的目标就是可运行的代码,而重新陈述问题则是将时间用在与编写代码没有关系的地方。有了计划之后,我们就可以把“形式化地重新陈述问题”作为自己的第一个步骤,完成重新陈述就意味着取得了进展。
即使重新陈述问题并没有直接让我们获得新思路,它仍然可能在其他方面提供帮助。例如,如果我们碰到了一个问题(由上级或指导老师所“指派”),我们可以把问题重新陈述给指派这个任务的人,以确认自己的理解无误。另外,重新陈述问题对于使用其他常用的技巧也可能是一个必要的先决步骤,例如削减或划分问题。
总而言之,重新陈述问题可以转换整个问题领域。我在第6章的递归解决方案中所使用的技巧就是一种重新陈述递归问题的方法,使我可以像处理迭代问题一样处理它们。
找到一种方式把一个问题的解决方法划分为几个步骤或几个阶段,可以使问题更容易解决。如果我们把一个问题划分为两个片段,可以认为每个片段的难度相当于原先整个问题的一半,但通常还要容易得多。
如果读者了解常用的排序算法,对下面这个类比应该是非常熟悉了。假设我们需要把100个文件按照字母顺序放在一个箱子里,并且我们采用的基本字母排序方法是一种很有效的被称为插入排序的方法:随机取其中一个文件,把它放在箱子里,然后把第2个文件放在箱子中相对于第1个文件正确的位置,接着继续这个过程,总是把新文件放在箱子里相对于其他文件正确的位置。因此,在任一特定时刻,箱子中的文件就是按字母顺序排列的。假设有人一开始粗略地把这些文件分成数量大致相等的4组:A~F、G~M、N~S和T~Z,然后告诉我们分别对各组文件按字母顺序排列,最后依次把各组文件放在箱子里。
如果每组大约包括了25个文件,人们可能觉得分别对4组25个文件按字母排序所需要的工作量和对单组100个文件按字母排序的工作量是一样的。实际上,前者的工作量要小得多,因为插入一个文件所需要的工作量是随着已经排好序的文件数量的增加而增长的。我们必须检查箱子中的每个文件才能知道这个新文件应该放在哪个位置。(如果对此感到怀疑,可以考虑一个更极端的版本,比较一下对50组2个文件进行排序的方法,很可能不到一分钟就能完成全部100个文件的排序。)
同样,对问题进行划分常常可以使问题的难度大幅度降低。把各个编程技巧组合在一起使用要比单独使用每个技巧困难得多。例如,如果一段代码在一个while循环内部包含了一系列的if语句,而这个循环本身又位于一个for循环的内部,这样的代码是很难编写和理解的。相对而言,按照顺序编写这些相同的控制语句则要容易编写和理解很多。
我们将在后面的章节中讨论划分问题的具体方法。但是,我们终归应该意识到这种可能性。记住,像瓷砖滑块这样的问题常常隐藏着潜在的划分方法。有时候,寻找问题的划分方法就是削减问题的方法,正如我们稍后将要讨论的一样。
作家在开始创作的时候,常常会收到这样的建议“写自己知道的东西”。这并不意味着作家只能描写他们在日常生活中直接观察到的人和事。如果这样,我们就无法看到奇幻小说、历史小说以及其他许多流派的小说了。但是,这个建议的意思是,作家所写的东西距离他自己的经历越远,写作的难度也就越大。
同样,在编程的时候,我们应该尽量从自己知道的部分开始着手。例如,一旦我们把问题划分为几个片段,应该寻找自己已经知道怎样编写代码的片段。完成了解决方案的一部分之后,可能会激发完成剩余工作的灵感。另外,正如我们可能预料到的那样,问题解决领域的一个常见主题就是取得实际的进展以构建自己的信心,相信自己能够最终完成整个任务。通过从自己所知的领域开始着手,我们就能够构建获得成功的信心和动力。
“从自己所知的开始”这句格言还适用于尚未对问题进行划分的时候。想象一下,有人创建了一个包含每个编程技巧的完整列表:编写一个C++类、对一个数值列表进行排序、寻找一个链表的最大值等。作为程序员,在开发过程的每一刻,这个列表中可能有许多任务是我们所掌握的,有些是需要花费一些心思的,还有一些则是现在还不知道怎么解决的。一个特定的问题用自己已经掌握的技巧可能是完全可以解决的,也可能是无法解决的。但是,在寻找其他方法之前,我们应该用已经掌握的技巧对问题进行完整的研究。如果我们把编程技巧看成是工具,把编程问题看成是家庭维护项目,首先应该用手头上已经有的工具进行修理,然后再考虑到五金店购买新工具。
这个技巧遵循了我们已经讨论的原则。它遵循了一个计划,指挥我们的工作。当我们用自己所掌握的技巧对一个问题进行研究时,可以更好地理解这个问题本身以及它的最终目标。
当我们面临一个无法解决的问题时,通过这种技巧,可以削减问题的范围。我们可以添加或取消约束条件,产生一个自己知道如何解决的问题。在后面的章节中,我们将通过实际例子讨论这种技巧,不过下面先通过一个基本的例子阐述它的概念。假设一个三维空间中有一系列的坐标,我们的任务是找到空间距离最近的那对坐标。如果我们并不能立即知道怎样解决这个问题,可以采用一些不同的方式削减这个问题以寻求解决方案。例如,如果这些坐标是在一个二维空间而不是三维空间中如何是好?如果削减成这样还是无法解决,那么把二维空间再缩减为一条直线,这些坐标就成了各个不同的数(是否可以用C++的double类型表示),这样不是就可以解决了吗?现在,这个问题在本质上就成了在一个数的列表中寻找两个具有最小绝对差的数。
或者,我们在削减问题时仍然让这些坐标位于三维空间中,但只处理3个值,而不是任意数量的坐标系列。因此,现在问题就不再是寻找一种算法,计算两个任何坐标之间的距离,而是变成了坐标A与坐标B比较、坐标B与坐标C比较,然后是坐标A与坐标C比较。
这两种削减方法通过不同的方式简化了原先的问题。第一种削减方法消除了计算三维点之间距离的需要。也许我们还不知道该怎样计算空间距离,但在知道怎么做之前,仍然可以取得一些进展。反之,第二种削减方法仍然要求我们计算三维点之间的距离,但是消除了在任意数量的三维点之间寻找最小值的问题。
当然,为了解决最初的问题,我们最终需要组合这两种削减方案所涉及的技巧。即使如此,削减问题允许我们对一个更简单的问题进行操作,即使我们无法找到一种方法把问题划分为几个阶段。在实际效果上,它相当于故意同时、又是临时的小林丸号。尽管我们知道并不是对整个问题进行处理,但是经过削减的问题与原先的问题仍然具有相当多的共性,足以让我们向最终的解决方案又迈进一步。许多时候,程序员发现他们具备了解决问题所需要的所有单独技巧,通过为问题的每个单独片段编写代码,他们可以想到怎样把各个不同的代码片段组合为一个统一的整体。
削减问题还允许我们准确地理解剩余的难点位于何处。程序员新手常常需要向经验丰富的程序员寻求帮助,但是如果他无法准确地描述自己所需要的帮助,那么对于双方都很可能是一种饱受挫折的体验。我们绝对不可能把问题削减为“这是我的程序,它无法工作。为什么?”使用问题削减技巧,我们可以准确地描述自己所需要的帮助,表示“这是我编写的一些代码。如您所见,我知道怎样计算两个三维坐标之间的距离,并且知道一个距离是否小于另一个距离。但是,我无法找到一种通用的解决方案,在众多坐标中寻找那对具有最小距离的坐标。”
对于我们而言,类比就是一个当前问题和一个已经解决的问题之间的相似性。我们可以利用这种相似性来解决当前问题,而这种相似性可能以多种形式存在。有时候,它意味着两个问题实际上是同一个问题。狐狸、鹅、玉米问题和Quarrasi锁问题就属于这种情况。
大多数类比并没有这么直接。有时候,相似性只涉及到问题的一部分。例如,两个数值处理问题可能在其他方面都不一样,唯一的共同点就是都需要比内置的浮点数据类型更精确的数值。我们无法使用这种类比来解决整个问题,但是如果我们已经想出了办法处理额外的精度问题,那就可以按照同样的方式再次处理相同的问题。
尽管认识类比是提高自己的问题解决速度和技能的最重要方式,但它也是最难培养的一种技巧。原因是在一开始很难发现类似的关系,除非有大量以前的解决方案可供参考。
这是成长中的程序员经常寻求捷径的地方。他们常常寻找那些与所需要的代码相似的代码,并在后者的基础上进行修改。但是,出于某些原因,这是错误的做法。首先,如果我们没有自己完成一个解决方案,就不能彻底理解并吸收它。简单地说,要想正确地修改一个自己并没有完全理解的程序是非常困难的。我们并不需要通过编写代码获得完全的理解,但是如果我们无法编写代码,我们对它的理解肯定是有限的。其次,我们所编写的每个成功的程序并不仅仅是一个当前问题的解决方案,它还是一种潜在的类比资源,可以供解决未来的问题所用。我们现在对其他程序员的代码的依赖程度越深,在未来仍然需要这种依赖的可能性也就越大。我们将在第7章深入讨论“良好的复用”和“不良的复用”。
有时候,取得进展的最好方法是对事物进行试验并观察其结果。注意,试验与猜测并不相同。当我们进行猜测时,自己输入一些代码并希望它能够完成任务,但对于能否达到目的自己并没有很强的信心。试验则是一种可控的过程。我们假设当某些代码执行时将会发生什么,然后对它进行试验,观察自己的假设是否正确。根据这些观察,我们可以获得一些信息,帮助自己解决原先的问题。
在处理应用程序编程接口或类库时,试验尤其能够提供帮助。假设我们编写了一个程序,使用了一个表示向量的库类(当元素被添加时能够自动增长的一维数组),但以前从来没有使用过这个类,并且不确定从这个向量中删除一个元素时会出现什么情况。在还没有掌握这个类的详细机制时,不要匆匆用它来解决原先的问题,而是可以先创建一个简短的单独程序,专门对这个向量类进行试验,尤其要在自己关心的场景下对它进行试验。如果在这个“向量演示程序”中花费一点时间,那么在以后的工作中它可以作为这个类的参考使用。
另一种形式的试验与调试相似。例如,一个特定的程序所产生的输出与预期的正好相反。如果输出的是数值并且所输出的数正如预想的一样,但顺序正好相反。如果在检查了代码之后还不明白为什么会发生这种情况,可以进行试验,修改代码,故意产生反向的输出(可能是运行一个反方向的循环)。如果输出结果发生了变化或者没有发生变化,都可能揭示出自己原先的源代码所存在的问题,为自己的思路打开一个缺口。不管怎样,我们都朝着解决方案迈进了一步。
最后一个技巧其实谈不上技巧,而是一句格言:避免陷入挫折感。当我们陷入挫折感时,自己的思维不再那么清晰、工作不再那么高效,所有的任务需要花费更长的时间并且看上去更为困难。更糟的是,挫折感会不断恶化,很可能从一开始轻度的焦虑变成最终难以遏制的烦躁。
当我向程序员新手提出这个忠告时,他们常常会反驳说,虽然他们在原则上同意我的观点,但他们对于是否会遭遇挫折是无法控制的。要求一位缺乏成功感的程序员避免陷入挫折感岂不是相当于要求小孩子在踩到钉子时不要叫喊吗?除非能够预料到自己将踩到钉子上,否则不可能及时抑制大脑的本能反应。因此,我们能够做的就是让小孩子避免踩到钉子。
程序员的处境并不相同。程序员不会像自我激励的大师一样大声叫喊,他们在遭受挫折时并不会对外部刺激做出强烈的反应。陷入挫折感的程序员并不是对显示器上的源代码生气,尽管他可能会对着屏幕表达挫折感。反之,陷入挫折感的程序员是对自己生气。挫折的来源同时也是挫折的目标,也就是程序员的思维。
如果我们允许自己陷入挫折感时(我故意使用了“允许”这个词),实际上就为自己继续失败找到了借口。假设我们正在处理一个难题,并且挫折感不断上升。几个小时后,我们咬牙切齿,愤怒地把铅笔折成两截,并告诉自己如果能冷静下来,一定能取得实质性的进展。事实上,我们已经决定向自己的怒气屈服,觉得这要比勇敢面对这个难题容易得多。
最终,避免陷入挫折感是我们必须做出的决定。不过,我们可以采用一些思路,也许相助于实现这一点。首先,不要忘记第一条规则,也就是说始终要制订计划。虽然编写解决原先问题的代码是这个计划的目标,但这并不是这个计划的唯一步骤。因此,如果制订了一个计划并遵循了它,我们就能够取得进展并对此坚信不疑。如果完成了最初计划的所有步骤,但还是无法开始编写代码,这个时候就应该制订另一个计划。
另外,如果读者觉得继续干下去可能会陷入挫折感时,可以休息一会。一个诀窍是让手头上所处理的问题不止一个。这样,如果读者对一个问题感到无可奈何,可以把精力转向另一个问题。注意,如果成功地划分了问题,就可以对单个问题应用这种技巧,只要把陷入僵局的那部分问题扔在一边,转而解决其他部分的问题就可以了。如果没有可以处理的其他问题,也可以离开椅子做些其他事情。可以热热身,放松一下脑子,例如散步、洗衣服、做伸展运动(如果读者是一个整天坐在计算机前的程序员,我强烈建议养成做伸展运动的习惯)。在休息结束之前,不要再考虑那个问题。
记住,为了真正学到东西,只有通过实践才有可能。因此,要尽可能多地完成习题。当然在第1章中,我们还没有讨论编程。但即使是这样,我还是鼓励读者尝试完成一些习题。读者可以把下面这些习题看成是演奏真正音乐之前的指法练习。
1.1 完成一个中等难度的数独题(可以从网络或当地报纸上寻找),用不同的策略进行试验,并对结果加以说明。能不能为解决数独问题编写一个通用计划呢?
1.2 考虑瓷砖滑块问题的一种变型,每块瓷砖上显示的是图片而不是数字。这种变化使难度增加了多少?为什么?
1.3 为瓷砖滑块问题寻找一种与我不同的解决策略。
1.4 搜索旧式的狐狸、鹅和玉米问题的变型并尝试解决它们。很多著名的难题来源于Sam Loyd或者是由他推广的。因此,可以通过他的名字进行搜索。而且,一旦发现(或者觉得太难而放弃思考,只是看看)了解决方案,思考怎样据此创建难题的简化版本。有哪些东西必须修改?仅仅修改约束条件还是描述方式?
1.5 尝试为其他传统的铅笔和纸游戏(例如纵横填字谜)编写一种显式的策略。应该从什么地方开始呢?在陷入僵局时应该怎么做呢?即使是“Jumble(类似七巧板的益智游戏)”这样的简单报纸游戏,也非常适合思考它的解决策略。
现在是时候把我们在前面各章所学习的知识揉和到一起,完成从雏鸟初飞的新手到能够熟练解决问题的程序员的蜕变。
在前面各章中,我们解决了各个不同领域的问题。我相信对这些领域的问题的研究最有益于程序员的成长。当然,我们需要学习的东西还有很多,许多问题需要本书未能覆盖的技巧才能解决。在本章中,我们将尽可能完整地讨论通用的问题解决方案,利用我们在前面各章的探索旅程中所获得的知识,开发出一个总体计划来解决任何编程问题。尽管我们把它称为总体计划,但实际上它只是一个非常特定的规划:它将成为我们自己的规划,而不是其他人的。我们还将讨论程序员用于增长知识和提升技能的许多方式。
在第1章中,我们学习了解决问题的第一个原则是“总是要有计划”。更准确的说法是总是遵循自己的计划。我们应该创建一个总体计划,最大限度地发扬长避短,然后把这个总体计划应用于自己必须解决的每个问题中。
在多年的教学生涯中,我看到过很多能力不同的学生。我不能简单地说有些程序员比其他程序员更有能力,虽然事实可能确实如此。即使是在相同能力水平的程序员之间,也存在很大的区别。我经常不可思议地看到以前学习得很挣扎的学生很快精通了某种特定的技巧,或者在其他领域天赋卓然的学生在一个新领域却暴露出明显的弱点。就像不存在两个完全相同的指纹一样,没有两个大脑是完全相同的,对于一个人来说非常容易的一堂课对于另一个人来说可能非常困难。
假设读者是一位美式足球教练,正在制订下一场比赛的进攻计划。由于伤病的原因,无法确定两名四分卫谁能够首发登场。这两名四分卫都具有高度的职业素养,但是和所有人一样,他们也有各自的优点和缺点。为一位四分卫所制订的完美比赛计划套用于另一位四分卫身上却可能带来糟糕的结果。
在创建总体计划时,教练需要根据队中的四分卫进行排兵布阵。为了实现最大的获胜机率,需要制订一个计划,既要认识到自己的优势,也要明白自己的弱点。
在制订自己的总体计划时,关键的步骤是认识到自己的优势和弱点。这并不困难,但它需要花费精力并且需要一个公平的自我评估。为了从错误中获益,不仅需要在程序中所出现的地方修正它们,还必须对它们进行关注,至少是在大脑里,最好是记录在文档中。通过这种方式,可以发现在其他情况下可能错失的行为模式。
下面将描述两种不同类型的弱点:编码弱点和设计弱点。编码弱点是指在实际编写代码时可能反复犯错的领域。例如,许多程序员在编写循环的时候,经常会出现迭代次数多1次或少1次的情况。这个错误称为栅栏柱错误,它取材于一个古老的难题,就是建造一条总长50m的栅栏并且每根栅柱之间相隔10英尺,一共需要几根柱子?大多数人的第一反应是5,但是如果仔细考虑,答案应该是6,如图8.1所示。
大多数编码弱点出现在由于程序员编写代码过于迅速或者缺乏充分准备而导致语义错误的情况下。反之,设计弱点在问题的解决或设计阶段经常出现。例如,我们可能不知道该怎么入手或者不知道怎么把以前所编写的子程序集成到一个完整的解决方案中。
图8.1 栅栏难题
尽管这两种类型的弱点存在一些重叠,但它们会导致不同类型的问题,因此必须按照不同的方式予以解决。
针对编码弱点的计划
在编写程序的时候,最令人气恼的事情莫过于花了几个小时的时间追踪一处语义错误,结果却发现只是一个非常简单而且很容易修正的错误。没有任何东西是完美的,因此没有办法完全消除这样的情况,但是优秀的程序员将会尽他所能避免相同的错误再次发生。
有一位程序员已经厌倦了C++编程中可能最为常见的语义错误:误用赋值操作符(=)代替了相等操作符(==)。由于C++的条件表达式的结果是整数,而不是严格的布尔值,因此下面这样的语句在语法上是合法的:
在这种情况下,整数值1被赋值给number,然后1这个值成为了条件语句的结果,C++把它当作true
处理。显然,程序员的意图其实是:
被这类错误的屡次发生搞得心烦气躁之后,这位程序员告诫自己用另一种方式来编写相等性测试,让数字值出现在左边。例如:
通过这种做法,如果他不小心再次犯了上面这个错误,1 = number这个表达式将不再是合法的C++表达式,因此会产生语法错误,会在编译时被捕捉。原来的错误在语法上是合法的,因此它只是个语义错误,在编译时可能会被捕捉,但也可能根本不会被捕捉。由于我自己也曾经多次犯过这个错误(有时候在查找这个错误时会急得发疯),因此也采用了这种方法,把数字值放在相等操作符的左边。采用这种做法之后,我发现了一些奇怪的事情。由于它与我平时所使用的风格相悖,因此在编写条件语句时把数字值放在左边会让我的思维暂时停顿。我会这么思考:“我需要记住把数字值放在左边,这样在误用了赋值符时就能发现这种情况”。正如读者所料,把这种想法在脑子里过一遍之后,绝不会再错误地使用赋值操作符,而是能够正确地使用相等操作符。现在,我不再把数字值放在相等操作符的左边,但在编写条件表达式时仍然会习惯性地停顿一下,使上面这个想法再过过脑子,这样就不会再犯这种错误了。
通过这个事情,我所得到的一个经验就是:首先要意识到自己在编码层次上的弱点,然后才能有效地避免它们。这是好消息,坏消息是我们必须通过实践才能认识到自己的编码弱点。关键的技巧是让自己知道为什么会犯某个特定的错误,而不仅仅是修正这个错误并继续下一步工作。这可以帮助我们确认自己有没有遵循的某个基本原则。例如,我们编写了下面这个函数,计算一个整数数组中所有正数的平均值:
初看上去,这个函数并没有什么问题。但是经过仔细观察,还是可以看到它存在一个问题。如果数组中没有任何正数,当循环结束时positiveCount
的值将是0,这将导致在函数结束时执行除零运算。由于这是浮点除法,因此程序可能不会实际崩溃,而是产生某种奇怪的行为,这具体取决于这个函数的返回值在整体程序中是怎样被使用的。
如果我们很快就设法运行了这段代码,并且发现了这个问题,可能会添加一些代码,处理positiveCount
为零的情况,并继续下一步工作。但是,如果想完善自己的编程能力,就应该问问自己犯了什么错误。当然,这个特定的问题是没有考虑到除零的可能性。但是,如果分析只是到此为止,并不会对未来提供多大的帮助。显然,此时应该考虑分母可能为零的其他情况,但这也不算一种非常常见的情况。反之,我们应该问问自己是否违背了什么基本原则。答案是:我们要坚持寻找那些可能导致代码失败的特殊情况。
考虑到这个基本原则之后,就很容易看到我们所犯错误的模式,因此在将来很容易捕捉到这类错误。问自己“这里是不是存在除零错误的可能性”远不如问自己“这个数据存在什么特殊情况”更为有用。提出作用面更宽的问题,除了能够想到不要出现除零运算之外,还会迫使自己考虑空数据集、超出预期范围的数据等问题。
针对设计弱点的计划
设计弱点需要一种不同的方法才能克服。但是,第一个步骤仍然是一样的,就是要认识到自己的弱点所在。很多人在这个步骤上存在问题,因为他们并不愿意对自己采取批评态度。人们总会想方设法隐瞒自己的失败。就像接受工作面试时,当一位面试官问你最大的弱点是什么时,你很可能会回答一些不会对面试结果产生影响的弱点,而不是坦率地承认自己的真正缺点。但是,就像超人也受制于氪星石一样,就算是最优秀的程序员也存在真正的弱点。
下面是程序员弱点的一个示例列表(当然并不完整),读者可以看看自己是否符合其中的几条。
过于复杂的设计
存在这个弱点的程序员所创建的程序常常具有过多的组成部分,或者具有过多的步骤。虽然程序能够完成任务,但它们无法让自己充满信心,就像穿上去的衣服一扯线头就会全部散架一样。很显然,它们是非常低效的。
不知如何着手
这种类型的程序员具有高度的惰性。也许是由于在解决问题上缺乏信心,也可能生来就是慢性子,这类程序员花费了太多时间考虑怎么开始解决问题。
疏于测试
这类程序员不喜欢对自己的代码进行正式的测试。这样的代码在一般情况常常能够很好地完成任务,但是面对特殊情况时常常会导致失败。还有一些情况下,这样的代码能够顺利地完成任务,但是对于程序员没有进行测试的大型问题,它就难以表现出应有的适应能力。
过分自信
自信是件好事,本书的目标之一就是培养读者的自信心。但是,过分自信和不够自信一样并非好事。过分自信会通过各种方式表现出来。过分自信的程序员可能会尝试一种超出需要的更复杂解决方案,或者在非常短的时间内就匆匆完成一个项目,导致粗率、缺陷丛生的程序产生。
脆弱领域
这种类型的弱点可谓五花八门。有些程序员一直在顺利地工作,但在遇到了某些概念后突然变得不知所措。以本书前面各章所讨论的话题为例,大多数程序员在面对某个领域时,就算完成了所有的习题,他们在这个领域的信心也要比在其他领域弱得多。例如,有些程序员会迷失于指针程序中;或者递归的概念会把有些程序员的脑子搞混。有些程序员在设计详尽的类时会遇到困难。这并不是说这些程序员就没有办法应付这些问题,但对他们而言这些是非常艰巨的任务,就像在泥地里开车一样。
我们可以通过不同的方法暴露自己的主要弱点。一旦认识到自己的弱点之后,就很容易针对它们制订计划。例如,对于经常忽略测试的程序员,在制订每个模块的编写计划时,可以明确地把测试作为必须完成的部分,在完成测试之前不能开始下一个模块的设计。或者,也可以考虑一种称为“测试驱动的开发”的设计用法。在这种惯用法中,首先编写测试代码,再编写填充这些测试的其他代码。对那些迟迟不能入手的程序员,可以采用问题的分治或削减原则,一旦他觉得可以就开始编写代码,当然还要知道将来可能需要对这些代码进行重写。对于那些常常设计得过于复杂的程序员,可以在总体计划中增加一个明确的重构步骤。关键在于,不管程序员的主要弱点是什么,它们只不过是项目成功完成的道路上的绊脚石而已。
根据自己的优点制订计划
根据弱点制订计划在很大程度上是为了避免错误。但是,良好的计划并不仅仅是为了避免错误。它还涉及到根据自己的当前能力以及可能受到的约束,尽可能实现最佳结果。这意味着我们还必须根据自己的优点制订总体计划。
读者可能觉得本节的内容不适合自己,至少目前为止还不适合。不管怎样,如果读者已经开始阅读本书,就有可能成为一名程序员。读者可能觉得自己在当前阶段还谈不上有任何优点,但事实上还是有的,即使自己并没有意识到它们。下面是一些常见的程序员优点的列表,当然并不完整。我对每个优点提供了描述和提示,以帮助读者判断自己是否具有这些优点:
细心
这种类型的程序员能够预料到特殊情况,在潜在的性能问题出现之前就预感到它们,而且绝不会让整体情况掩盖那些必须精心处理的细节,而这些细节又往往是实现完整和准确的解决方案所必需的。具有这个优点的程序员倾向于在编写代码之前先在纸上测试他们的计划,他们会小心细致地编写代码,并且经常进行测试。
快速学习能力
具有快速学习能力的程序员能够很快学会新的技巧,无论是一种已经熟悉的语言中的一项新技巧还是学习一个新的应用程序框架。这种类型的程序员享受学习新事物的挑战,可能会根据这个喜好来选择项目。
快速编码能力
具有快速编码能力的程序员无需很长时间就可以根据一本参考书捣鼓出一个函数。到了开始打字的时间,不需要特别地费劲,代码就会从指尖迅速涌出,并且其中很少出现语法错误。
永不放弃
对于有些程序员而言,讨厌的程序缺陷就像无法回避的个人遭遇一样。如同程序戴着皮革手套扇了程序员一个巴掌,然后轮到程序员对此做出回应。这类程序员始终头脑冷静、意志坚定,不会被挫折所击倒。他们坚信只要付出足够的努力,必将取得最后的胜利。
超级问题解决专家
假如读者在阅读本书时还不是一位超级问题解决专家,但是在了解了一些指导方针之后,觉得做所有的事情时都变得得心应手。那么,具有这种能力的程序员在刚刚接触一个问题的时候就会开始思考潜在的解决方案。
完美主义者
对于这类程序员而言,一个工作程序就像一件精妙的玩具。完美主义者绝不会丧失让计算机按照他的命令行事的激情,并且喜欢想方设法找点事情让计算机去做。在某种意义上,完美主义意味着不断向工作程序添加更多的功能,这种症状称为爬行功能主义。在他们眼里,也许可以对程序进行重构以提高性能,也许可以让程序在程序员或用户面前显得更精巧。
很少有程序员能够同时拥有上面所说的多个优点。事实上,有些优点会相互抵销。但是,每个程序员都有自己的优点。如果读者觉得自己不符合上面所说的任何一条,也只是意味着对自己还不够了解,或者其优点并不属于上面所提到的这几种类型。
一旦确认了自己的优点,就需要在总体计划中利用它们。假设读者具有快速编码能力,很显然它可以使任何项目更快地到达终点。但是,怎样才能以系统的方式利用这个优点呢?在正式的软件工程中,有一种方法称为快速原型法,就是在一开始编写一个程序的时候并没有深入的计划,需要通过连续的迭代予以完善,直到最终的结果能够满足问题需求。作为快速编码者,可以尝试采用这种方法:有了一个基本的思路之后就可以开始编写代码,用粗略的原型来指导最终程序代码的设计和开发。
如果读者具有快速学习能力,在每个项目开始的时候应该寻访新的资源或技巧来解决当前问题。如果既不具备快速学习能力,但也不会轻易被挫折所击垮,那么在项目开始的时候可以从最困难的部分入手,给自己最多的时间来处理它们。
因此,不管自己拥有何种优点,要保证在编程时利用它们。设计自己的总体计划,尽可能地把时间留给自己最擅长的事情。通过这种方式,读者在编程时不仅能够产生最好的结果,还将体会到最多的乐趣。
让我们观察创建总体计划的一个实例。这个计划的组成部分包括自己已经掌握的所有问题解决技巧,再加上对自身的优点和弱点的分析。我将使用自己的优点和弱点作为例子。
在问题解决技巧方面,我用了本书所讨论的所有技巧,但尤其钟爱“削减问题”技巧,因为这种技巧能够让我感觉到自己向最终的目标不断迈出坚实的步伐。如果目前还无法编写满足完整规范的代码,可以先忽略部分规范,直到有信心完成剩余的内容为止。
我最大的编码弱点是过于认真。我喜欢编程,因为喜欢看到计算机按照自己的命令行事。有时候,应该分析自己所编写的东西的正确性时,我会考虑:“直接让它运行吧,看看会发生什么。”这种做法的危险在于程序可能会失败。虽然程序看上去似乎很成功,但是它并没有覆盖所有的特殊情况。或者它虽然成功,但并不是我应该编写的最佳解决方案。
我喜欢优雅的程序设计,希望程序能够很方便地被扩展和复用。当我编写大型项目时,常常花费大量的时间开发其他途径的设计方案。总体而言,它是一个良好的能力,但有时这会导致我把过多的时间花在设计阶段,没有留下太多的时间实现最终所选择的设计。另外,这也会导致解决方案的过度设计。也就是说,有时候设计的解决方案会比实际所需要的解决方案更优雅、更容易扩展并且更健壮。由于每个项目的时间和金钱都是有限的,因此最佳的解决方案必须同时兼顾程序的质量和资源的节约。
我觉得自己最大的编程优点就是能够很快领会新概念并且热爱学习。虽然有些程序员喜欢一直使用相同的技巧,但我喜欢在项目完成时能够学到新东西,并且总是很乐于接受这类挑战。
有了这些思路之后,下面是我对一个新项目的总体计划。
为了弥补我的主要弱点,我严格地控制自己在设计阶段所花费的时间,或者说控制了在设计阶段所考虑的不同设计方案的数量。对于某些读者而言,这好像是种危险的想法。在进入编码阶段之前,难道不应该尽可能地多花点时间在设计阶段吗?大多数项目失败的原因难道不是因为在前期所花的时间太少从而导致后期的一连串妥协吗?这些顾虑当然是对的,但是我现在并不是为软件开发创建一条通用的指导方针,而是为自己制订处理编程问题的总体计划。我的弱点是过度设计而不是设计不足,因此控制设计时间这个规则对我而言是合理的。对于其他程序员而言,这样的规则很可能是灾难。有些程序员可能需要一个规则迫使他们把更多的时间花在设计上。
完成最初的分析之后,我就开始考虑这个项目是否有机会让自己学习新的技巧、库等知识。如果答案是肯定的,我就打算编写一个小型的测验台程序,对这些新技巧进行试验,然后再把它们吸收到自己所开发的解决方案中。为了克服过于认真这个弱点,在完成每个模式的编码时,可以添加一个简单的代码回顾步骤。但是,这并不是我的意愿所在。当我完成每个模块时,希望继续前进并让它实际运行。单纯地希望我在这个时候能够停下来就像在一个肚子饿得咕咕叫的人身边放上一袋打开的薯片,然后惊奇地发现这袋薯片被吃光了。在制订克服程序员弱点的计划时,不要让程序员跟自己的直觉做斗争。如果我创建了两个版本的项目:一个是原始的任由我处理的版本,另一个是经过优化的准备发行的版本。如果允许我对第一个版本按照自己的意愿行事,但是在经过完全的验证之前,不要把它的代码吸收到另一个优化的版本中,这样无疑更容易克服自己的弱点。
制订了总体计划之后,我们就可以开始动手了。这正是本书所讨论的内容:从一个问题(任何问题)开始,寻找一种解决方案的方法。在前面各章中,问题描述使我们可以一开始把目光瞄准某个方向。但是在现实世界中,大多数程序并没有阐述需要使用数组或递归,或者要求把程序的一部分功能封装到一个类中。反之,程序员必须把这些决策作为问题解决过程的组成部分。
一开始,很少有需求能够让问题看上去变得更简单。不管怎样,设计需求是一种约束条件,难道约束条件不会使问题变得更困难吗?虽然这是对的,但不可否认的是所有的问题都有约束条件,只不过有些约束条件能够很明确地看到,有些则不是非常明显。例如,一个特定的问题没有明确表示是否需要动态分配的内存,并不意味着在做出这个决定时不会受到影响。对于一些更宽泛的约束条件,无论是关于性能、可修改性、开发速度还是其他方面的约束条件,一旦做出了错误的设计选择,就会导致难以满足甚至无法满足这些约束条件。
想象有一帮朋友要你选择一部让所有人一起观看的电影。如果一位朋友明确表示想看喜剧片,另一位朋友不喜欢老式电影,还有一位朋友列出了5部她刚刚看过的电影并表示不想重复观看。这些约束条件会导致你的选择变得困难。但是,如果每个人所提的建议是“只要挑部好看的就行”,你所面临的选择就会更加困难,很可能会挑选出一部至少有一位朋友根本不喜欢看的电影。
因此,按照更大、更广泛的定义,约束条件弱的问题常常是最难解决的。但是,它们可以通过本书所描述的问题处理技巧来解决,只是需要花费更多的时间。掌握了这些技巧并且制订了总体计划之后,就有能力解决任何问题。
为了证明刚才所讨论的观点,我打算带领读者完成绞刑者程序的第一个步骤。它是一种经典的儿童游戏,不过在此基础上我增加了一个变化。
在阅读问题描述之前,我们首先回顾一下这个游戏的基本规则。第1位玩家选择一个单词并告诉第2位玩家这个单词包含了几个字母。接着,第2位玩家猜一个字母。如果该字母确实是在这个单词之中,第1位玩家就说出这个字母出现在单词中的位置。如果这个字母在单词中的出现次数不止1次,那么必须说明它所有的出现位置。如果这个字母并没有出现在这个单词之中,第1位玩家就在他所绘制的一幅绞刑者图画中添上一笔。如果第2位玩家猜中了这个单词的所有字母,那他就获得了胜利。但是,如果第1位玩家画完了绞刑者,他就获得了胜利。关于画完这个绞刑者一共需要多少笔,存在不同的规则。因此,换用更通俗的说法,两位玩家在游戏之前先约定第2位玩家猜错多少次就算第1位玩家获胜。
既然我们已经了解了基本规则,现在可以观察特定的问题,包括我所增加的那个具有挑战性的变化。
编写一个程序,它基于文本的猜字游戏(也就是说,不需要实际绘制绞刑者,只需要记录不正确的猜测数量)的玩家1。玩家2通过指定待猜测的单词的长度以及输掉游戏时的猜错次数,设置游戏的难度。
我所增加的那个变化是程序可以进行作弊。它并不是在游戏开始时就实际挑选一个单词。程序可以避免挑选单词,只要当玩家2失败时,程序就能够显示一个与玩家2所提供的所有信息匹配的单词。所有猜中的字母必须出现在正确的位置上,猜错的字母不能出现在最终的单词中。当游戏结束时,玩家1(程序)会告诉玩家2这个单词已经被选好。因此,玩家2永远无法证明程序是在作弊,只不过发现自己的获胜机会很渺茫而已。
按照现实世界的标准,这并不是一个非常复杂的问题,但它足以说明当我们处理一个指定了结果但没有指定标准解决方法的编程问题时所面临的各种情况。根据问题描述,我们可以打开自己的开发环境,从十几个不同的情况挑选一个开始编写代码。当然,这是错误的方法,因为我们在开发程序之前总要制订一个计划。因此,我需要把自己的总体计划应用于这个特定的例子中。
我的总体计划的第1部分是限制在设计阶段所花费的时间。为了实现这一点,我在编写代码之前要对设计进行仔细考虑。但是,我相信在这个阶段进行一些试验是必要的,它们可以帮助我想出这个问题的解决方案。我的总体计划也允许创建2个项目:一个是粗略的原型,另一个是经过优化的最终解决方案。因此,我允许自己在真正的设计工作开始之前为那个原型编写代码,但不允许在最终解决方案中编写代码,除非我相信自己的设计已经完成。这并不能保证我可以对第2个项目的设计完全满意,但它为实现这个目标提供了最好的机会。
现在是时候对问题进行划分了。在前面各章中,我们曾列出完成一个问题所需要的所有子任务,因此在这里我也将列出一个子任务列表。但是,现在完成这个任务还是有点困难的,因为我不知道这个程序将怎样进行作弊。我需要对这个问题进行进一步研究。
绞刑者程序的作弊是一个非常具体的问题,我相信通过搜索常规的组件来源是无法找到任何帮助的。不可能存在像NefariousStrategy(违法乱纪策略)这样的模式。现在,关于怎样进行作弊,我只有一个非常模糊的思路。我考虑列可以在一开始选择一个难点的单词,只要玩家2选择了这个单词中没有出现的字母就一直沿用它。但是,当玩家2猜中了这个单词中的一个字母时,我可以换个单词,选择一个所包含的字母到目前为止还没有被猜过的单词。换句话说,我将尽可能地否认玩家2的猜测。这是一种思路,但光有这个思路是不够的,我还需要一些可以实现的东西。
为了验证自己的思路,我打算在纸上模拟玩家1,对一个单词列表进行操作。为了简单起见,假设玩家2所设定的单词长度为3个字母,并且表8.1列出了我所知道的所有3字母的单词。我假设自己所选择的第一个“问题单词”是列表中的第1个单词bat。如果玩家2所猜的字母不是b、a或t,我就说“错”,然后朝胜利又迈进了一步。如果玩家2猜中了这个单词中的任意一个字母,我就挑选另一个单词,只要它不包含玩家2之前所猜测的任何字母。
但是,看了这个表格之后,我无法保证这种策略是最好的。在有些情况下,它可能是合理的。假设玩家2猜了b。这个表格中的其他单词都不包含b,因此我可以切换到其他任何单词。这意味着我最大限度地降低了风险,我只是从单词列表中消除了1个可能的单词。但是,如果玩家2接着猜了a会怎么样呢?如果我回答“错”,我就必须排除所有包含了a的单词,这样就只剩下表8.1第2列的那3个单词可以供我选择。如果我决定承认字母a是正确的,那么我还剩下5个单词可以选择,如第3列所示。但是,注意这种扩展选择只有当5个单词中的a都处于同一位置时才成立。一旦声明某次猜测是正确的,我必须指出这个字母出现在单词中的位置。剩下的、可以用来应付未来猜测的单词越多,我对游戏获胜的信心就越足。
表8.1 示例单词列表
所有单词 |
不带a的单词 |
带a的单词 |
---|---|---|
bat |
dot |
bat |
car |
pit |
car |
dot |
top |
eat |
eat |
saw |
|
pit |
tap |
|
saw |
||
tap |
||
top |
比外,即使我设法避免在游戏中早早就暴露字母,但还是要预计玩家2最终是否会做出正确的猜测。例如,玩家2可以从所有的元音字母开始猜测。因此,当一个字母被暴露时我必须决定该怎么应对。根据这个示例列表的试验,我必须要找到这个字母最常出现的位置。从这个角度出发,我认识到用这种方法进行作弊是错误的。我不应该事先挑选一个单词,即使是临时的,只要追踪所有可以选择的有可能性的单词就可以了。
有了这个思路之后,我可以用一种不同的方式来定义作弊:使候选单词列表中的单词尽可能多。对于玩家2所做出的每次猜测,这个程序必须要做出一个决定。它应该表示猜中还是猜错呢?如果表示猜中,被猜中的字母出现在哪个位置?我会让程序维护一个不断减少的候选单词列表,并在每次猜测之后,所做出的决定就是使这个列表保留尽可能多的单词。
现在我已经对问题有了足够的理解,可以创建自己的子任务列表了。对于同等规模的问题,在早期就列出这样一个清单可以有很好的机会能够确定一些操作。这是毫无疑问的,因为我在总体计划中已经预料到自己不会第一次就创建出一个完美的设计。
存储并维护一个单词列表
这个程序必须维护一个合法的英语单词列表。因此,这个程序必须从一个文件中读取一个单词列表并在内部以某种格式存储它们。当程序开始作弊后,随着游戏地不断进行,这个列表中的单词将不断减少。
创建一个特定长度的单词子列表
假设意图是维护一个候选问题单词的列表,那么我必须从一个由玩家2所指定长度的单词列表开始游戏。
追踪被选择的字母
这个程序需要记住哪些字母已经被猜过,其中有哪些是不正确的、哪些看上去是正确的以及它们在问题单词中所出现的位置。
没有出现某个字母的单词计数
为了便于进行作弊,我需要知道列表中有多少单词并不包含最近被猜测的字母。记住,程序将决定这个最近被猜测的字母是否出现在问题单词中,其目的是使候选单词列表保留尽可能多的单词。
根据字母和位置确定最大数量的单词
这看上去是难度最大的操作。我们假设玩家2刚刚猜了字母d
并且当前游戏所设定的问题单词的长度为3。当前的候选单词列表中可能一共有10个单词包含了d
,但这并不重要,关键在于程序必须说明这个字母出现在问题字母中的哪个位置。我们把字母在单词中的位置称为模式。因此,d??
就是一个三字母模式,它的第1个字母为d
,另两个字母可以是d
之外的任意字母。如表8.2所示。假设第1列的单词列表包含了程序所知的所有含d
的三字母单词。另外几列按照该模式对这个列表进行分解。出现次数最多的模式是??d
,一共有17个单词。17这个数量将与候选列表中不包含d
的单词数量进行比较,以确定程序应该表示猜中还是猜错。
表8.2 三字母单词
所有单词 |
?dd |
??d |
d?? |
d?d |
---|---|---|---|---|
add |
add |
aid |
day |
did |
aid |
odd |
and |
die |
|
and |
bad |
doe |
||
doe |
bed |
dog |
||
dog |
bid |
dry |
||
dry |
end |
due |
||
due |
fed |
|||
did |
had |
|||
die |
hid |
|||
doe |
kid |
|||
dog |
led |
|||
dry |
mad |
|||
due |
mod |
|||
end |
old |
|||
fed |
red |
|||
had |
rid |
|||
hid |
sad |
|||
kid |
||||
led |
||||
mad |
||||
mod |
||||
odd |
||||
old |
||||
red |
||||
rid |
||||
sad |
创建一个与模式匹配的单词子列表
当程序声明玩家2猜中一个字母后,它将创建一个新的候选单词列表,只包含与所选择的字母模式匹配的单词。在前一个例子中,如果我们声明d为猜中,那么表8.2的第3列将成为新的候选单词列表。
在游戏结束之前一直进行
所有操作就绪之后,我需要编写代码,把所有的操作集成在一起并实际运行游戏。这个程序应该反复请求玩家2(用户)进行猜测、确定拒绝或接受这次猜测所剩下的候选单词列表哪个更长,并相应地削减这个单词列表,然后根据已揭晓的所有正确猜中的字母以及此前所猜测的所有字母,显示最终的问题单词。这个过程将一直持续,直到游戏结束,即其中一位玩家获胜。因此,我还需要制订游戏在什么条件下可以结束。
尽管前面列出的所需操作列表看上去是比较粗略的,但设计决策却是根据这些操作做出的。考虑“创建一个与模式匹配的单词子列表”这个操作。这个操作将出现在我的解决方案中,至少将出现在它的初始版本中。但是,严格地说,它根本不是必需的操作。“创建一个特定长度的单词子列表”操作同样不是。我并不是为了维护一个不断变小的候选问题单词列表,而是如何在整个游戏过程中保留一开始时的问题单词主列表。但是,这将导致其他操作变得复杂。“没有出现某个字母的单词计数”操作不能仅仅迭代候选问题单词列表,并对不包含指定字母的所有单词进行计数。由于将对主列表进行搜索,因此它还必须检查每个单词的长度,并判断这个单词是否与到目前为止问题单词所暴露的字母匹配。我觉得自己所选择的路径在总体上变得更容易了,但必须意识到即使是早期的选择也会影响最终的设计。因此,除了在开始阶段把问题分解为子任务之外,我还必须做出其他决定。
怎样存储单词列表
这个程序的关键数据结构是单词列表,程序将在游戏期间不断缩减这个列表。在选择数据结构时,我进行了下面这些考虑。首先,我相信并不需要对列表中的单词进行随机访问,而是需要把这个列表从头至尾作为整体进行处理。其次,我并不知道这个列表的初始长度。再次,我需要经常对这个列表进行削减。最后,这个程序经常会使用标准string
类的方法。综合上面这些因素,我决定这个结构的初始选择是标准模板库的list
类,并用string
作为它所包含的数据项的类型。
怎样追踪被猜的字母
被选择的字母在概念上是一个set。也就是说,一个字母或者被选择,或者没有被选择,并且每个字母被选择的次数不超过1次。因此从本质上说,这个问题就是字母表中的一个特定字母是否为一个“被选择的”set的一个成员。因此,我打算用一个长度为26的bool
类型的数组来表示被选择的字母。如果这个数组被命名为guessedLetters
,并且a在游戏进行过程中已经被猜过,那么guessedLetters[0]
就是true,否则就为false。guessedLetters[1]
表示b,接下来以此类推。我将使用本书一直使用的范围转换技巧在小写字母a和它在数组中的对应位置之间进行转换。如果letter
是个表示小写字母的字符,那么guessedLetters[letter - 'a']
就是它在数组中的对应位置。
怎样存储位置模式
我将要实现的一个操作“创建一个与模式匹配的单词子列表”将使用单词中某个字母的位置模式。这个模式是由另一个操作“根据字母和位置确定最大数量的单词”所产生的。因此,我应该用什么格式表示这种数据呢?模式是一系列的表示一个特定字母所出现位置的数字。存储这些数字的方法有很多种,但我为了保持简单,使用另一个list
,数据项的类型为int
。
是不是应该编写一个类
由于我用C++编写这个程序,因此可以自己决定是否使用面向对象编程。我首先想到的是上面列表中的许多操作可以很自然地放在一个称为wordList
的类中,再添加根据指定的标准(即长度和模式)删除单词的方法。但是,由于想尽量避免做出以后可能会被撤销的设计决定,因此我打算在第一个粗略的试验程序中完全采用过程性编程。一旦我已经解决了这个程序的困难部分并实现了操作列表中的所有操作,就可以更好地决定是否在最终的版本中采用面向对象编程。
现在可以开始做有趣的事了,我打开自己的开发环境并投入工作。这个程序将要使用标准库中的一些类,为了清晰起见,我首先列出了所有头文件和相关的using
指令:
现在,我准备为自己的操作列表中的操作编写代码了。在某种程度上,我可以按照任意顺序为这些操作编写代码,但首先打算编写的函数是从一个包含单词的普通文本文件中把单词读取到自己所选择的list<string>
结构中。在这个时候,我意识到需要找到一个现成的单词文件,而不用自己输入这些单词。幸运的是,用Google搜索“word list”显示了一些提供普通文本格式的英语单词(每行显示一个单词)的网站。我已经掌握了怎样在C++中读取文本文件,但即使自己并不熟悉这个操作,也可以编写一个小型的测试程序来练习这个技巧然后再用于绞型者作弊程序。我将在本章的后面内容中讨论这种做法。
找到了文件之后,我可以编写这个函数:
这个函数非常简单,因此我只进行一些简要的说明。ifstream
对象 表示一个输入流,它的工作方式就像cin
一样,区别在于它是从一个文件中而不是从标准输入流中进行读取。如果它的构造函数无法打开这个文件(通常意味着无法找到这个文件),那么这个对象就为NULL
,这是我明确检查的一种情况。如果这个文件存在,就在一个循环中对它进行处理。这个循环每次把这个文本中的一行文本读取到一个字符数组中,并把这个数组转换为一个string
对象,然后再把它添加到一个list
对象中。我最终所使用的英语单词文件包含了带撇号的单词,它们对于这个游戏是不合法的,因此将明确排除它们。
接着,我编写一个函数,显示这个list<string>
中的所有单词。这并不是必需的操作,我不会在游戏中使用这个函数(毕竟,它只能帮助被欺骗的玩家2),但它很适合测试我的readWordFile
函数是否正确地完成了任务:
它在本质上与前一章所介绍的列表遍历代码是相同的。注意,我把它的参数声明为常量引用。由于这个list对象在一开始时可能相当庞大,传递引用参数可以减少函数调用的开销,而传递值参数就必须复制整个list。把这个引用参数声明为常量参数可以表示这个函数将不会修改list,这就使它的代码更容易读懂。常量list需要使用常量迭代器。cout
流无法输出string对象,因此这个方法使用c_str()
函数生成对应的以null字符结尾的字符数组。
我使用相同的结构编写了一个函数,以完成对list对象中不包含某个指定字母的单词进行计数:
正如我们所看到的那样,这是一个相同的基本遍历循环。在循环内部,我调用了string
类的find
方法,它返回它的char
参数在这个string
对象中的位置。如果未找到这个字符,就返回一个特殊值npos
。
我使用相同的基本结构编写了一个函数,以完成从单词列表中删除所有与指定长度不匹配的单词:
这个函数是一个非常好的例子,说明了我们所编写的每个程序都为自己提供了一个很机的机会以加深对程序工作方式的理解。这个函数对我来说很容易编写,因为通过自己以前所编写的程序理解了“幕后”所发生的事情。这个函数使用了与前面的函数相同的遍历代码,但循环内部的代码就比较有趣。erase()
方法从一个list
对象中删除一个由迭代器所指定的数据项。但是,根据我们在第7章实现链表类的迭代器模式的经验,我们知道迭代器可以肯定就是指针。根据我们在第4章的指针操作经验,我们知道当一个指针是野引用、指向已经被删除的东西时,它没什么用处并且往往非常危险。因此,我知道需要在这个操作之后为iter
赋一个合法的值。幸运的是,erase()
的设计者已经预料到了这个问题并通过这个方法返回一个新的迭代器,指向被删除的元素之后紧随的那个元素。因此,我可以把这个值赋值给iter
。另外,注意我只有在没有从list
中删除当前字符串时才明确把iter
推进一步,因为用erase()
的返回值进行赋值时已经把这个迭代器向前推进了一步,我不想跳过任何数据项。
现在开始进入困难的部分:在剩余的单词列表中寻找一个指定字母的最常见模式。这是使用分治法技巧的另一个机会,我知道这个操作的其中一个子任务是确定一个特定的单词是否与一个特定的模式匹配。记住,模式就是list<int>
对象,其中每个int
值表示字母出现在单词中的位置。因此,为了让一个单词匹配一个模式,这个字母必须出现在单词中的指定位置,而不能出现在单词中的其他位置。有了这个思路之后,我就可以通过遍历一个字符串来测试它是否匹配了。对于这个字符串中的每个位置,如果出现了指定的字母,我就确定这个位置是在模式中。如果出现了其他字母,我就确定这个位置不是在模式中。
为了简单起见,我首先编写一个单独的函数,以检查一个特定的位置编号是否出现在一个模式中:
熟悉了前几个函数之后,这段代码显得相当简单。我简单地对list
进行遍历,搜索number
。如果找到就返回true
,如果到达list
的尾部还没找到就返回false
。现在,我可以实现通用的模式匹配测试了:
正如我们所看到的那样,这个函数遵循了之前所制订的计划。对于这个字符串中的每个字符,如果它与letter
匹配,就确认当前位置是在这个模式中;如果这个字符并不与letter
匹配,就确认这个位置并不在这个模式中。如果一个位置并不与这个模式匹配,这个单词就被拒绝;否则,遍历到这个单词尾部的时候,这个单词就被接受。
此时,我感觉到如果list中的每个单词都包含了指定的字母,寻找最常见模式的任务就会容易很多。因此,我编写了一个简单的函数,以去掉那些不包含这个字母的单词:
这段代码只是前几个函数所使用的思路的组合。既然我已经想到了这个函数,就需要一个相反的函数去掉那些包含了指定字母的单词。我将使用这个函数,当程序表示最近一次猜测为错时对候选单词列表进行削减。
现在,我准备为特定的字母寻找单词列表中最常见的模式了。我思考了一些方法并挑选了自己认为最容易实现的一种。首先,我调用上面的函数以删除所有不包含指定字母的单词。接着,我提取列表中的第1个单词,确定它的模式,并对列表中具有相同模式的其他单词进行计数。当我进行计数时,它们都将从列表中被删除。然后,对现在位于列表头部的那个单词执行相同的处理,直到这个列表为空。其结果如下所示:
这个列表之所以作为值参数传递的!,是因为这个函数在处理过程中将把这个列表清空,而我并不想影响这个函数的调用代码实际所传递的参数。注意maxPattern
和maxPatternCount
都只是作为输出参数。它们将把最常出现的模式和出现次数传递给这个函数的调用代码。我删除了不包含letter
的所有单词。接着,进入这个函数的主循环,它在列表不为空时将一直继续。循环内部的代码分为三个主要部分。首先,一个for
循环构建了列表第1个单词的模式。接着,一个while
循环对列表中与这个模式匹配的单词进行计数。最后,我采用第3章所讨论的“山丘之王”策略,观察这个计数是否大于到目前为止的最大计数值。
我所需要的最后一个功能函数将显示到目前为止猜测的所有字母。读者应该还记得我把它们存储在一个包含26个bool
值的数组中:
注意,我把一个范围的基本值(在这个例子中就是字符a)加上另一个范围的一个值,这个技巧是在第2章中首先采用的。
现在,我已经完成了所有的关键子任务,可以尝试解决整个问题了。但是,还有很多函数未经过完全的测试,我想尽快对它们完成测试。因此,我并不打算在一个步骤中处理剩余的所有问题,而是打算对问题进行削减。为此,我打算把有些变量(如问题单词的长度)作为常量。
由于我最终将会抛弃这个版本的程序,因此可以毫无顾虑地把整个游戏的逻辑放在main
函数中。但是,由于结果非常长,因此我打算分阶段显示这些代码。
第1部分的代码设置了玩这个游戏时所需要的常量和变量,这段代码大部分看上去都非常容易理解。单词列表是根据一个文件创建的,然后削减为指定的单词长度,在此例中为常量值8。变量misses
用于存储玩家2猜错的次数,而变量discoveredLetterCount
用于追踪这个单词所暴露的位置个数(因此,如果d出现了2次,猜d就把这个值增加了2)。变量revealedWord
用于存储玩家2当前已知的问题单词,用星号表示到目前为止还没有被猜中的字母。bool类型的数组guessedLetters
用于追踪到目前为止所猜测的特定字母,用一个循环把它的所有值都设置为false。最后,变量nextLetter
用于存储玩家2的当前猜测。我输出revealedWord
初始值,然后进入主要的游戏循环。
出现了以下两种情况之一就可以结束游戏。其一,玩家2发现了单词中的所有字符,使discoveredLetterCount
达到了wordLength
的值;其二,玩家2的猜错次数达到了maxMisses
值。因此,只要这两个条件都没有被满足,这个循环就会一直持续。在循环内部,从用户那里读取了下一次猜测字母之后,guessedLetters
数组中对应的位置就会被更新。然后,作弊就开始了。程序调用countWordsWithoutLetter
,确定如果把这次猜测声明为错误时单词列表中还剩下多少个候选单词,并调用mostFreqPatternByLetter
函数确定如果承认这次猜中最多还能剩下多少个候选单词。如果前者更大,就删除含有被猜测字母的单词,并且把猜错数加1。如果后者更大,就采用mostFreqPatternByLetter
函数所提供的模式并更新revealedWord
值,同时从单词列表中删除所有与这个模式不匹配的单词。
代码的剩余部分被我称为“验尸循环”,循环之后的操作是由“杀死”循环的条件所决定的。在这里,要么是我们的程序成功地通过作弊获得胜利,要么是玩家2克服了所有的困难迫使程序显示完整的单词。注意,当程序获胜时,列表中至少还保留一个单词,因此我只显示第1个单词,并声称这就是我所挑选的单词。更邪恶的程序可能会在剩余的单词中随机地挑选一个,以减少对手发现作弊的可能性。
我已经把所有代码集中在一起并对它进行了测试,它能够完成任务,但很显然还需要很多改进。除了所有设计方面的考虑之外,这个程序还缺少很多功能:它并不允许用户指定问题单词的长度或允许猜错的次数;不检查被猜测的字母之前是否被猜过;更有甚者,它甚至没有检查输入的字符是不是小写字母;它还缺少很多界面友好性,例如没有告诉用户目前还允许猜错几次。另外,我觉得如果程序提供再玩一次的功能,而不是生硬地迫使用户重新运行这个程序会更好一些。
至于设计方面,当我思考程序的最终版本时,打算严肃地考虑采用面向对象设计。单词列表类看上去像是一个很自然的选择,而上面的main函数实在是过于庞大了。我喜欢采用模块化的、易于维护的设计。我觉得main函数应该尽量短小精悍,它的作用就是指挥各个子程序完成真正的工作。因此,上面的main函数需要分解为几个函数。另外,我的一些初始设计选择可能需要重新加以考虑。例如,站在事后诸葛的角度,以list<int>
的形式存储模式似乎显得有些臃肿。也许我可以考虑采用一个bool
类型的数组,就像guessedLetters
一样。
也许我应该寻找另一种结构。现在我还需要回过头来观察在解决这个问题时是否有机会学习新的技巧。我在思考是否存在自己没有考虑到的特殊数据结构能够帮忙。尽管我最终还是决定采用原先的选择,但仍然可以从这种思考中学到很多东西。
尽管所有这些决定仍然是若隐若现的,但我觉得正沿着自己的道路前进。让一个工作程序满足问题的本质需求是一个非常重要的步骤。我可以非常轻松地在原始版本中对不同的设计思路进行试验,自己的信心来源就是已经拥有了一个解决方案,只不过现在的目标是寻找一个更好的解决方案而已。
创建还原点
Microsoft Windows操作系统在安装或更改系统组件之前会创建一个还原点。还原点包含了关键文件的备份拷贝,例如注册表。如果一次安装或更新导致了严重的问题,可以通过复制这些文件有效地“回滚”或撤消到还原点。
我强烈建议在自己的源代码中采用与还原点相同的方法。当我们已经有了一个预期在将来会进行修改的工作程序之后,应该创建整个项目的一份拷贝,然后只对这份拷贝进行修改。这种做法非常省力,如果以后发觉自己的修改不合适,就可以节省大量的时间。程序员很容易陷入这样的思维陷阱:“我已经完成过这件事件,因此再完成一次肯定没问题”。通常情况下这是正确的,但是在“知道自己可以重新做某件事情”和“直接拿来旧的源代码供直接参考”之间还是存在很大的差别的。
我们还可以使用版本控制软件,它实现了复制和存储项目文件的自动化。版本控制软件所实现的功能不仅仅是“还原点”功能。例如,它还允许多个程序员独立地对同一批文件进行操作。虽然对这类软件的讨论超出了本书的范围,但是作为程序员,还是应该对此有所了解。
目前为止,读者是否已经发现了我在这个解决方案中采取的所有问题解决技巧?我为解决这个问题制订了一个计划。和往常一样,这是所有问题解决技巧中最为关键的一个。我决定首先完成第一个版本的解决方案,采用自己非常熟悉的数据结构即数组和list
类。我简化了程序的功能,这样更容易编写这个粗略而可行的版本,并以最快的速度对代码进行测试。我把问题划分为不同的操作,并把每个操作实现为一个不同的函数,这样就可以对程序的不同片段进行独立地操作。当还不清楚怎样进行作弊时,我进行了试验,把“作弊”重新表述为“最大限度地保留候选单词列表的长度”,这对我而言是一个可以实现的具体概念。在实现所有操作的特定细节方面,我采用了本书中所讨论的各种问题解决技巧。
我还成功地避免了遭遇挫折,读者也要对自己充满信心。
在继续讨论之前,读者必须清楚地理解我在这个问题的解决过程中所采取的步骤。读者在解决这个问题时并不一定要采取相同的步骤。上面所显示的代码不见得是这个问题的最佳解决方案,也不一定比读者所想出来的方法更合适。我希望这个例子能说明不管问题的规模如何,它们都可以用本书所使用的各种基本技巧进行解决,只不过有时需要采取一些变化。如果读者所面临的问题规模要比这个例子复杂1倍甚至10倍,它可能对读者的毅力是很大的挑战,但是读者最终还是有能力解决它。
还有一个话题需要讨论。在精通本书的问题解决技巧之后,如果我们想把程序员作为自己毕生的事业,还需要走出关键的一步。但是,就像大部分职业一样,这是一条没有终点的道路,因此我们必须设法完善自己,成为更优秀的程序员。和编程中的每个任务一样,我们也应该为自己学习新技巧和新技术制订计划,而不是东一榔头西一锤子式地攫取新知识。
在本节中,我们将讨论读者可能想要获取新技巧的一些领域,并讨论每个领域的一些系统性的学习方法。所有领域的一个共同特点是必须把想要学习的东西运用在实践中。这也是本书的每一章都以习题结尾的原因,读者应该已经完成所有的习题了吧?阅读新的编程思路是学会它们的关键第一步,但也仅仅是第一步。为了达到在现实世界的问题的解决方案中熟练运用一种新技巧的程度,首先应该在一个规模较小的问题中试验这个新技巧。记住,我们的基本问题解决技巧之一就是对问题进行削减,以使自己所处理的每个状态只有一个实质性的元素。我们不需要在学习新技巧的同时解决一个将成为解决方案核心的重要问题,因此这样一来,自己的注意力会被两个困难问题所分散。
我觉得C++在编写代码方面是一种优秀的语言,并且在第1章已经解释了为什么它还是一种非常适合学习的语言。没有一种语言在所有方面都比其他语言更为出色,因此优秀的程序员应该学习几种不同的语言。
花时间学习
尽可能在使用一种新语言编写代码之前,留出时间对它进行研究。如果读者用一种以前从未使用过的语言解决一个不是很简单的问题,就违背了一个重要的问题解决规则:避免受挫。为自己设置任务学习一种语言,在完成这个任务之后才能用这种语言完成“真正的”程序。
当然在现实世界中,我们有时候无法完全控制分配给自己的项目。在任何时刻,我们都可能接到请求用一种特定的语言编写一个程序,并且这个请求的时间期限非常紧张,在处理实际问题之前没有多少时间供我们悠闲地研究这种语言。防止出现这种情况的最好方法是在使用一种新语言之前就未雨绸缪,对它有所研究。我们应该对自己感兴趣的语言或者在以后的编程工作中很可能会用到的语言进行研究。这是从短期来看时间效率不高,但从长期来看能够收到丰厚回报的又一种情况。即使结果证明在不远的将来并不需要使用现在所研究的语言,但是对另一种语言的研究仍然能够提高自己所掌握语言的技能,因为它迫使你用新的不同方式进行思考,打破了旧思维方式,使你能够从新的视角审视自己的技巧和技术。我们可以把它看成是编程中的交叉培训。
从自己所知道的开始
当我们开始学习一种新的编程语言时,应该对它毫无了解。但是,如果它并不是我们所学习的第一种编程语言,那么我们实际上已经掌握了很多编程技巧。因此,学习一种新语言的一个非常好的方法就是理解怎样用这种新语言改写自己用另一种已经掌握的语言所编写的代码。
如前所述,我们需要通过实践来学习,而不能仅仅通过阅读。找到一些用其他语言所编写的程序,然后用这种新语言重新编写它们。对单独的语言要素(如控制语句、类、其他数据结构等)进行系统性地研究,目标是尽可能地把自己在其他语言上的知识和技能转移到这种新语言上。
研究区别所在
下一个步骤是研究新语言与已掌握语言的区别所在。虽然两种高级语言可能具有广泛的相似之处,但它们之间肯定存在不同的地方,否则也没有必要选择新语言来完成某个项目了。同样,我们要通过学习来完成这个目标。例如,仅仅通过阅读了解“一种语言的多选择语句允许它的条件为某个范围的值(C++的switch
语句只能使用单独的值)”的效果远远不如在实际编写代码时使用这个功能编写有意义的代码。
很显然,这个步骤对于那些存在显著匹别、但又同等重要、并且具有共同祖先的语言是极为重要的,例如C++、C#和Java,它们都是C的面向对象的后代。语法上的相似性使我们很容易误以为自己对新语言理解甚深,实际上却并非如此。考虑下面的代码:
如果这两行是以C++代码的形式出现在你的面前,你会认为第1行创建了integerListClass
类的一个对象,第2行调用了这个对象的addInteger
方法。如果这个类确实存在并且具有接受一个int参数的方法,这段代码完全没有任何问题。现在,我告诉你这段代码是用Java而不是C++编写的。从语法上说,这两行代码并没有不合法的地方。但是,在Java中,光凭类对象的一个变量声明并不能创建这个对象,因为这个对象变量实际上是个引用。也就是说,它的行为与指针相似。为了在Java中执行相同的步骤,正确的代码应该是:
我们可能很快理解了Java和C++之间的这个特定区别,但许多其他区别可能非常微妙。如果没有花时间去发现它们,那么在新语言进行调试时可能会变得极为困难。当我们回顾自己用新语言所编写的代码时,内心深处对其他语言的固有思维可能会向自己反馈不正确的信息。
研究优秀的代码
在本书中,我的一个观点是:不应该通过直接拿来别人的代码并对它进行修改来学习编程。但是,有时候研究其他人的代码是非常重要的。虽然可以通过编写一系列的原创程序来学习一种新语言的技能,但是为了达到精通的程度,我们还需要参考其他精通这种语言的人所编写的优秀代码。
我们并不是想要“剽窃”这样的代码,也不打算借用这段代码解决一个特定的问题。反之,我们通过观察现有的代码,以发现这种语言的“最佳实践”。观察编程专家的代码,不仅要明白这位专家想要做什么,还要明白他为什么要这样做。如果代码附有注释,那就再好不过了。要区分某种做法仅仅是风格上的选择还是为了实现性能的优化。完成了这个步骤之后,就可以避免一个常见的陷阱。程序员们常常对一种新语言有所了解之后就匆匆上手,结果他们所编写的代码非常脆弱,并没有利用这种语言的所有特征。例如,你是一位被要求用Java编写代码的C++程序员,显然不能安于用C++编写代码。反之,你要按照Java程序员所采用的方式编写真正的Java代码。
和其他所有事物一样,要把自己所学习的知识投入到实践中。拿出原先的代码并对它进行修改,以完成一些新的任务。然后把代码扔在一边,尝试重新编写它。目标是能够对这样的代码得心应手,足以回答其他程序员所提出的相关问题。
需要强调的是,这个步骤出现在其他步骤之后。在到达研究其他人所编写的新语言代码这个阶段之前,我们应该已经学习了这种新语言的语法,并把自己通过其他语言所学习的问题解决技巧应用于这种新语言。如果我们首先研究用新语言所编写的长长的程序例子,并对这些例子进行修改来缩短学习过程,很可能会限制自己的学习深度。
当你认为自己“知道”了一种语言时,并不会意识着你已经了解了这种语言的所有知识。即使精通了这种语言的语法,总是会存在新的方法能够组合现有的语言特性来解决问题。这些新方法大多已经在前一章讲述“组件”时进行了讨论,我们在第7章讨论了怎样创建组件知识库。其中一个重要的因素就是努力。一旦已经掌握了用某种方法解决问题的能力,就容易依赖自己已经知道的方法而停止对新事物的追求。这就像一位棒球投手能够投出一种犀利的快球,但不知道怎样投其他类型的好球。虽然有些投球手仅靠一种投球姿势就实现了成功的职业生涯,但是从一位看守员成长为先发队员,投球手还需要知道更多。
为了使自己成为的最优秀程序员,需要想法设法掌握新知识和新技能,并把它们投入到实践中。寻求挑战并克服它们,对自己所选择的语言的程序员专家所完成的工作进行研究。
记住,需求是发明的源泉,要想办法寻找无法用自己当前的技能圆满解决的问题。有时候,可以通过修改自己已经解决的问题以增加新的挑战。例如,我们可能已经编写了一个在数据集非常小的情况下能够顺利工作的程序,但是当允许数据增长到非常庞大的规模时会发生什么情况呢?或者,如果我们编写了一个在本地硬盘存储数据的程序,但是想远程存储数据时该什么办呢?如果我们需要一个程序的多个执行能够并发地进行远程访问和更新数据,应该怎么办呢?从一个工作程序开始并添加新的功能,就可以把注意力集中在这个新的编程方向上。
现代的编程语言与它们的核心代码库是分不开的。例如,当我们学习C++的时候,不可避免地会学到有关标准模板库的东西。当我们研究Java的时候,也会了解标准Java类。但是,除了与语言捆绑在一起的库之外,我们还需要研究第三方的代码库。有些是通用的应用程序框架,例如Microsoft的.NET框架,它可以在几种不同的高级语言中使用。在某些情况下,库是某个领域所特定的,像用于图形的OpenGL。还有一些库是第三方的专利软件包的组成部分。
和学习新语言一样,我们不应该在需要使用一个新库的主要项目中学习这个新库。反之,应该在一个重要性为零的测试项目中独立地学习这个库的主要组件,然后再把它们用于真正的项目。我们应该给自己布置难度不断增长的问题。记住,我们的目标并不是为了完成这些问题,而是通过这个过程进行学习。因此在自己的程序中成功地应用了这个新库之后,就不再需要对解决方案进行完善,甚至不需要将它们完成。然后,这些程序可以作为以后工作的参考。当我们因为不记得该怎么办而烦恼时,例如不知道怎样在OpenGL中把一个2D画面叠加到一个3D场景中,最好的办法莫过于打开一个自己以前所编写的专门用来演示这种技巧的旧程序,因为它是为此量身定做的。
另外,在学习一种新语言时,一旦掌握了一个库的基本内容,还应该阅读专家使用这个库所编写的代码。大多数大型的库具有官方文档并没有描述的特质或禁忌,只有具有长期经验的程序员才有可能发现它们。事实上,为了尽快地掌握某些库,需要使用其他程序员所提供的框架。重要的是,我们对别人代码的依赖不能超过必要的限度,应该尽快进入重新创建自己最初所看到的代码这个阶段。我们会惊奇地发现通过重建其他人的现成代码这个过程能够学到大量的东西。我们可能在原先代码中看到一个库函数的调用,并理解传递给这个函数的参数产生了一个特定的结果。但是,当我们把这段代码放在一边,并重新生成属于自己的效果时,就会迫使自己研究这个函数的文档,了解这个参数可以接受的所有特定的值,以及为了取得所需要的结果而必须把它们设置为什么。
作为一名长期的教育工作者,我觉得在本节结束时必须考虑上课这个问题。不管我们想要学习的是编程的哪个领域,总能找到可以为我们上课的人,无论是在传统的课堂上,还是在一些在线环境中。但是,上课只是学习的一种催化剂,而不是学习本身,尤其是在编程这个领域。不管编程老师多么学识渊博、多么富有激情,但是当实际学习新的编程技能时,我们所面对的是自己的计算机,而不是坐在课堂上面对老师。正如我在本书中反复强调的那样,必须把编程思路投入到实践中,这样才能保证自己真正学会它们。
这并不是说上课就没有价值,事实上它们常常具有非常巨大的价值。编程中的有些概念在本质上是难以理解的或者容易混淆,如果我们请教一位善于答疑解惑的教师,可以节省大量的时间和精力。另外,通过上课还可以对我们的学习进行评估。如果我们的教师尽心负责,可以从他对我们的代码的审阅中学到很多东西,可以极大地提高学习效率。最后,课业的成功完成可以给当前或未来的员工提供一些证明,表明我们已经理解了所学习的主题(就算运气不佳,所遇到的教师能力有限或责任心不足,起码我们有过这样的经历)。
要记住编程教育是我们的责任,就算我们只上了一堂课时。当一门课程在期末结束时,它可以提供评级的框架,但这个框架并不会限制我们的学习。要把自己的上课时间看成是尽可能多地学习相关主题的好机会,而并不仅局限于课程大纲所列的目标。
我非常喜欢回想自己的第一次编程经历。我编写了一个简短的、基于文本的弹球机模拟程序。虽然听上去好象不可思议,但我在那个时候还没有自己的计算机,谁能在1976年就拥有自己的计算机呢?但是,在我父亲的办公室里,有一台电传打字机终端,它在本质上是一台巨大的点阵式打印机,拥有像算盘一样的键盘,并通过声频调制解调器与本地大学的主机进行通信(拿起电话用手拨号,听到嘶嘶的电子声时,把电话听筒放在一个与终端相连的特殊支架上)。虽然我的弹球模拟程序非常原始和粗糙,但是当这个程序开始运行并且计算机按照自己的指令操作时,我便深深地着迷了。
在那天我的感觉,计算机就像一堆无限的乐高积木、建筑模型和林肯汽车模型,可以让我建造自己能够想象得到的任何东西。正是这种感觉激发了我对编程的热爱。当开发环境宣布顺利生成了程序并且我的指尖放在键盘上等待程序的执行时,自己总会感到非常兴奋,那是一种对成功的期待和对失败的预感。同时渴望看到自己努力的成果,不管是编写一个简单的测试项目还是对一个大型解决方案进行最后的优化,不管是创建一个漂亮的图形程序还是创建一个数据库应用程序的前端。
我希望你在编程中能够产生相似的感觉。即使你还在努力弄懂本书所讨论的一些技术要点,我仍希望你能够理解:只要编程能够让你感觉到兴奋,能够让你深陷其中,就没有你解决不了的问题。最重要的就是你愿意投入精力并沿着正确的方向前进,时间会接管剩余的一切。
你现在是不是能够像程序员一样思考了呢?如果你已经完成各章最后的习题,就应该已经能够像程序员一样思考,并对自己的问题解决能力充满信心。如果你还没有解决很多习题,我会向你提出一个建议,并且你也能够猜到,那就是完成更多的习题。如果你跳过了前面的一些章节,不要从本章的习题开始,回到你跳过的地方,从那个地方开始学习。如果你不想完成更多的习题 ,因为你不喜欢编程,那我也无能为力了。
一旦我们能够像程序员一样思考,就要为自己的技能感到自豪。如果有人叫你码农而不是程序员,奚落你说一只受过良好训练的鸟也能啄出代码,你可以反驳说自己并不仅仅是编写代码,而是使用代码来解决问题。当你坐在面试桌前接受未来雇主或客户的面试时,你要相信不管自己所面试的工作需要什么,你都能够满足其要求。
现在只剩下最后一组习题了。当然,它们比以前各章的习题难度更大,并且更为开放。
8.1 编写绞刑者作弊问题的一个完整实现程序,要比作者的解决方案更优秀。
8.2 对自己的绞刑者问题进行扩展,使用户可以选择成为玩家1。用户仍然要选择单词中的字母数以及允许猜错的次数,但是由程序进行猜测。
8.3 用另一种语言重新编写自己的绞刑者程序,这种语言应该是读者目前知之甚少或者完全不了解的。
8.4 把自己的绞刑者程序以图形的形式实现,显示绞刑架和绞刑者。我们应该以程序员而不是艺术家的目光来考虑图形,因此不用担心艺术质量。但是,我们必须创建一个真正的图形程序。不要用ASCII文本来绘制绞刑者,因为这太容易了。我们可以考虑用C++的2D图形库或者选择一种更加面向图形的不同平台,例如Flash。使用图形绞刑者可能要求对猜错次数进行限制,但应该有一种方法提供至少一个范围内的选择。
8.5 自行设计:采用在绞刑者问题中所学习的技巧解决另一个完全不同的、涉及单词列表的问题,例如使用单词的其他游戏,像拼字游戏、拼写检查程序或自己想到的其他程序。
8.6 自行设计:寻找一个规模或难度肯定是自己当前的技能所无法解决的C++编程问题,想办法解决它。
8.7 自行设计:寻找自己感兴趣但还没有在程序中使用过的一个库或API。对这个库或API进行研究,然后在一个实用的程序中使用它。如果对通用的编程感兴趣,可以考虑Microsoft .NET库或者一种开放源代码的数据库类库。如果喜欢低层的图形,可以考虑OpenGL或DirectX。如果喜欢编写游戏,可以考虑像Ogre这样的开放源代码的游戏引擎。思考自己所编写的程序的类型,找到一个适合的库,并对它进行研究。
8.8 自行设计:为一个新平台(对自己而言是不熟悉的)编写一个实用的程序,例如,移动编程或网络编程。