第1章

计算思维与C语言的初体验

计算机堪称20世纪以来人类最伟大的发明之一，对人类的影响非常深远。计算机是一种具备数据处理与计算能力的电子化设备。1946年，美国宾夕法尼亚大学教授埃克脱（Eckert，John Presper，Jr.）与莫奇利（John W. Mauchly）合作发明了人类第一台真空电子管计算机——ENIAC。接着冯·诺依曼（John vonNeumann）教授首先提出了存储程序与二进制编码的概念，认为数据与程序可以存储在计算机存储器内。这开启了程序语言与程序设计蓬勃发展的序幕。

对有志于从事信息专业工作的人员来说，程序设计是一门与计算机硬件和软件息息相关的学科，称得上是近十几年来蓬勃兴起的一门科学。

程序设计的本质是数学，而且是简单的数学应用。过去对于程序设计的实践目标，我们会非常看重“计算”能力。而随着信息与网络科技的高速发展，现在程序设计课程的目的更多的是对学生“计算思维”（Computational Thinking, CT）的训练。

1.1

认识计算思维

日常生活中的大小事，无疑都是在解决问题，只要涉及“解决问题”的事情，都可以套用计算思维来解决。读书与学习就是为了培养人们解决生活中遇到的问题的能力。计算思维是一种利用计算机逻辑来解决问题的思维，是一种能够将问题“抽象化”与“具体化”的能力，也是现代人应该具备的素养。

我们可以这样形容：“学程序设计不等于学计算思维，而程序设计的过程就是计算思维的一种表现；并且要掌握计算思维，程序设计是一个非常好的途径。”程序语言本质上只是一种工具，从来都不是掌握的重点，没有最好的程序语言，只有最适合的程序语言。学习程序语言的目标绝对不是要将每个学习者都训练成专业的程序设计师，而是要培养学习者的计算思维。

2006年美国卡内基梅隆大学的周以真（Jeannette M. Wing）教授首度提出了“计算思维”的概念，她提到计算思维是现代人的一种基本技能，所有人都应该积极学习。随后谷歌公司为教育者开发了一套计算思维课程。这套课程包括培养计算思维的4个方面——分解、模式识别、归纳与抽象化、算法。虽然这并不是培养计算思维的唯一方法，但是通过这4个方面，我们能更有效率地利用计算方法与工具来解决问题，进而建立计算思维。

1.1.1

分解

许多人在编写程序或解决问题时，往往会因为不知道从何分解问题而将问题想得太复杂。如果一个问题不进行分解，一般会较难解决。分解相当于将一个复杂的问题分成许多个小问题，先将这些小问题逐个击破；小问题全部解决之后，原本的复杂问题也就解决了。

我们以一个实际例子进行说明，假设有8幅很难画的图，我们可以将其分成两组各4幅画来完成；如果还是觉得太复杂，可以将其分成4组，每组各两幅画来完成，如图1.1所示。利用相同模式反复分解问题，这就是分治算法的核心精神。

图1.1

Tips

分治算法是一种很重要的算法，我们可以应用分治算法来逐一分解并解决复杂的问题。它的核心精神是将一个难以直接解决的大问题依照不同的概念分解成两个或更多个子问题，再逐个“击破”，分而治之。其实任何一个可以用程序求解的问题所需的计算时间都与其规模有关，问题的规模越小，越容易直接求解。

例如一台计算机出现故障了，如果将整台计算机逐步分解成较小的部分，对每个部分的各种元件进行检查，就容易找出问题所在；又如一位警察在思考如何破案时，也习惯将复杂的问题分成许多小问题。程序员遇到问题时，通常会考虑所有的可能性，把问题逐步分解后进行解决，久而久之，这样的逻辑就变成了他的思考模式。

1.1.2

模式识别

将一个复杂的问题分解之后，我们常常能发现小问题之间的共有属性及相似之处，在计算思维中，这些属性称为“模式”。模式识别是指在一堆数据中找出特征或规则，并将其作为对数据进行辨识与分类决策的判断依据。在解决问题的过程中，找到模式非常重要，因为模式可以简化问题。当问题存在共通模式时，它们就很容易被解决。因为当共通模式存在时，我们可以用相同的方法去解决这类问题。