本书针对零基础的初学者,以算法为核心,以编程为手段,最终的目的是培养读者的计算思维。
本书涉及大学计算机课程中程序设计、数据结构和计算机原理等多个领域的知识,从程序、编程和算法是什么入手;然后重点介绍了控制流程和数据结构,并针对数据结构的限制和实现剖析了现代电子计算机的基础:二进制和冯·诺依曼结构;最后重点介绍了6大经典算法的原理、过程和编程实现,以及其背后的算法策略。
为了使零基础的读者能够上手编程,本书从操作角度阐述了编程工具的使用和程序编写、运行、调试的过程。
微软资深算法工程师为初学者定制的基础算法课。攻克数据结构及六大经典算法,由编程学算法,以算法促编程,锻炼思维“肌肉”,让大脑灵活地转起来
前言
笔者第一次接触编程是20 世纪80 年代,当时参加了宋庆龄儿童活动中心举办的一项编程体验活动,就是照着前面黑板上写的代码在现场的机器上敲一遍,然后运行。当时到底用的是什么语言已经记不清了,但是还记得花费了好大力气,摸索着敲了一遍完全不清楚其含义的字符串,然后按照说明运行,最终毫无动静。虽然请教了巡场的工作人员,但他们也不知道是什么问题,到离场时都没能让程序“跑”起来——难道,编程就是要用计算机“写”一堆“ 密码”吗?如果这堆密码“跑”起来了,又会是怎样的效果呢?
初次不成功的体验后,直到20 世纪90 年代中期,因为学校开设了计算机课,笔者才再度接触编程。老师在课堂上讲了一点Basic 语言知识,编写的是a+b=c 之类的程序,然后运行得出结果。笔者由此知道了编程语言,期末考试成绩也不错,但对于编程是什么,计算机能干什么,还是不明所以。国外的影视剧中用计算机能做生意,能管理企业,但我们编写的程序只能做算术题,这是为什么呢?
上大学后,除了编程语言,笔者还学习了“数据结构”、“计算机原理”、“计算机体系结构”、“编译原理”、“操作系统”和“软件工程”等专业课程,这才逐渐明白了“编程”这一表面现象背后的体质:算法是怎么回事,计算机是如何运行的,为什么我们输入的静态字符能够变成动态的程序,通过其“跑动”来满足人们的需求……并由此了解到编程其实就是实现算法的过程。
算法,才是编程的核心。
后来进入职场,成了程序员,十几年一路走来,始终在一线研发岗位,开发过不同类型的实践项目,在开发过程中不断学习、揣摩,才逐渐领悟到抽象算法和现实问题之间的关系:软件开发就是通过各种算法实现具体的业务逻辑,把繁杂的过程抽象化、可计算化的过程。
而软件开发工作背后的思维逻辑(将一个个具体的问题及其解决方案表达成计算机可以处理的形式,并设计计算的方式,将客观世界解释为一个复杂的信息处理过程)则被称为计算思维,其具体表现如下:
* 把一个大问题分解为一个个子问题,然后进一步分解为一个个子子问题……直到无须分解。
* 分别执行一个个最小规模的问题。
* 按照问题划分的结构将各个小问题的结果组成整个问题的结果。
也就是自上而下进行结构化的设计,遇到问题“分而治之,各个击破”。这种解决问题
的方法并不是计算机专业独有的,完全可以脱离编程而存在,并且是各行各业都需要的:
* 准备一桌宴席应该怎么做?先确定总共有几道菜;然后购买原料,逐一烹调,装盘上桌——这是分而治之的过程。
* 创作一幅漫画应该怎么做?先确定故事背景、人物设置;然后构思主题、情节,绘制分镜头脚本;最后将每个分镜头的草图通过精描、上色等步骤绘制成成品图——这也是分而治之的过程。
* 举办一场学术会议应该怎么做?先确定主题、主讲人、参会群体、场地;然后分头准备(如邀请主讲人、确定演讲题目、制定日程)、租用/ 借用场地、协调交通、布置会场;最后招募参会者,注册、缴费,安排各项活动——这也是分而治之的过程。
* 开办一家餐馆应该怎么做?
* 拍摄一部电影应该怎么做?
* 研发一款电动汽车应该怎么做?
* 建设一个高新科技开发区应该怎么做?
* ……
计算思维不仅提出了一套解决问题的方法论,而且非常强调实践性——解决方案不是理论正确就可以,而是要在实际中可行才可以。
这个特点是由计算思维的诞生背景所决定的——当计算机科学家处理问题时,除了需要知道如何将一个问题抽象为计算机能够理解的可计算模型,还要能够将计算收敛到有限空间中得到结果。如果算法的时空复杂度过大,以当前的算力在有效求解的时间内无法得出结果,那么再完美的理论算法也无法在现实中奏效。
世界上的问题有大有小,所需要的资源有多有少,但抽象到最高层面的方法论可以是一致的。计算思维是各行各业都需要的。
掌握计算思维单靠理论学习是远远不够的,必须经由大量的实践。编程实践就是习得计算思维的最佳方式。
既然要进行编程实践,学习编程语言和工具的使用方法当然是必不可少的。但语言、工具都只是皮毛,随着计算机技术的发展,编程语言日益增加,各种工具日新月异,“保质期”越来越短。而经由现实问题提炼出来的经典算法却经得起时间的考验。
从计算机被发明出来到现在,一些逻辑层面的基础问题在大多数应用领域都会用到。
许多应用层繁多的花样,最终对应的都是共同的基础问题。计算机领域的科研人员、开发者,在几十年的工作中,针对一些历史悠久、应用广泛、高频出现的问题,研发出了对应的精致、高效的算法,我们将这些算法称为经典算法。
计算机的经典算法也有多种,但其中重要且常用的相对有限,主要有:
* 针对序列数据的查找算法和排序算法是基础。
* 针对树和图数据结构的各种算法:首先是遍历算法(深度优先和广度优先);然后是各种类型的树结构,以及以计算图中不同顶点间最短路径为目的的各种算法。
* 若干用于解决数学问题(求最大公约数等)的计算机算法。
通过对经典算法的研习和实践,掌握“用数值表达现实事物,用运算描述任务目标,
再通过算法处理数据找到到达目标的最优路径”的方法论。如此,既是一种有效的思考力训练,又是形成计算思维的过程。由此形成的思维能力是内力,而同步掌握的编程技能则属外功。
从长远来看,学习编程可以提升人们的计算思维水平;就近期来看,掌握一门正在日益变得通用的技能非常重要。
本书针对没有任何程序设计基础的读者,同步讲解两方面内容:使用Python 语言编写程序;基础经典算法。由编程学算法,以算法促编程。同时,为了帮助读者理解算法,本书还介绍了计算机的基础运行原理。
在大学计算机专业课程中,本书所介绍的内容往往被拆分在如下几门课程中:
* 程序设计语言(如Python)
* 数据结构
* 计算机组成原理和体系结构
本书将几个领域的知识融合在一起,从日常事物开始,介绍软件、程序、算法和编程分别是什么;然后重点介绍编程的两大要素,即控制流程和数据结构,并详细介绍了几种常见的数据结构(如数组、链表、树和图),在此过程中,由数据结构的限制和实现引出现代电子计算机的基础——二进制和冯?诺依曼结构;最后进入算法阶段,从最简单的顺序查找开始,一边介绍算法,一边介绍它们的编程实现,详细介绍的经典算法包括顺序查找、二分查找、简单排序(包括选择排序、起泡排序、插入排序)和快速排序。
介绍具体算法无法脱离背后的原则,所以本书还介绍了作为快速排序思维基础的分治策略和引自数学的递归等算法策略。为了使零基础的读者能够上手编程,本书从操作角度阐述了编程工具的使用和程序编写、运行、调试的过程。
如此安排本书的内容主要源于以下两点:
* 使读者在接触编程的最初阶段就能够明确编程的核心是算法,从而将掌握算法策略、原理和过程作为学习重点,而不必将过多精力投入编程语言的语法或工具的操作等 “易过期”的细节上。
* 在学习理论算法的同时能够时刻联系实际,使读者不仅可以理解算法本身在不同应用场景中的优点和缺点,还可以运用算法解决现实中的问题,并培养读者的计算思维。
为了写作本书,笔者专门邀请了两位零基础的同学作为学生,按照上述思路,为她们上了为期一年的“算法编程同步学”课程。本书就是根据这门课程的教案整理而成的。在此特别感谢康牧心和任臻同学。