作者：赵军 等
出版社：机械工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
计算思维与算法入门试读：
前言
程序设计课程越来越普及，让每一个学生拥有程序设计的能力是各大专院校在信息科学与技术教学方面的重点之一。当然，学习程序设计的目标不是把每个学习者都培养成专业的程序设计人员，而是帮助每一个人建立起系统化的逻辑思维模式和习惯。以往程序设计的实践目标非常重视“计算”能力，随着近年来因特网的高速发展，计算能力早已不是唯一的目标，程序设计课程着重于培养学习者的“计算思维”，也就是分析与分解问题的能力。
编写程序代码不过是整个程序设计过程中的一个阶段，在编写程序之前，有需求分析与系统设计两大阶段。计算思维是培养系统化逻辑思维的基础，有了这一基础在面对问题时才能具有系统分析与问题分解的能力，从中探索出可能的解决办法，并找出最有效的算法。
算法一直是计算机科学领域非常重要的基础课程，从程序设计语言实践的角度来看，算法是有志于从事信息技术方面工作的专业人员必须重视的一门基础理论课程。无论我们采用哪种程序设计语言来编写程序，所设计的程序能否快速而高效地完成预定的任务，其中的关键因素都是算法。对于将来不从事信息技术方面工作的人而言，学习算法同样可以培养自己系统化逻辑思维的习惯，这种思维习惯可以运用在各行各业中，让学习者终身受益。
本书精选计算思维与算法课程中核心的内容：第1章介绍程序设计与计算思维两者间的关系；第2章介绍常用数据结构与算法，包括数组、矩阵、链表、堆栈、队列、树、图及哈希表等数据结构，以及分治法、递归法、贪心法、动态规划法、迭代法、枚举法、回溯法等常见的算法；第3~9章针对分治法、贪心法、动态规划法、安全性算法、树结构的算法、改变程序功力的经典算法、游戏设计中的算法，逐一介绍计算机科学中较为知名的一些算法。
为了帮助更多人轻松地了解算法的精髓，本书采用丰富的图例阐述这些算法的基本概念，并结合范例诠释这些算法，期望读者学习之后可以将各种计算思维与算法真正运用于程序设计实践中。
为了检验读者的学习成果，每一章的最后都安排了与本章重点内容相关的习题，让读者有更多操作演练的机会。
最后，希望读者通过学习本书可以培养逻辑思维能力，进而在自己的工作和生活中获益。
本书主要由赵军编著，同时参与编写工作的还有王国春、施研然、王然、孙学南等。如果读者在学习过程中遇到无法解决的问题，或者对本书有意见或建议，可以通过邮箱booksaga@126.com与编者联系。赵军2019年1月第1章程序设计与计算思维
计算机堪称20世纪以来人类最伟大的发明之一，对于人类的影响更甚于工业革命所带来的冲击。计算机是一种具备数据处理与计算功能的电子设备。自从人类发明并开始大量应用计算机之后，无论是政府、企业还是个人，对于数据和信息处理的效率都有了极大的提升，如图1-1所示。图1-1 工厂生产线与大楼自动化安保管理
对于一个有志投身信息技术领域的人员来说，程序设计就是一门和计算机硬件与软件息息相关的学科，是计算机诞生以来一直蓬勃发展的一门新兴科学。之所以说它是新兴科学，是因为计算机的程序设计还在不断地发展和演变，只不过现在的方向是大数据和人工智能等领域。为了发挥计算机强大的运算能力，我们必须掌握程序设计的基本方法和了解它的基本概念。所谓程序，是由符合程序设计语言（Programming Language）语法规则的程序语句、程序代码或程序指令所组成的，而程序设计的目的是通过程序的编写与执行来满足计算机用户的需求。提示
程序设计语言是一种人类用来和计算机沟通的语言，是由文字与记号所形成的程序语句、代码或指令的集合。程序设计语言主要的功能是将用户的需求使用程序指令表达出来，让计算机按照程序指令替我们完成诸多工作和任务，每种程序设计语言都有各自的文法规则，即语法（syntax），也就是它的使用规则。程序设计语言的语法一直朝着易于使用、易于调试、易于维护以及功能更强的目标持续发展和演变。
对于我们学习程序设计而言，目标无疑就是让我们设计的程序更有效率、可读性更高。我们知道，与计算机作为硬件工具一样，程序设计语言也只是一种应用工具，因此没有最好的程序设计语言，只有是否适合的程序设计语言，各种程序设计语言都是实现目标的方法。例如，著名的积木式程序设计语言Scratch，其集成开发环境的界面如图1-2所示。图1-2 积木式程序设计语言是指设计者能以拖曳积木的方式来组合出程序图1-3 云计算加速了新一代人才必须具备程序设计能力时代的来临
随着信息技术与网络科技的发展，当前进入物联网（Internet of Things，IoT）、大数据、人工智能的云计算（Cloud Computing）时代。一个国家或地区的程序设计能力已经被看成是国力或者地区竞争力的象征。程序设计不再只是信息类学科的专业，而是新一代人才必备的基本能力，各个先进的国家或者地区纷纷将程序设计（或简称编程）列入学生的必修课程，发达地区的城市中小学都开设了编程的信息课程。通过学习程序设计的过程让学生获得解决问题的能力，只有将“创意”通过“设计过程”与计算机相结合，才能顺应这个快速发展和演变的物联网、大数据、人工智能的云计算时代，如图1-3所示。提示“云”泛指“网络”，这个名字的源头是工程师通常把网络架构图中不同的网络用“云朵”的形状来表示。云计算就是将网络连接的各种计算设备的运算能力提供出来作为一种服务，只要用户可以通过网络登录远程服务器进行操作，就可以使用这种计算资源。“物联网”是近年来信息产业界的一个非常热门的议题，它是指将各种具有传感器或感测设备的物品（例如RFID、环境传感器、全球定位系统（GPS）等）与因特网结合起来，并通过网络技术让各种实体对象自动彼此沟通和交换信息，也就是通过巨大的网络把所有东西都连接在一起。1.1 认识计算思维
学习程序设计的目标绝对不是要将每个学习者都培养成专业的程序设计人员，而是要帮助每个人建立系统化的逻辑思维模式。以往程序设计的实践目标非常重视“计算”能力，近年来随着因特网的高速发展，计算能力的重要性早已不是唯一的目标，因而程序设计课程的目的特别着重于培养学生的“计算思维”（Computational Thinking，CT，或称为“运算思维”），也就是分析与分解问题的能力。图1-4 要学好计算思维，通过程序设计来学是最快的途径
编写程序代码不过是程序设计整个过程中的一个阶段而已，在编写程序之前，还有需求分析与系统设计两大阶段。计算思维是用来培养系统化逻辑概念的基础，进而学习在面对问题时具有系统的分析与分解问题的能力，从中探索出可能的解决办法，并找出最有效的算法。我们可以这样说：“学习程序设计不等于学习计算思维，但要学好计算思维，通过程序设计来学绝对是最快的途径”，如图1-4所示。
计算思维是一种使用计算机的逻辑来解决问题的思维，前提是掌握程序设计的基本方法和了解它的基本概念，是一种能够将计算“抽象化”再“具体化”的能力，也是新一代人才都应该具备的素养。计算思维与计算机的应用和发展息息相关，程序设计相关知识和技能的学习与训练过程其实就是一种培养计算思维的过程。当前许多欧美国家从幼儿园开始就培养孩子的计算思维，让孩子从小就养成计算思维的习惯。培养计算思维的习惯可以从日常生活开始，并不限定于任何场所或工具，日常生活中任何牵涉到“解决问题”的议题，都可以应用计算思维来解决，通过边学边体会，逐渐建立起计算思维的逻辑能力。
假如你今天和朋友约在一个没有去过的知名旅游景点碰面，在出门前，你会先上网规划路线，看看哪些路线适合你的行程，以及选乘哪一种交通工具最好，接下来就可以按照计划出发。简单来说，这种计划与考虑过程就是计算思维，按照计划逐步执行就是一种算法（Algorithm），就如同我们把一件看似复杂的事情用容易理解的方式来解决，这样就具备了将问题程序化的能力。图1-5所示的范例是小华早上上学并买早餐的简单计算思维。图1-5 学生买早餐的过程也是一种计算思维的应用
2006年，美国卡内基·梅隆大学Jeannette M.Wing教授首次提出了“计算思维”的概念，她提出计算思维是现代人的一种基本技能，所有人都应该积极学习。随后谷歌公司为教育者开发了一套计算思维课程，这套课程提到培养计算思维的4部分，分别是分解（Decomposition）、模式识别（Pattern Recognition）、模式概括与抽象（Pattern Generalization and Abstraction）以及算法（Algorithm）。虽然这并不是建立计算思维唯一的方法，不过通过这4部分我们可以更有效地进行思维能力的训练，不断使用计算方法与工具解决问题，进而逐渐养成我们的计算思维习惯。
在训练计算思维的过程中，其实就培养了学习者从不同角度以及现有资源解决问题的能力。正确地运用培养计算思维的这4部分，同时运用现有的知识或工具，找出解决困难问题的方法。学习程序设计就是对这4部分进行系统的学习与组合，并使用计算机来协助解决问题，如图1-6所示。图1-6 计算思维的4部分示意图1.1.1 分解
许多人在编写程序或解决问题时，对于问题的分解不知道从何处着手，将问题想得太庞大，如果一个问题不进行有效分解，就会很难处理。将一个复杂的问题分割成许多小问题，把这些小问题各个击破，小问题全部解决之后，原本的大问题也就解决了。
假如我们的一台计算机出现部件故障了，将整台计算机逐步分解成较小的部分，对每个部分内的各个硬件部件进行检查，就容易找出有问题的部件。再假如一位警察在思考如何破案时，也需要将复杂的问题细分成许多小问题，如图1-7所示。图1-7 将复杂的问题分解为小问题
下面举一个例子来说明。假如我们要分解教小孩刷牙的问题，可以分解与细分成以下情况（见图1-8）：
·用哪种牙刷较好
·要刷多久
·如何刷
·哪种牙膏适合
·准备漱口杯图1-8 教小孩刷牙的问题
在一些综艺节目中会出现所谓的终极密码游戏，主持人随机从1~100中取出一个彩球（见图1-9），让嘉宾猜彩球的数字，主持人只能针对嘉宾猜的数字回答“高了”或“低了”，这也是一种问题分解的具体应用。想想看，如何才能快速猜到这个数字呢？图1-9 抽彩球游戏也是一种计算思维的训练
假如取出的彩球数字是“38”，那么我们可以将1~100的数字数列（sequence）先取中间的数字50来比较，38在1~50之间，所以只剩下数列前半段1~50，运用同样的方式取中间的数字再进行比较，数字数列又排除一半，只剩25~50，一直循环这个过程就能找到数字38。这个过程可以参考图1-10。图1-10 猜测彩球数字的一种二分查找法
事实上，这样的解题分析过程就是训练和培养程序设计的计算思维过程。在上述分析过程中，虽然并没有提到任何艰深的程序设计语言，但是已经带入了程序设计的两个重要概念：“循环（loop）”和“二分查找法（binary search）”。提示
循环会重复执行一个程序区块中的程序语句，直到满足特定的结束条件为止。例如，想要让计算机算出1+2+3+4+…+100的值，在程序语句中并不需要我们大费周章地从1累加到100，这时只需要使用循环结构就可以轻松实现这种累加。
二分查找法是将数据序列分割成两等份，再用要查找的键值与中间值进行比较，如果键值小于中间值，就可以确定要查找的数据在数据序列的前半段，否则就在后半段。1.1.2 模式识别
在将一个复杂的问题分解之后，我们常常可以发现小问题中有共同的属性以及相似之处，在计算思维中，这些属性被称为“模式”（Pattern）。模式识别是指在一组数据中找出特征（Feature）或规则（Rule），用于对数据进行识别与分类，以作为决策判断的依据。在解决问题的过程中，找到模式是非常重要的，模式可以让问题的解决更简化。当问题具有相同的特征时，它们能够被更简单地解决，因为存在共同模式时，我们可以用相同的方法解决此类问题。
例如，当前常见的生物识别技术就是利用人体的形态、构造等生理特征（Physiological Characteristics）以及行为特征（Behavior Characteristics）作为依据，通过光学、声学、生物传感等高科技设备的密切结合对个人进行身份识别（Identification或Recognition）与身份验证（Verification）的技术。又例如，指纹识别（Fingerprint Recognition）系统以机器读取指纹样本，将样本存入数据库中，然后用提取的指纹特征与数据库中的指纹样本进行对比与验证（见图1-11），而脸部识别技术则是通过摄像头提取人脸部的特征（包括五官特征），再经过算法确认，就可以从复杂背景中判断出特定人物的脸孔特征。图1-11 指纹识别系统的应用已经相当普遍
当我们发现越来越多的模式时，解决问题就会变得更加容易和迅速。在知道怎么描述一只狗之后，我们可以按照这种模式轻松地描述其他狗，例如狗都有眼睛、尾巴与4只脚，不一样的地方是每只狗都或多或少地有其独特之处（见图1-12），识别出这种模式之后，便可用这种解决办法来应对不同的问题。图1-12 狗都有眼睛、尾巴与4只脚
因为我们知道所有的狗都有这类属性，当想要画狗的时候，便可将这些共同的属性加入，这样就可以很快地画出很多只狗。在平时，我们也能进行模式识别的思维训练，可以通过动手画图、识别图形、分辨颜色或对物体分类来进行训练。1.1.3 模式概括与抽象
模式概括与抽象在于过滤以及忽略掉不必要的特征，让我们可以集中在重要的特征上，这样有助于将问题抽象化。通常这个过程开始会收集许多数据和资料，通过模式概括与抽象把无助于解决问题的特性和模式去掉，留下相关的以及重要的属性，直到我们确定一个通用的问题以及建立解决这个问题的规则。“抽象”没有固定的模式，它会随着需要或实际情况而有所不同。例如，把一辆汽车抽象化，每个人都有各自的分解方式，像车行的业务员与修车技师对汽车抽象化的结果可能就会有差异，如图1-13所示。图1-13 车行业务员和修车技师对汽车抽象化的结果会有差异
车行业务员：轮子、引擎、方向盘、刹车、底盘。
修车技师：引擎系统、底盘系统、传动系统、刹车系统、悬吊系统。
如何正确而快速地将现实世界的事物抽象化是一门学问，而计算思维着重于分析、分解与概括（或归纳）的能力，是练习抽象化非常有效的方法。在日常生活中也处处可见抽象化，例如我们将复杂、有地形背景的北京地铁运行图简化为如图1-14所示的纯线路图模式，以简单明了的方式标示出各个不同地铁线路的走向及各个站点。图1-14 北京地铁线路图
计算思维可视为是运用信息科技有效解决问题的心智历程，通过模式概括与抽象的过程整理出有用的数据、资源以及限制条件，整个思维过程可以使用“思维导图（Mind Map）”来归纳和整理。思维导图是由英国的Tony Buzan于20世纪70年代提出的一种辅助思考的工具，又称脑力激荡图、思维图，它是一种使用图像来帮助思考与表达思维的工具，可以刺激思维并帮助整合思想与信息。借助这种方式，我们可以更轻松地以图形方式来表达自己的想法。
思维导图的绘制其实非常简单，中心点通常表示一个核心主题，用一张纸把记忆记录下来，再把绘图者的思考、分析、规划、概括和归纳后的信息以笔记方式呈现，用关键词向外扩张延伸出分支来表达内容。通过主题的脑力激荡，把想到的字词、概念全部写下来，使用不同尺寸的文字、线条与图形来区别数据间的从属关系与重要程度。除了材料、内容、色彩等多方面的构思以外，同时也训练绘图者在思考过程的“流畅性”与“变通性”，刚开始的思维可能很发散，我们不用想太多，通通写下来就好了，等收集到一定程度，再慢慢筛选掉不适合的部分。假如我们要规划一个减轻体重的计划，首先必须制定一个核心目标，聚焦在“减重”这个主题上，再按序想出解决问题的方法来归纳整理。如图1-15所示是一个思维导图的范例。图1-15 思维导图的范例1.1.4 算法
算法是计算思维4个基石的最后一个，不但是人类使用计算机解决问题的技巧之一，也是程序设计中的精髓。算法常出现在规划和设计程序的第一步，因为算法本身就是一种计划，每一条指令与每一个步骤都是经过规划的，在这个规划中包含解决问题的每一个步骤和每一条指令。
在日常生活中有许多工作可以使用算法来描述，例如员工的工作报告、宠物的饲养过程、厨师准备美食的食谱、学生的课程表等。如今我们几乎每天都要使用的各种搜索引擎都必须借助不断更新的算法来运行，如图1-16所示。
特别是在算法与大数据的结合下，这门学科演化出“千奇百怪”的应用，例如当我们拨打某个银行信用卡客户服务中心的电话时，很可能会先经过后台算法的过滤，帮我们找出一名最“合我们胃口”的客服人员来与我们交谈。在因特网时代，通过大数据分析，网店可以进一步了解产品购买和需求产品的人群是哪类人，甚至一些知名IT企业在面试过程中也会测验候选者对于算法的了解程度，如图1-17所示。图1-16 搜索引擎的背后是不断优化的搜索算法图1-17 一些知名IT企业面试时也会测验候选者对算法的了解程度提示
大数据（Big Data，又称为海量数据）由IBM公司于2010年提出，是指在一定时效（Velocity）内进行大量（Volume）、多样性（Variety）、低价值密度（Value）、真实性（Veracity）数据的获得、分析、处理、保存等操作。数据的来源有非常多的途径，大数据的格式也越来越复杂，大数据解决了商业智能无法处理的非结构化与半结构化数据。
在韦氏辞典中，算法定义为：“在有限步骤内解决数学问题的程序。”如果运用在计算机领域中，我们也可以把算法定义成：“为了解决某项工作或某个问题，所需要的有限数量的机械性或重复性指令与计算步骤。”1.2 算法的条件
在计算机中，算法更是不可或缺的一环。在认识了算法的定义之后，我们再来看看算法所必须符合的5个条件（可参考图1-18和表1-1）。图1-18 算法必须符合的5个条件表1-1 算法必须符合的5个条件
我们认识了算法的定义与条件后，接着要来思考：用什么方法表达算法最为适当呢？其实算法的主要目的在于让人们了解所执行的工作流程与步骤，只要能清楚地体现算法的5个条件即可。
常用的算法一般可以用中文、英文、数字等文字来描述，也就是使用文字或语言语句来说明算法的具体步骤，有些算法则是使用可读性高的高级程序设计语言（如Python、C、C++、Java等）或者伪语言（Pseudo-Language）来描述或说明的。例如，以下算法就是用Python语言来描述函数Pow（）的执行过程：计算所传入的两个数x、yy的x值。def Pow(x,y): p=1 for i in range(1,y+1): p *=x return pprint(Pow(4,3))
公约数是指可以整除两个整数的整数，通过辗转相除法可以求两个整数的最大公约数，就是通过算法来求解的。下面我们使用while循环设计一个C语言程序，求所输入的两个整数的最大公约数（g.c.d）。辗转相除法的算法如下：if (Num1 < Num2){ TmpNum=Num1; Num1=Num2; Num2=TmpNum; /* 找出两个整数中的较大值 */ }while (Num2 != 0) /* 辗转相除法，直到除数为0就终止循环 */{ TmpNum=Num1 % Num2; /* 求两个整数的余数 */ Num1=Num2; Num2=TmpNum; /* 将本轮相除求得的余数作为下一轮的除数 */} printf("最大公约数(g.c.d)=%d\n",Num1); 提示
伪语言接近于高级程序设计语言，是一种不能直接放进计算机中执行的语言。一般都需要通过一种特定的预处理器（Preprocessor）或者通过人工编写转换成真正的计算机语言才能够加载到计算机中执行，目前较常使用的伪语言有SPARKS、PASCAL-LIKE等。
流程图（Flow Diagram）是一种相当通用的算法表示法，就是使用某些特定图形符号来表示算法的执行过程。为了让流程图具有更好的可读性和一致性，目前较为通用的是ANSI（美国国家标准协会）制定的统一图形符号。表1-2列出了流程图中一些常见的图形符号并附有简单的说明。表1-2 流程图中常见的图形符号
假如我们要设计一个程序，让用户输入一个整数，而这个程序可以帮助用户判断输入的整数是奇数还是偶数，那么这个程序的流程图大致如图1-19所示。
为了让他人容易阅读，绘制流程图应注意以下几点：（1）采用标准通用符号，符号内的文字尽量简明扼要。（2）绘制方向应自上而下，从左到右。（3）连接线的箭头方向要清楚，线条避免太长或交叉。图1-19 用流程图描述算法的例子——判断奇数和偶数提示
算法和过程是有区别的，过程不一定要满足算法有限性的要求，例如操作系统或计算机上运行的过程，除非宕机，否则永远在等待循环中（waiting loop），这就违反了算法五大条件中的“有限性”。
再来看一个算法的例子，我们知道计算机内部是以二进制数的方式来处理数据和信息的，而人类则是以十进制数的方式来处理日常运算的。在计算机中，有些数据也会采用八进制数或十六进制数来表示。十进制数转换成非十进制数要分为整数部分的转换和小数部分的转换，下面通过范例来说明相关的转换算法。（1）十进制数转换成二进制数（63）=（111111）（十进制整数转换成二进制整数，参考图1021-20）图1-20 十进制整数转成二进制整数（0.625）=（0.101）（十进制小数转换成二进制小数，参考102图1-21）图1-21 十进制小数转换成二进制小数（12.75）＝（12）＋（0.75），参101010（十进制数转换成二进制数）考图1-22。图1-22 十进制数转换成二进制数
其中，（12）＝（1100），（0.75）＝（0.11）102102
所以（12.75）＝（12）＋（0.75）101010
＝（1100）＋（0.11）22
＝（1100.11）2（2）十进制数转换成八进制数（63）＝（77）（参考图1-23）108图1-23 十进制整数转换成八进制整数（0.75）＝（0.6）（参考图1-24）108图1-24 十进制小数转换成八进制小数（3）十进制转换成十六进制（63）＝（3F）（参考图1-25）1016图1-25 十进制整数转换成十六进制整数（0.62890625）＝（0.A1）（参考图1-26）1016图1-26 十进制小数转换成十六进制小数（120.5）＝（120）＋（0.5）101010
其中，（120）＝（78），（0.5）＝（0.8），参考图1-27。10161016图1-27 十进制数转换成十六进制数
试读结束[说明：试读内容隐藏了图片]