第1章 计算思维与计算机
劳动创造了工具，而工具又拓展了人类探索自然深度和广度的能力。计算机是人类对计算工具不懈努力追求的*好回报，计算思维则是人类依靠计算机强大的计算能力解决问题而自然产生的思维模式。因此，人类的计算需求孕育出计算工具，计算工具的发展深刻影响着人类认识和改变世界的思维能力。
下面我们将从计算环境的演变开始认识计算，并跟随计算工具的发展史，探索计算思维的形成与发展历程。
1.1 计算与计算工具
在人们的生活中，计算无处不在。古有“运筹帷幄之中，决胜千里之外”，今有云计算、海计算、智能计算、互联网等把人、物与计算工具联系起来。计算这个原本专门的数学概念已经泛化到人类的整个知识和生活领域，成为人们认识事物、研究问题和思考生活的一种新视角、新观念和新方法。
1.1.1 计算的概念
当今学科种类繁多，涉及面广，每个学科都需要进行大量的计算。天文学家需要计算分析星位移动；生物学家需要计算发现基因组的奥秘；经济学家需要从大量的数据中寻找消费行为和商业机会等。计算无处不有、无处不在，但计算究竟是什么？
1．计算的定义
计算，一个我们并不陌生的概念，如加、减、乘、除、正弦、微分、积分等数值计算以及符号推导等，其实计算除了包括具体的数值问题求解，还包括针对具体问题进行的定理、公理的推导和证明等。随着信息时代的到来，以计算机为中心的计算概念正在拓广，并被不断赋予新的含义，成为自然、科学和社会三大系统各个领域的基本处理过程。
所谓计算，抽象地讲就是将输入A依据一定的法则变换为输出B的过程，如图1.1所示。
图1.1 计算的定义
下面举三个简单的例子。
(1)令A是一个四则运算表达式，B为表达式的值，从A到B的过程就是一个表达式的计算过程。
(2)令A为一组公理和推导规则，B为一个定理，从A到B的一系列变换就是定理的证明过程。
(3)令A为“中国”，B为“China”，从A到B的过程就是将中文翻译成英文的计算过程。
从上面三个简单的例子中可以看出，计算是依据一定规则，在有限的步骤内将输入转化为输出的过程。
2．可计算与不可计算
什么问题可以计算？什么问题不可计算？在20世纪之前，人们对这些问题并没有深入思考。虽然在对可计算性的有关数学描述中，定义了递归函数与可计算函数等，但实质上可计算性就是要求对某个函数或问题的计算过程可以用符号记录下来，或者说在有限步骤内可以完成计算。直到20世纪30年代，人们才从哥德尔(K.Godel)、丘奇(A.Church)、图灵(A.M.Turing)等科学家的研究中弄清楚，计算*重要的问题是清楚什么问题可计算，什么问题不可计算。
从计算机科学的角度而言，一个问题是否可计算与该问题是否具有相应的算法完全等价。一个生活问题能不能用计算机求解，关键是能不能把这个问题用计算机可以接受的方式表示出来，以及求解的过程是否能用算法计算。
3．计算的分类
计算的可行性是计算机科学的理论基础。现实世界需要计算的问题很多，如哪些问题可以自动计算，哪些问题可以在有限的时间、空间内自动计算，哪些问题不能计算，这些都体现了计算的复杂性和可行性。计算的可行性理论起源于对数学基础问题的研究，确定了哪些问题可以用计算机解决，哪些问题不可以用计算机解决。因此，根据计算的可行性，计算可分为硬计算和软计算两大类。
1)硬计算硬计算(传统计算)这个术语由美国加州大学的Cadenza教授于1996年提出，长时间用于解决各种不同的问题。
硬计算解决问题时，一般要遵循如下步骤：
第1步：分析与问题相关的变量，然后分为两组，即输入或条件变量(输入数据A)，以及输出或行动变量(输出数据B)。
第2步：数学方程建立数学关系(f(A)=B)。
第3步：用解析或数学方法求解方程。
第4步：基于数学方程的解，确定解决问题的思路和方法。
硬计算的主要特征是严格、确定和精确。但硬计算不适合处理现实生活中的许多不确定、不精确问题。
2)软计算
软计算通过对不确定、不精确及不完全真值的容错以取得低代价的解决方案。它通过模拟自然界中智能系统的生化过程(人的感知、脑结构、进化等)来有效地处理日常生活中的问题。软计算包括模糊逻辑、人工神经网络、遗传算法和混沌理论等几种计算模式。这些模式是互补及相互配合的，因此在许多应用系统中组合使用。
计算能力是人类的基本能力之一，计算工具则是用于完成计算的器具。计算不仅仅是一种数据分析的过程，更是一种用于思考和发现问题的方法，这种思维方式伴随着人类计算工具的产生、发展过程。下面，我们就追随计算工具的发展历程，探索计算工具中包含的计算思维方式。
1.1.2 计算工具的发展史
人类发明了各种计算工具，从古老的“结绳记事”到算盘、计算尺、差分机到现代计算机等。计算的思维方式指引着计算工具经历了从简单到复杂、从低级到高级、从手动到自动的发展过程，而且还在不断发展。回顾计算工具的发展历史，大致可以划分为四个阶段。
1．手动式计算工具
人类计算的行为由来已久，远古时代，人类就有了计算需求和解决问题的能力。双手是人类*初的计算工具，掰手指头数数是人类*早的计算方法。人有十个手指头，因此十进制成为人们熟悉的计数法。由于双手的局限和社会生产力的发展，人类开始使用石头、结绳、小棍子等工具进行计算。英文单词的计算一词calculation的字根为calculus，其本意就是用于计算的小石子。
1)算筹
我国古代劳动人民*先创造和使用了一种简单的计算工具——算筹。根据史书的记载，算筹是一根根同样长短和粗细的小棍子，多用竹子制成，也有的用木头、兽骨、象牙、金属等材料制成。算筹采用十进制记数法，有纵式和横式两种摆法，这两种摆法都可以表示1、2、3、4、5、6、7、8、9九个数字，数字0用空位表示，如图1.2所示。
图1.2 算筹
在春秋战国时期，算筹的使用已经非常普遍了。算筹的记数方法为：个位用纵式，十位用横式，百位用纵式，千位用横式， ，这样从右到左，纵横相间，就可以表示任意大的自然数。
2)算盘
计算工具发展史上的第一次重大改革是算盘，也是我国古代劳动人民首先创造和使用的。算盘由算筹演变而来，并且和算筹并存竞争了一个时期，终于在元代后期取代了算筹。算盘采用十进制记数法并有一整套计算口诀，如“三下五除二”“七上八下”等算法，这是*早的体系化算法。算盘能够进行基本的算术运算，是公认的*早使用的计算工具。
3)Napier算筹
1617年，英国数学家约翰 内皮尔(John Napier)发明了Napier算筹，也称Napier算筹，如图1.3所示。
图1.3 Napier算筹
Napier算筹由10根长条状的木棍组成，每根木棍的表面雕刻着一位数字的乘法表，右边第一根木棍是固定的，其余木棍可以根据计算的需要进行拼合和调换位置。Napier算筹可以用加法和一位数乘法代替多位数乘法，也可以用除数为一位数的除法和减法代替多位数除法，从而大大简化了数值计算过程。
4)对数计算尺
1621年，英国数学家威廉 奥特雷德(William Oughtred)根据对数原理发明了对数计算尺，也称圆形计算尺，如图1.4所示。
对数计算尺在两个圆盘的边缘标注对数刻度，然后让它们相对转动，就可以基于对数原理用加减运算来实现乘除运算。
17世纪中期，对数计算尺改进为尺座和在尺座内部移动的滑尺。18世纪末，发明蒸汽机的瓦特独具匠心，在尺座上添置了一个滑标，用来存储计算的中间结果。对数计算尺不仅能进行加、减、乘、除、乘方、开方运算，而且可以计算三角函数、指数函数和对数函数，它一直使用到袖珍电子计算器面世。
即使在20世纪60年代，对数计算尺的使用仍然是理工科大学生必须掌握的基本功，是工程师身份的一种象征。
图1.4 对数计算尺
2．机械式计算工具
1)帕斯卡加法器
17世纪，欧洲出现了利用齿轮技术的计算工具。1642年，法国数学家布菜士 帕斯卡(Blaise Pascal)发明了帕斯卡加法器，如图1.5所示。
图1.5 帕斯卡加法器
帕斯卡加法器是由齿轮组成、以发条为动力，通过转动齿轮来实现加减运算，用连杆实现进位的计算装置。帕斯卡从加法器的成功中得出结论：人的某些思维过程与机械过程没有差别，因此可以设想用机械来模拟人的思维活动。这是人类历史上第一台机械式计算工具，其原理对后来的计算工具产生了深远的影响。
2)莱布尼茨四则运算器
德国哲学家、数学家戈特弗里德 威廉 莱布尼茨(Gottfried Wilhelm Leibniz)学习了关于帕斯卡加法器的论文，该论文激发了他强烈的发明欲望，决心把这种机器的功能扩大到乘除运算。1673年，莱布尼茨研制了一台能进行四则运算的机械式计算器，称为莱布尼茨四则运算器，如图1.6所示。
图1.6 莱布尼茨四则运算器
这台机器在进行乘法运算时采用进位-加(shift-add)，即步进( stepped reckoning)的方法，后来演化为二进制，被现代计算机采用。
3)巴贝奇差分机
19世纪中期，为了解决航海、工业生产和科学研究中的复杂计算问题，许多数学表(如对数表、函数表等)应运而生。这些数学表虽然带来了一定的方便，但由于采用人工计算，其中的错误很多。英国数学家查尔斯 巴贝奇(Charles Babbage)决心研制新的计算工具，专门用于航海和天文计算，用机器取代人工来计算这些实用价值很高的数学表。
巴贝奇在前人马洪发明的逻辑演示器的影响下，于1822年开始设计差分机(different engine)，其目标是能计算20位有效数字的6次多项式的值。在英国政府的支持下，巴贝奇差分机历时10年研制成功，如图1.7所示。
这是*早采用寄存器来存储数据的计算工具，体现了早期程序设计思想的萌芽，使计算工具从手动机械跃入自动机械的新时代，因此他被称为“计算之父”。
4)巴贝奇分析机1832年，巴贝奇开始进行新的研制计
划，设计一台能够处理数学公式的分析机(analytical engine)。在分析机的设计中，巴贝奇采用了三个具有现代意义的装置。
(1)存储装置：采用齿轮式装置的寄存器保存数据，既能存储运算数据，又能存储运算结果。
(2)运算装置：从寄存器取出数据进行加、减、乘、除运算，并且乘法以累次加法来实现，还能根据运算结果的状态改变计算的进程，用现代术语来说，就是条件转移。
(3)控制装置：使用指令自动控制操作顺序，选择所需处理的数据以及输出结果。
我们今天使用的每一台计算机都遵循巴贝奇的基本设计方案。但是巴贝奇先进的设计思想超越了当时的客观现实，由于当时的机械加工技术还达不到所要求的精度，这台以齿轮为元件、以蒸汽为动力的巴贝奇分析机一直到巴贝奇去世也没有完成。
3．机电式计算机
1)霍利里思制表机
1886年，美国统计学家赫尔曼 霍利里思(Herman Hollerith)借鉴了雅各织布机的穿孔卡原理，用穿孔卡片存储数据，采用机电技术取代了纯机械装置，制造了第一台可以自动进行加减四则运算、累计存档、制作报表的制表机，如图1.8所示。
这台制表机参与了美国1890年的人口普查工作，使预计10年的统计工作仅用1年零7个月就完成了，是人类历史上第一次利用计算机进行的大规模数据处理。霍利里思于1896年创建了制表机公司(Tabulating
展开
