第3 章计算思维
【学习内容】
本章介绍计算思维与计算机问题求解,主要知识点如下。
(1)计算思维的定义及其核心概念。
(2)逻辑思维与算法思维。
(3)问题求解策略。
(4)模式与归纳。
(5)抽象与建模。
(6)评价解决方案。
(7)计算机问题求解的步骤。
(8)应对错误
(9)测试与调试。
【学习目标】
通过本章的学习,读者应该掌握以下内容。
(1)了解计算思维的定义与核心概念。
(2)理解分解法问题求解策略。
(3)理解模式与归纳方法。
(4)理解科学抽象方法与原则。
(5)理解计算机问题求解的一般步骤。
(6)理解算法的概念、算法的描述方法。
(7)了解如何应对错误。
(8)了解常用避免与减缓错误的策略。
(9)了解测试与调试。
(10)了解软件开发方法及其应用。
计算思维应成为信息社会每个人必须具备的基本技能。本节将围绕计算思维的核心
概念———逻辑思维、算法思维、问题求解策略、模式与归纳、抽象与建模、解的评价,以及算
法、数据结构与程序等内容展开,为读者利用计算思维解决各领域问题奠定基础。
3.概述
1
1.但目前仍没有一个明确而统一的计算思
5节中简要介绍了计算思维及其重要性,
维的定义,不同的学者从不同的角度来定义计算思维,这些定义有很多相似的地方,但也
有差别。例如,周以真教授认为,计算思维是定义和解决问题,并将其解决方案表达为人
或机器能有效执行的形式的思维过程。也有学者认为计算思维是对问题进行抽象并形成
自动化解决方案的思维活动,等等。因此,理解并学习计算思维的最好可行方法,是从各
类定义中提取出共有的核心概念,识别出那些外围的、不应包括在计算思维定义中的非核
心概念,然后聚焦于核心概念的学习。
通常认为计算思维的核心概念有以下一些,本章将在后面具体介绍。
(1)逻辑思维。
(2)算法思维。
(3)分解。
(4)泛化与模式识别。
(5)建模。
(6)抽象。
(7)评估
。
而以下一些概念一般不认为是计算思维的核心概念
。
(1)数据表示。
(2)批判性思维。
(3)计算机科学。
(4)自动化。
(5)模拟与可视化。
计算思维不是计算机科学家所特有的,而应该成为信息社会每个人必须具备的基本
技能。计算思维已经在其他学科中产生影响,而且这种影响在不断拓展和深入。计算机
科学与生物、物理、化学,甚至经济学相结合,产生了新的交叉学科,改变了人们认识世界
的方法。例如,计算生物学正在改变生物学家的思考方式,计算博弈理论正在改变经济学
家的思考方式,纳米计算正在改变化学家的思考方式,量子计算正在改变物理学家的思考
方式。
任何人都可以应用计算思维,利用计算机来解决其领域(包括但不限于计算机科学)
的问题。计算思维的核心概念对不同领域的人来说是不同的。例如,对计算机科学家来
说,算法思维指的是对算法及其在不同问题上的应用进行研究;对数学家来说,算法思维
可能意味着按照运算规则进行某种运算;对科学家来说,算法思维可能指的是按照某个流
程进行一次实验。再例如,用隐喻和比喻写故事,对语言学家来说就是使用了抽象,当科
学家构建了一个模型,或数学家使用代数描述问题时,就意味着使用了抽象。
考虑这样一个场景,在各类表彰大会上,一般都要给被表彰者颁发奖状或证书,由于
第
3
章计算思维
55
大学计算机基础(第4 版)
主席台场地所限,一次只能上去一部分人。每组获奖者在领取证书后,要拍照,然后退场。
为使颁奖过程尽量高效,通常在一组获奖者上台领奖时,下一组获奖者就已经在台下等候
了。上一组获奖者一离场,下一组获奖者直接从台下登台重复领奖过程。这就是计算思
维中流水线的应用。
也可从另一个角度来理解计算思维———计算思维不是什么,通过对这个问题的讨论
和研究,能深入地理解计算思维。
首先,学习计算思维不等于学习计算机科学。后者学习的主要目标是学习和运用数
学计算原理,来研究与计算机科学自身紧密相关的问题。前者的学习目标不是“像计算机
科学家一样思考”,而是希望能用计算思维的核心概念,帮助解决日常生活或工作中的问
题。其次,学习计算思维不是学习程序设计,后者的主要目的是如何更好地写程序,产出
高质量的软件。前者会包含一部分程序设计的内容,但最主要的目标是如何在使用计算
机的条件下,进行问题求解。
因此,学习计算思维的最终目标不是让每个人都像计算机科学家一样思考,而是能应
用计算思维的概念,在所有学科领域内或学科之间解决问题、发现新问题。
此处,用一个简单的例子来展示利用计算思维求解问题与常用数学思维的区别。
例3-1 有一些数,除以10余7,除以7余4,除以4余1,求满足条件的最小正整数。
解:这些数满足的条件是比10的倍数小3,且比7的倍数小3,且比4的倍数小3。
即比10、7和4的公倍数小3的数都会满足条件。因此,最小的满足条件的数为10、7和4
最小公倍数减3,即140-3=137。
如果利用计算思维解这道题,核心是设计能自动执行的算法。思路是从1开始,不断
地枚举数并判断枚举的数是否满足题设条件。不满足条件,则增1枚举下一个数。重复
该过程,直到找到第一个满足条件的数,且第一个满足题目要求的数就是最小的数。按照
该思路编写的Python程序代码如下所示。这个程序利用题设条件做了优化,即该数除
以10余7,则这个数的个位数是7。因此,从7开始,每次增加10,获得下一个数。该程序
的输出为137,与求最小公倍数的方法得到的结果一致。
for i in range(7, 1000, 10):
if i%7 ==4 and i%4 ==1:
print(i)
break
在展开介绍计算思维的核心概念之前,先用一个简单的问题来说明各核心概念在问
图3-1 一个条形码示例
题求解时的体现。条形码是日常生活中常见的符号,如出现
在各种商品包装上的条形码,图3-1是一个条形码示例。条
形码的数字不是随便生成的,有一个公式,对条形码各位数
字进行运算,如果条形码正确,则得到的结果是10的倍数。
当条形码有错误(扫码器读入有误或印刷有错)或相邻两位
数字调换了位置,则组合后的结果将不是10的倍数,这样就
检测出了条形码中的错误。
56
第3 章 计算思维
具体的计算过程:从条形码最右边的数字开始,逐个取出数字,轮流用1和3乘以取
出的数字,然后把所有的乘积累加,看看得到的结果是否是10的倍数。对图3-1的示例,
最右边数字是9,则计算9×1,9的下一位数字是4,则计算4×3。照此依次计算5×1、
4×3、6×1、7×3、8×1和9×3,累加这些乘积,即9+12+5+12+6+21+8+27=100,
为10的倍数,因此,可以判断这个条形码是正确的。
假设扫码器将图3-1最左边的数字扫成了5,则最后的计算结果是9+12+5+12+
6+21+8+15=88,不是10的倍数,则检测到扫码错。又例如,如果图3-1最左边两位数
字印刷反了,变成了89764549,则最后的计算结果是98,也会检测到条形码的错误。
下面的代码给出了检测条形码正确性的Python实现。
barcode =input("请输入8 位条形码: ")
total =0
multiplier =1
position_in_code =len(barcode)
while position_in_code !=0:
total +=int(barcode[position_in_code-1]) * multiplier
if multiplier ==1:
multiplier =3
else:
multiplier =1
position_in_code -=1
if total %10 ==0:
print("条形码扫码正确!")
else:
print("条形码有错误!")
程序中将条形码以字符串的形式读入,然后position_in_code从最右边开始扫描,每扫
描一个字符,根据当前的状态决定是乘1还是乘3,并将字符转换成整数后再进行乘运算。
这个程序从设计到实现,处处都体现了计算思维的核心概念,总结于表3-1中。
表3-1 计算思维的核心概念在条形码例子中的体现
核心概念定 义本例中的体现
逻辑思维
逻辑是研究推理的科学,逻辑思维帮助人们
理解事物、建立和检查事实
逻辑让人们能读懂程序,理解其检测错
误的工作原理。推理能用于预测检查正
确或不正确的条形码时会发生什么
算法与算法
思维
算法是用于完成某个任务的一系列指令或
一组规则。算法思维能让人们设计出借助
计算机解决问题的算法
能帮助人们理解利用公式验证条形码
正确性的指令序列。也可以设计其他
的算法完成同样的验证
分解
分解是将问题或系统拆分成更小、更易管理
的小问题或小系统的过程。它有助于人们解
决复杂的问题,因为拆分出的每个小部分都
可以被单独解决,组合它们的解决方案后,
可以构造出整个问题的解,而不需要一次考
虑整个问题的解
把“在条形码中查找错误”这个问题分
解成多个小问题,例如,把条形码解码
成数字,把这些数字相乘和相加,检查
运算结果,以及如果有错误或问题时给
出错误信息
57
续表
核心概念定义本例中的体现
泛化与模式
使用模式意味着发现解决方案之间的相似
之处和共同的差异。通过提取模式,可以做
出预测、制定规则并解决更一般的问题,这
就是泛化
一个算法就能发现条形码中的典型错
误,算法能够发现交替乘1和乘3的操
作模式,用循环来消除重复的交替乘
操作
抽象
抽象是通过识别和丢弃不必要的细节来简
化事物,它使人们能处理复杂的问题。数据
可以通过抽象来表示(例如,用数字来表示
文本、图像、声音等) 。模拟提供了真实场景
的抽象
不同粗细的条纹表示不同的数字,一串
数字表示一种产品。此外,该程序用交
替乘1和乘3来构造校验和,而其他场
合使用不同的校验和(例如,信用卡号
码的校验和是通过乘以2来构造的,而
ISBN-10 号码用每个数字乘以不同的数
来构造校验和), 所以,可以抽象出使用
不同数字构造校验和的算法
评估
评估指以客观的和系统的方式做出判断,并
评估问题的可能解决方案。其目标是利用现
有资源实现最有效率和最有效的解决方案
对该算法可以考虑这些评估问题:是否
会发现所有可能的条形码错误? 用该
程序发现错误要花多长时间? 一台小
型机器能否快速高效地执行这个检错
操作?
3.逻辑思维与算法思维
2
逻辑思维和算法思维都是计算思维的核心概念,处于非常重要的地位。关于逻辑和
算法的内容,可以写成很厚的书籍。本节不会完备地介绍逻辑与算法相关的知识,而会关
注于如何使读者形成逻辑思维和算法思维习惯的一些核心要素。
3.1
逻辑思维
2.
简单来说,逻辑是关于推理的科学,是一种区分正确和不正确论证的系统。所谓论
证,指的是从假设出发,经过一系列推理,得出结论的过程。逻辑包含一组规则,当将这组
规则应用于论证时,能证明什么是成立的。下面是一个典型的逻辑论证证明。
1. 苏格拉底是人。
2. 所有的人都会死。
3. 所以,苏格拉底会死。
即便是没学过哲学和逻辑,也能看懂这个论证证明。这样的推理过程在日常生活中
经常被使用,例如,房间里有风,房间的窗户是开着的,所以,风是从窗户吹进来的。但是,
这样的推理并不能保证总是对的,有时会导致错误的结论。同时,计算思维需要利用计算
机自动地完成各种推理,因此,在学习如何得出计算的解之前,要学会如何正确地运用
大学计算机基础(第
4
版
)
逻辑。
在逻辑推理中,所有已知的事实称为前提。前提的表示形式是带有真假含义的陈述
句,因此,每个前提都对应一个值———“ 真”或“假”。在前面的苏格拉底论证中,前两句话
就是前提———对应着“真”的两个陈述句。
有了前提后,就可以在此基础上进行推理,得出结论。推理的方法通常分为演绎推理
和归纳推理。演绎推理从前提条件开始,推导出其结论,是最强的推理形式。初中数学中
的几何证明,就是典型的演绎推理,从已知条件、公理和定理出发,证明题目结论的成立。
例如,三角形的内角和为180°,△ABC
是一个三角形,所以,△ABC
的内角和为180°。
但是,也要注意在使用演绎推理时常犯的两种错误。第一种是前提有错,导致结论错
误。例如下面这个推理,第2个前提是错误的,所以,推理过程即便是正确的,结论也是错
误的。
1. 卡拉是条狗。
2. 所有的狗都是棕色的。
3. 所以,卡拉是棕色的。
第二种错误是因为结论与前提没有必然联系导致的,例如下面这个推理,其过程是错
的,所以导致结论是错的。
1. 所有的乒乓球是圆的。
2. 地球是圆的。
3. 所以,地球是乒乓球。
现实生活中其实很少使用演绎推理,因为演绎推理对所使用的前提要求较高,最好是
简洁、清晰的。但是,现实生活中碰到的情况主要是混杂而不明晰的,所以,常用的推理是
归纳推理。例如,直角三角形的内角和是180°;锐角三角形的内角和是180°;钝角三角形
的内角和是180°;直角三角形、锐角三角形和钝角三角形是全部的三角形;所以,一切三
角形的内角和都是180°。这个例子从直角三角形、锐角三角形和钝角三角形的内角和分
别都是180°这些个别性知识,推出了“一切三角形的内角和都是180°”这样的一般性结
论,这就是归纳推理。又如,在数学题目中看到数列0、2、4、6、8、10…时,会很自然地归纳
出这个数列是由所有非负偶数构成的,据此,有很大把握归纳出10 后面的数应是12 。
归纳推理对前提的要求较低,不一定是绝对的“真”或绝对的“假”,可以是“百分之多
少的真”。因此,得到的结论也不能保证是绝对的“真”或“假”,而是有一定可能可信的结
论。例如,下面的推理是正确的,在结合了概率知识后,结论是可信的。
1. 一个袋子里有99 个红球和一个黑球。
2. 有100 个人从袋子里取球,每人只能取一个。
3. 小明是100 人中的一人。
4. 所以,小明有很大可能取到一颗红球。
逻辑推理对掌握计算思维非常重要,因为最后的解决方案要在计算机上运行,计算机
给出的结果严格依赖于解决方案中的逻辑推理。因此,应用计算思维设计问题的解时,必
第
3
章计算思维
95
须保证以下3方面。
(1)推理是有效的。
(2)给计算机的输入是可靠的。
(3)能解释计算机的输出,是绝对正确的(演绎推理)还是可能正确的(归纳推理)。
日常生活中大量使用的是归纳推理,得出的结论通常是“百分之多少的真”,而计算机
更擅长处理非黑即白的绝对性问题。因此,为指示计算机进行逻辑决策,需要一种逻辑系
统,能将日常的推理系统映射到计算机能理解的形式上。布尔逻辑即是这样一种逻辑系
统,其处理的逻辑只能在“真”和“假”中取一个值。“真”和“假”在不同的问题背景下有不
同的形式,例如,Python中的True和False,数字电路里的0和1,等等。
布尔逻辑中的语句称为命题,命题指的是具有明确真假含义的陈述语句,其含义只能
为真(True)或假(False), 不能同时既为真又为假。其含义必须是明确的,而不是含糊的。
可以将这种陈述句进行符号化,即用一个字母来表示一个命题,这样的字母称为命题词。
多个命题结合起来构成更复杂的命题,称为复合命题,而连接命题的符号称为逻辑运
算符。
下面以五子棋为例,介绍布尔逻辑的相关知识。五子棋游戏是大家基本都玩过的棋
类游戏(见图3-2), 它是一种两人对弈的纯策略型棋类游戏,棋盘与围棋通用,是起源于
中国古代的传统黑白棋种之一。五子棋专用棋盘为15×15,盘面由纵横各十五条等距离
垂直交叉的平行线构成,共225 个交叉点,交叉点即为落子点,盘面正中一点为“天元”。
图3-
2
五子棋盘
五子棋的行棋顺序为黑先白后,从天元开始相互顺序落子。某些规划中,对双方前两
步的行棋有约束,可分解为以下几条规则,可见每条规则是一个命题。每个命题后面的字
母为其对应的命题词,注意字母的选取是任意的,也可用其他字母来表示这些命题。
1. 黑方的第一个棋子应下在天元上。(P)
2. 白方的第一个棋子只能下在与天元邻近的8个点上。(Q)
3. 黑方的第二个棋子只能下在与天元邻近的5×5 点上。(R)
4. 白棋的第二个棋子不受限制,可下在棋盘任意位置。(U)
大学计算机基础(第
4
版
)
第3 章 计算思维
可知这些条件必须同时成立,才是合规的下棋过程,即应该表达为“黑方的第一个棋
子应下在天元上;并且白方的第一个棋子只能下在与天元邻近的8个点上;并且黑方的第
二个棋子只能下在与天元邻近的5×5点上;并且白棋的第二个棋子不受限制,可下在棋
盘任意位置”。用来连接这种所有条件必须同时成立的“并且”,是一种逻辑运算符,称为
“与”(And),对应着Python中的and运算符。上述行棋规则可用Python表达式表达为
PandQandRandU。
五子棋判断胜负的规则较多,包括以下几条,每个命题后面的字母为其对应的命
题词。
1.最先在棋盘横向、竖向、斜向形成连续的相同色5个棋子的一方为胜。(P)
2.黑棋禁手判负,白方应立即向黑方指出禁手,自然而胜。(Q)
3.当黑方在落下关键的第五子时,若在形成五连的同时,又形成禁手,则禁手失效,黑方胜。(R)
4.黑方走出长连禁手时,白方无论何时指出,立即获胜。(U)
可知这些条件只要有一条成立,则棋局以某一方获胜而结束。因此,上述规则又可表
达为“最先在棋盘横向、竖向、斜向形成连续的相同色5个棋子的一方为胜;或黑棋禁手判
负,白方应立即向黑方指出禁手,自然而胜;或当黑方在落下关键的第五子时,若在形成五
连的同时,又形成禁手,则禁手失效,黑方胜;或黑方走出长连禁手时,白方无论何时指出,
立即获胜”。用来连接这种所有条件至少有一条成立的“或”,称为“或”(Or)逻辑运算符,
对应着Python中的or运算符。上述行棋规则可用Python表达式表达为PorQorR
orU。
除了上述五子棋规则外,其实还隐含着一些显而易见、一般不做专门说明的规则。例
如,如果棋盘上某个交叉点没有棋子,则该交叉点称为空闲交叉点。在遵循行棋规则的前
提下,只能将子落在空闲交叉点上。此处,“没有棋子”就是对“有棋子”的否定,此处“没”
是一种逻辑运算符,称为“非”(Not),对应着Python中的not运算符。假设“有棋子”被符
号化为P,则“没有棋子”可用Python表达式表达为notP。
考察前述五子棋胜负判断规则可知“若1~4规则至少有一条成立,则可判定黑/白方
获胜”“如果1~4的条件都不成立,那么双方依次落子”。其中的“若……则”和“如果……
那么”也是一种逻辑运算符,称为“蕴含”(implication),用于表达“如果……若”和“那
么……则”后命题之间的相关关系,“如果……若”后的命题称为前提,“那么……则”后的
命题称为结论,即前提为真,则结论也必须为真。注意蕴含只表示前提和结论是相关的,
但并不表示两者有因果关系。例如对命题“若1~4规则至少有一条成立,则棋局结束”,
当满足前提条件时,棋局确实会结束。但反过来,棋局结束是因为满足了1~4规则中的
一条,则不一定成立,有可能下满了整个棋盘,无处落子,棋局也会结束。基于前述讨论,
命题“若1~4规则至少有一条成立,则可判定黑/白方获胜”可用Python表述为下面的
代码。
if P or Q or R or U:
print("black or white win")
61
可知在五子棋游戏中,当棋盘上的交叉点都被占满后,棋局就没法继续下去了。对这
种情况,参照前面介绍,可表述为“双方都没法继续落子,当且仅当所有交叉点被占了”。
其中的当且仅当也是一种逻辑运算符,称为“等值”(equivalence)。等值是双向的,即第
一个命题为真,则第二个命题为真;第一个命题为假,则第二个命题为假。
当且仅当的英文为“,(”) 以P代表“双方都没法继续落子”,Q代表“所有交
叉点被占了”, 双方都没法继续落子, innyi可
被拆分为两个命题,分别如下。
则“
ifandonlyif
当且仅当(fadolf)所有交叉点被占了”
(1)双方都没法继续落子,i则P成立。此
时,可称Q是P的充分条件。
当(f)所有交叉点被占了:即当Q成立时,
(2)双方都没法继续落子,仅当(onlyif)所有交叉点被占了:即仅当Q成立时,P才
成立。也就是当Q不成立时,P也不成立。此时,可称Q是P的必要条件。
命题“双方都没法继续落子,当且仅当所有交叉点被占了”可用Python表述为P==Q 。
上述用字母表示命题,用运算符表示自然语言中的连词的方法,称为符号化,它是符
号逻辑的基础。符号逻辑是用数学方法研究逻辑或形式逻辑的学科。
3.2
算法思维
2.
逻辑系统给出了一组规则用来对(一部分)现实世界进行建模和推理,既可以描述静
态的事物,也可以描述事物的发展变化过程。例如,3.1节提到的五子棋游戏,用布尔逻
2.
辑描述了行棋规则和输赢判断规则,通过将这些逻辑规则与具体棋局结合,可以使逻辑命
题在具体棋局中做出真假判断,从而得出棋局在不同时刻的状态———谁赢了,是否还可继
续落子,等等。
算法构建于逻辑之上,但不等同于逻辑,算法既要基于逻辑做出逻辑判断,又要基于
逻辑判断执行某些动作,算法是现实世界计算系统的根本。
计算机执行算法时,只会关注当前正在执行的步骤,而在进入下一步时,会忘记上一
步做的所有事情。因此,要让算法正确执行,必须提供一种机制记住上一步或前几步做的
事情。算法在执行过程中有其需要处理的对象,如参与加运算的加数。因此,本质上,只
要记住每一步完成后,算法操作对象的值,即记住了该步所做的操作。这种用于保存操作
对象结果的机制称为变量,变量的值可通过赋值进行修改。这种每一步都需要记住的信
息称为状态,它是算法执行过程中需要记住的所有事物的总和。如五子棋游戏中,当前棋
盘黑子和白子的位置、轮到谁落子等信息,就是五子棋算法需要记住的状态信息。
第1章已经介绍过,算法中动作步骤的组织可有3种方式:顺序的、选择的、循环的。
顺序结构是最简单的、最常用的,只要按照解决问题的顺序写出相应的动作即可,动作执
行顺序是自上而下,依次执行。
日常生活中有很多做事情的动作就是典型的顺序结构。例如,吃小笼汤包的十二字
口诀“轻轻提、慢慢移、先开窗、后吸汤”,按照这个顺序,就能完成吃一个小笼汤包的动作。
非常重要的一点是顺序非常重要,这4个动作的顺序一旦发生变化,吃小笼汤包的事就不
大学计算机基础(第
4
版
)
会太顺利。
在地铁站自动售票机上买车票的过程,也是典型的顺序结构,如下所示。
1. 选择目的地。
2. 选择车票张数。
3. 投入硬币或插入合适的纸币。
4. 取找回的零钱。
5. 取车票。
现实世界中,还有许多场合需要先做逻辑判断,再根据判断,在多个动作中选择一个
执行,此时就需要用到选择结构。例如,学校鼓励学生帮家里做家务,考虑这样一个场景,
家长让你到楼下的小超市买一瓶生抽:如果有李锦记的生抽,就买李锦记的生抽,没有就
买其他品牌的生抽也行。这段话是指导你购买生抽的算法,重新编排一下,用选择结构进
行组织,如下所示。进入超市后,购买何种生抽是基于“是否有李锦记的生抽”的判断结
果,如果有,则买李锦记的生抽;如果没有,则买其他品牌的生抽。但是不论如何,只会买
一种生抽,而不会两种都买。
1. 如果超市有李锦记的生
抽
买李锦记的生抽
。
2. 否
则
买其他品牌的生抽
。
3. 带上生抽,离开超市回家。
在使用选择结构组织动作序列时,必须考虑全部可能的情况。特别是当算法要由计
算机来执行时,一定要记住计算机只会按你规定的动作执行,而不会帮你补充你遗忘的动
作,也不会对你给的含糊描述的动作做出额外的解释。
假设家长让你到楼下小超市买一瓶生抽,只吩咐了买李锦记的生抽。那么,如果当你
到超市时,发现没有李锦记的生抽,你会怎么办? 打电话回去问,还是自己随便买一瓶?
假设让计算机去买生抽的话,如果没有李锦记的生抽,计算机将留在超市,再也回不来了。
原因就是在设计买生抽的算法时,只考虑有李锦记的生抽情况,而没有告诉计算机,如果
没有李锦记的生抽怎么办。计算机只能执行你告诉它的动作,因此,如果超市没有李锦记
的生抽,它就再也回不来了。
在日常生活中,很多情况下需要重复做同一个动作,只有当达到了某个条件,才会停
下来。例如,学过的急救知识中,对呼吸、心跳不规则或停止的病人,需马上进行体外心脏
按压和口对口的人工呼吸。体外心脏按压和人工呼吸这个动作会重复做下去,直到病人
心跳恢复,或救护车到来。
对这些需要重复做多次的动作序列,可用循环结构来组织。通常用一些条件来控制
重复执行的动作序列,当达到停止条件时,可以结束重复动作的执行。这些停止条件即为
循环控制条件。通常有两种方式来决定重复做的事是否能停下来:一种是计数器控制;
另一种是标志值控制。
通常,为了加深对知识点的理解,老师要求学生多遍抄写某些重点知识点,假设是10
第
3
章计算思维
36
遍。那么,抄写的过程可以用下面的动作序列来描述。其中,“抄写次数”即为计数器,当
它达到10 时,就不要抄了。注意,也可以一开始就把抄写次数设成10,每抄写一遍,次数
减1,那么,此时的循环结束条件是什么呢? 下面是抄写知识点的算法描述。
1. 抄写次数是0。
2. 当抄写次数没到10,重复做下面的动作。
① 抄写一遍知识点。
② 抄写次数加1。
3. 完成作业。
下五子棋时,双方轮流落子,这个动作会重复执行下去。没办法像抄书一样,预先就
知道下多少个回合就会结束棋局。因此,很难设一个计数器来控制双方落子次数。此时,
可以通过设置一个标志值来控制落子的动作,这个值可以设成“黑胜或白胜”,黑胜或白胜
的判断可用3.1节的规则判断,此处不再展开。下棋的过程即可用下面的算法来
2.
描述。
1. 当不是黑胜或白胜时,重复做下面的动作。
① 黑落子。
② 白落子。
2. 宣布获胜方。
算法的有限性要求算法在有限步内必须停下来,那么,当算法中出现了循环时,必须
仔细设置循环的结束条件,确保循环总能停下来。通常称没法停下来的循环为无限循环,
算法中的无限循环通常是一种错误(Bug)。
3.3
小结
2.
逻辑思维和算法思维对掌握计算思维非常重要。在设计问题解决方案时,必须对逻
辑有很好的理解,并能将自然语言描述的命题等正确地转换成符号逻辑。逻辑同时是算
法的基础,也是计算的基础。算法描述的是过程性知识,这是利用计算思维设计问题解决
方案的基石。因此,需要掌握算法思维来正确地组织解决方案的动作序列。
3.问题求解策略
3
问题求解是一种创造性的工作,有时确实需要“灵光一闪”,好像得到解的过程无迹可
寻。但是,前人总结出来的系统化的求解问题的策略,对这种创造性的活动有很大的帮
助。此外,需要借助计算机求解的问题,通常不是人们用纸和笔就能解决的小规模问题,
因此,如何寻找大规模问题的解,分解策略就显得非常重要,也就不难理解其在计算思维
中的核心地位了。
大学计算机基础(第
4
版
)
3.基本步骤
3.1
人进行问题求解的过程可归纳为以下步骤①。
(1)理解问题:输入是什么,输出是什么。
(2)制订计划:准备如何解决问题。
(3)执行计划:具体解决问题。
(4)回头看:检查结果等。
对上述问题求解的步骤逐条进行考察,看看计算机能在每一步做些什么事。
(1)理解问题:计算机如何理解问题?
(2)制订计划:计算机能制订计划吗? 如果不能,如何针对计算机制订计划? 即什
么样的计划可能在计算机上实现? 什么样的形式才能让计算机知道该做什么和怎么做?
(3)执行计划:只有这个才真正是计算机能做的。
(4)回头看:为什么结果是(不)正确的? 求解效率还能提高吗?
因此,在理解问题并设计问题解时,解必须适合于在计算机上运行,并能发挥计算机
的威力,这种解通常以算法形式给出。此外,还可以看出,计算机只能完成人给它规定的
动作,而不要指望它做额外的事情。这也是运用计算思维求解问题时,需要特别注意的。
进行问题求解时,首先,不要害怕问题的规模和复杂度,复杂的大问题通常能被分解
成相关的小问题,而这些小问题是较易解决的。其次,不要一拿到问题就开始写解决方
案,这样做会导致对问题认识不清,可能会在解题过程中走偏,在错误的方向上越走越远。
因此,不论何种情况,都必须先理解问题。
问题求解就是要在问题(起点)和答案(终点)之间建立一个连接。理解问题阶段就是
要认清问题的起点和终点是什么,对起点的认识越深入,越能帮助人们发现什么是终点,
以及如何到达终点。所谓终点,指的是要达成的目标,而不是如何达成。在理解问题阶
段,要避免过早陷入寻找“如何做”中。
理解问题需要用到多方面的知识,如阅读理解、问题相关的背景知识、数学知识、物理
知识,等等,这些需要经过学习不断地积累,非一日之功。有些用于认识问题的建议,可以
帮助我们有效认识问题。
(1)对拿到的问题,尽量用自己的话再陈述一遍。
(2)尽量用图表或其他图形方式重新描述问题。
(3)尽量明确哪些是已知的,哪些是未知的,把未知的尽量明确。
(4)给出问题解决的标准,即明确“如何知道问题被解决了”,这常常就是问题求解的
目标
(
。
5)尽量用可度量的词汇来描述问题求解目标。
(6)大略地描述一下有效的解决方案看起来是什么样的,需要具备什么特征,等等。
对问题有很清楚的认识之后,可以开始制订解题计划。在制订解题计划过程中,有一
① 源自GeorgePolya的HowtoSolveIt
一书。
第
3
章计算思维
56
些需要时刻牢记的原则。
(1)解的质量。一般来说,某个问题的解会有多种,有些好,有些差,有些介于二者之
间。关注解的质量指的是寻求你所能找到的最优解。现实是有时最优解不存在,每种解
法有其好的一方面,此时,需要在各种解之间进行折中。
(2)协作。在制订解题计划过程中多与人交流,对发现解中的错误或改进解都会有
帮助。尽量尝试着向别人陈述你的解,与别人进行头脑风暴,用开放的心态考虑各种角度
反馈回来的意见,等等,都有助于通过协作完善解题计划。
(3)迭代。第一次得出的解题计划通常不是最好的那个。因此,在得出一个解题计
划后,多重复几次制订解题计划的步骤,不断地对解进行检查和改进,弥补不足。
3.2
分解法
3.
在各种解题策略中,分解法(Decomposition)是计算思维的核心概念之一。计算思维
通常用于解决大型复杂问题,而由于人每次能处理的问题规模有限,对大型复杂问题进行
分解是必需的。
采用分解法对问题进行划分,得到一组子问题,这些子问题是易于理解的,并且其解
是显而易见的。通常,这种分解过程会一直持续下去,直到每个子问题的解都很简单为
止。在分解过程中,子问题与原问题会形成一棵树。
计算机科学中的树结构与自然界的树是相反的———根在最顶上,向下生长。树结构
一般用来组织具有层次关系的数据。树中每个节点
或没有父节点,或有唯一的父节点。没有父节点的
节点是唯一的,称为根节点。每个节点可以有多个
子节点,没有子节点的节点称为叶节点。节点之间
用线连接。图3-3显示了一棵描述《红楼梦》中贾家
部分家族关系的树,线段代表树的边,用来表示父-子
层次关系。
以撰写某问卷调查报告为例,来展示如何进行
问题的分解。假设学校布置任务,要完成关于某主
题———如共享单车———的问卷调查报告。在确定
了主题后,撰写问卷调查报告不是一步就能完全解决的问题,因为要解决该问题,所需
考虑的细节太复杂,难以一次处理完,所以,需要将该问题进行分解。分解后各子问题
要变得简单,通过组合各子问题的解,构成整个问题的解。
通常来说,撰写问卷调查报告须分为几个步骤:制作问卷、收集数据、分析数据、撰写
报告、提交报告。据此,该问题分解为5个子问题,每个子问题将变得相对简单,且子问题
的目标很明确。分解后得到如图3-4所示的树形图。
通过分解,对撰写问卷调查这个问题认识更清楚,分解展示了解决问题所需的更多细
节,也展示了更多的未知因素。例如,撰写报告子问题中,报告由哪些部分组成,格式是什
么样的,目前还是未知的。此外,用什么方法收集数据,用什么工具分析数据,也是未知
大学计算机基础(第
4
版
)
图3-3《红楼梦》贾家部分家族关系树
的,等等。
图3-
4
撰写问卷调查报告的一级任务分解图
通过调研,发现有很多网站提供免费的问卷调查发布、数据统计与分析功能。假设拟
基于这样的网站进行本次问卷调查报告的撰写,那么“制作问卷”任务将被分解为编写问
卷题目和通过网络发布问卷两个子问题。收集数据、分析数据将变得简单,可直接利用网
站提供的功能,在人们通过计算机、手机等方式完成问卷调查时,自动完成数据的收集和
分析。因此,这两个问题将不再被分解。撰写报告任务相对而言较为复杂,可以根据报告
格式分解成多个子任务,例如,撰写摘要和引言,进行数据分析等。最后提交报告只需要
通过邮件将报告发送给老师即可。根据上述分析,可以得到如图3-5所示的问题分解树
形图。
图3-5撰写问卷调查报告的二级任务分解图
在问题分解时,按照子问题编号逐个考察,看该问题的解是否显而易见、是否足够简
单。如果是,则不需要再分解了,否则,可进一步分解成更小的子问题。该过程持续下去,
直到问题分解树中所有叶节点代表的问题足够简单为止。此外,在分解过程中,不要过度
陷入寻找问题的解的细节中,即如何做,而要将主要精力放在为解决该问题,需要做什么。
9节展示了如何用分解法打印月历。此处
再以绘制如图3-6所示的脸图形为例,利用分解
法,可将绘制机器人形状的任务分解成几个简单
图案的绘制,每个简单图案的绘制都是较为容
2.
易的
(
。
1)作为头的一个矩形。
(2)作为眼睛的两个同心圆图形(小的圆是
实心的)。
(3)作为嘴的一个矩形。
图3-6机器人脸图形示例
第
3
章计算思维
76
大学计算机基础(第4 版)
按照这个分解,绘制机器人脸图形的过程如图3-7所示。
图3-7 绘制机器人脸图形的过程
分解的结果是制订详细解题计划的起点。基于分解树,可以知道需要做什么才能
解决问题,可以看到各子问题之间的依赖关系———先做什么,后做什么,哪些可以一起
做。分解也有助于协作,可以将分解出来的子问题交给不同的人去(同时)完成,提高
效率。
3.3.3 关注点分离
将问题分解成易于单独求解的小问题。问题分解后,会发现大量的重复的模式出现
在解中,这些模式构成了程序设计语言的基本块,例如:①指令(即语句和表达式);②条
件;③循环;④子过程(即函数)。
对于非常小的程序,如最多几十行的程序,这些基本块足够用了。但是,随着程序规
模的增加,需要更好的方式来组织代码。正如不能用建造一个宠物窝的建筑技术,来建造
一座摩天大楼,需要额外的技术来建立大型的程序。复杂的解决方案要求将更小部分的
解组织成更大、更易于管理的最终解。
以图3-7的绘画案例为例子,展现如何在Python中应用这些技术。此处使用tkinter
进行图形绘制,这是Python标准的、内置的一个模块,提供了各种函数,以在画布上绘制
各种图形。其初始化方法如下所示:
import tkinter
window =tkinter.Tk()
c =tkinter.Canvas(window)
# 在此处绘制图形
c.pack()
window.mainloop()
这段代码是必要的初始化代码,运行后将创建并显示一个空白的窗口。后续,在注释
语句处可以添加绘画指令,可进行相应图形的绘制。
在运用分解策略将问题分解成易于单独求解的若干步骤(小问题)后,可以定义关注
点(Concern)为执行解决方案的一个独立步骤。例如,在电子表格中,计算单元格的内容,
并在屏幕上显示单元格,是两个不同的关注点。
68
第3 章 计算思维
在3.3.2节将绘制机器人脸形状的任务分解成几个简单图案的绘制后,可得到一个
绘制图3-7中简单脸的算法,如下所示。
1.以坐标(20,20)为左上角顶点,(80,80)为右下角顶点,线宽为2,绘制一个矩形。
2.以坐标(40,40)为圆心,6为半径,线宽为1,绘制一个圆。
3.以坐标(40,40)为圆心,3为半径,绘制一个实心圆。
4.以坐标(60,40)为圆心,6为半径,线宽为1,绘制一个圆。
5.以坐标(60,40)为圆心,3为半径,绘制一个实心圆。
6.以坐标(40,60)为左上角顶点,(60,70)为右下角顶点,线宽为1,绘制一个矩形。
该算法可用Python实现为如下的程序:
import tkinter
window =tkinter.Tk()
c =tkinter.Canvas(window)
#画脸
c.create_rectangle(20,20,80,80,width=2)
#画眼睛
c.create_oval(34,34,46,46,width=1)
c.create_oval(54,34,66,46,width=1)
#画眼珠
c.create_oval(37,37,43,43,fill='black')
c.create_oval(57,37,63,43,fill='black')
#画嘴巴
c.create_rectangle(40, 65, 60, 70, width=1)
c.pack()
window.mainloop()
程序中画圆用的是Canvas的create_oval(x0,y0,x1,y1,option,…)方法,其中
x0和y0为圆外接正方形的左上角坐标,x1和y1为圆外接正方形的右下角坐标,option
为其他的画圆选项,例如画实心圆,option为fill='black'或width=2等。因此,“以坐标
(40,40)为圆心,6为半径,线宽为1,绘制一个圆”,则该圆的外接正方形左上角点坐标为
(40-6,40-6),即(34,34),而外接正方形右下角点坐标为(40+6,40+6),即(46,46)。
其他圆的定位方法与此相同。绘制脸和嘴巴的矩形用Canvas的create_rectangle(x0,
y0,x1,y1,option,…)实现,其中x0和y0为矩形左上角顶点坐标,x1和y1为矩形右下
角顶点坐标,option为其他的画线选项,此处为fill=r' ed'。
可以将上述代码中从c.create_rectangle(20,20,80,80,width=2)开始到c.create_
rectangle(40,65,60,70,width=1)结束的几行代码置于一个函数内,如render_simple
_face,这样,在任何需要绘制脸的地方调用该函数即可。
将上述程序的c.create_rectangle(40,65,60,70,width=1)替换为c.create_arc
(40,60,60,70,start=0,extent=-180),即可绘制一张笑脸。此时,可以将绘制笑脸的
代码置于一个函数内,如render_simley_face。当然,也可将绘制2种脸的代码置于一个
69
函数内,如renderfaces(读者可以思考一下,这样做会带来哪些问题)。
带来的问题是(_) 画简单脸和笑脸的方法难以分离。因此,遵循关注点分离的原则———
一次只做一件事,为绘制每一种脸定义一个函数———一个函数只做一件事情。将功能分
成独立的单元可以提高解决方案的灵活性,Python的函数是创建一个独立代码块最基本
的手段,独立的代码块只执行(理想情况下)一个明确定义的任务。当每个函数都只有一
个关注点时,更易于发挥模块化的优势,以创造性地组合使用这些模块。
如果一个函数要负责实现多个功能,则该函数难以复用和测试。通过使每个函数只
关注一个明确定义的功能,能使:
(1)每个函数都变得更加可重用———在上例中,使用这些函数的人可以选择不同函
数绘制笑脸或简单脸。
(2)每个功能都是可测试的———因为可以测试函数这种小模块实现,所以更容易在
解决方案中定位错误。
严格来说,edrilfcedrie_ae各有两个关注点:组合各绘制
rnesmpeae和rnesmlyfc
步骤绘制整个脸图形,以(_) 及绘制(_) 单个的图形((_) 眼睛、眼珠、嘴等)。因为绘制各单个图形太
依赖于tkinter,如果将来要更新绘制机制以替换tkinter,则对函数中每行用到tkinter的
语句都要进行修改。因此,在关注点分离原则下,可以将函数的两个关注点进一步分离:
绘制完整图形只关注组合各步骤,而单个图形的绘制要分离到其他函数中。
通过关注分离点、模块划分,将完成类似功能的代码组织在一起,有助于提升程序的
可维护性。
3.模式与归纳
3.4
有效的问题求解不仅仅是找到一个解决方案就结束了,还涉及在得出解后,改进
解,使其更具效力。解的问题多了,会发现有些问题之间具有相似性,相似性会导致问
题的解中有些元素是重复出现的,或解中有些元素是类似的。仔细考察这些相似性,
找出解决方案中的相似性,归纳出普适解决方案,这是改进解决方案使其更具效力的
第一步。
寻找模式时,经常用到的原则有两个。
(1)不要重复自己。
(2)找出不同处并封装它们
。
以图3-7绘制脸图形的问题为例,再次考察前面给出的算法
。
1. 以坐标(20,20)为左上角顶点,(80)为右下角顶点,线宽为2,绘制一个矩形。
80,
2. 以坐标(40,40)为圆心,6为半径,线宽为1,绘制一个圆。
3. 以坐标(40,40)为圆心,3为半径,绘制一个实心圆。
4. 以坐标(60,40)为圆心,6为半径,线宽为1,绘制一个圆。
5. 以坐标(60,40)为圆心,3为半径,绘制一个实心圆。
6. 以坐标(40,60)为左上角顶点,(60,70)为右下角顶点,线宽为1,绘制一个矩形。
该算法中各指令间的模式很容易归纳出来。这种归纳使得解决方案变得简单,因为
大学计算机基础(第
4
版
)
包含的概念减少了。本例中,虽然有6步,但是只有绘制圆和绘制矩形两个概念,并且这
两个概念可以重复应用到绘制其他图形的解决方案中。
识别解决方案中的模式有一些通用的规则,下面列举这些规则。
(1)找出哪些名词重复出现,名词对应着解决方案的操作对象。
(2)找出哪些动词重复出现,动词对应着解决方案的操作。
(3)找出有哪些具体描述,这些具体描述在不同情况下可能被替换为其他的具体描
述。这些可被替换的描述称为变量。例如:
①形容词(红、长、光滑)表示事物的性质,可以归纳成(颜色、尺寸、材质), 在不同的
解决方案中会被其他相应的形容词替换。
②具体的数值,在不同的解决方案中会被其他的值替换
。
根据这些原则来考察上面绘制形状的算法,可以看到
:
(1)出现的名词:圆、半径、圆心、线宽。
(2)出现的动词:绘制。
(3)出现的形容词:黑色、实心。
(4)出现的数值:各个坐标。
进一步考察,有些名词是算法操作的对象,如圆、矩形,而有些是对象的性质,如半径、
圆心、线宽。因此,矩形和圆形是形状的特例,“形状”是矩形和圆的归纳。算法中的动词
只有一个,即绘制,它是该算法的核心操作。操作通常需要操作对象,对象是可变的,因
此,通常以参数形式出现。在该算法中,绘制的参数是形状。
算法中的形容词除了颜色,还有实心。所谓实心,指的是用某种颜色填充某个形状。
因此,又发现算法的一个操作,该操作有两个参数:颜色和形状。算法中出现的所有数值
都是坐标,是操作对象的属性,不同的对象,坐标值不同。
根据上述分析,可以对该算法进行如下归纳(带括号的操作,括号中是该操作的
参数)、
(1)绘制(形状)。一个画给定形状的操作。
(2)填充(形状,颜色)。一个用给定颜色涂满给定形状内部的操作。
(3)形状。带有外部边界的对象,特殊形状如下。
①圆:具有半径、圆心和线宽属性的形状。
②线:具有两个端点和线宽属性的形状。
至此,从一个具体形状的绘制算法出发,归纳出了其中的模式,并对其进行了简化。
归纳出来的模式可用于绘制其他形状的算法。
上述对算法中模式的归纳还停留在操作和操作对象上,更复杂的模式需要拓展视野,
寻找不同操作步之间的共性。这种归纳相对而言更难,并且需要更多的经验。但是这种
归纳是值得的,后面可以看到这种模式的归纳带来的效力。
简而言之,更复杂模式的归纳有下面这些可遵循的原则。
(1)操作步间的模式可归纳为循环。
(2)操作步块间的模式可归纳为子过程(函数)。
(3)条件和等式间的模式可归纳为规则。
第
3
章计算思维
17
1.
归纳为循环
仍以图3-7绘制脸图形的问题为例,考察算法中其中某几步。
1. 以坐标(40,40)为圆心,6为半径,线宽为1,绘制一个圆。
2. 以坐标(40,40)为圆心,3为半径,绘制一个实心圆。
3. 以坐标(60,40)为圆心,6为半径,线宽为1,绘制一个圆。
4. 以坐标(60,40)为圆心,3为半径,绘制一个实心圆。
经观察,可以发现第3、4步重复了第1、2步,唯一的差别是圆心坐标。由此,可以将
这4步归纳为一个循环,如下所示。
1. 令坐标集合为{(40,40),(60,40 )}。
2. 对坐标集合中的每个坐标(x,y):
① 以坐标(x,y)为圆心,6为半径,线宽为1,绘制一个圆。
② 以坐标(x,y)为圆心,3为半径,绘制一个实心圆。
至此,归纳出了一个循环,循环的控制条件是坐标集合中的所有元素,每次会用集合
中每个元素的值替换x和y,分别执行循环中的两个绘制操作,即第一次x=40 且y=40,
第二次x=60 且y=40 。
2.
归纳为子过程
子过程是对操作步块间的模式进行归纳,操作步块是由多个操作步构成的结构,如上
面的循环就是一个操作步块。该循环中两个绘制动作实现的功能是绘制一个眼睛,将这
两个绘制动作置于循环内,是为了连续绘制两个眼睛。
假设在某次绘制形状时,需要绘制多个脸的形状,那么,绘制两个眼睛的循环将在绘
制算法的多个地方出现。此时,多次出现的操作步块就会呈现出相似或相同的模式,当需
要更改绘制眼睛的方法时,需要在算法的多个地方进行修改。对此可以进行改进,进一步
归纳出绘制眼睛的子过程,将绘制眼睛的操作集中到该子过程内,而不需要在算法中重复
出现多次具体绘制眼睛的操作。
对上面归纳出的循环进一步归纳,可以看到,半径和线宽是可变的,因此,可归纳为如
下步骤。
1. 以坐标(x,y)为圆心,1为半径,线宽为w,绘制一个圆。
r
2. 以坐标(为圆心,2为半径,绘制一个实心圆。
x,y) r
基于此,可以定义一个画眼睛的子过程。
“画眼睛”是一个子过程,参数为(x,y,1,r2,w)。
1. 以坐标(x,y)为圆心,1为半径, w,绘制一个圆。线宽为(r)
2. 以坐标(为圆心为半径,绘制一个实心圆。,2(r)
x,y) r
大学计算机基础(第
4
版
)
现在,当需要绘制眼睛时,只需要用特定的参数调用“画眼睛”子过程即可。
例如:
1. 以r1=6、r2=3、x=40 、y=40 、w=1为参数调用“画眼睛”。
2. 以r1=6、r2=3、x=60 、y=40 、w=1为参数调用“画眼睛”。
3. 以r1=4、r2=2、x=240 、y=40 、w=1为参数调用“画眼睛”。
4. 以r1=4、r2=2、x=250 、y=40 、w=1为参数调用“画眼睛”。
可以看到,归纳出子过程后,绘制眼睛的操作集中在了子过程内,其他需要绘制眼睛
的操作变成了子过程调用。并且,不同的参数可以绘制不同的眼睛。这样带来的好处是
不言而喻的。
3.
归纳为规则
进一步考察“画眼睛”操作,可以发现构成眼睛的两个同心圆中,内圆半径是外圆半径
的1/2。如果对任何形状的眼睛来说,这个归纳都是成立的,那么,可进一步改进“画眼
睛”子过程,如下所示。此处总结出来的半径间的关系就是一条规则。
“画眼睛”是一个子过程,参数为(x,y,r,w)。
1. 以坐标(x,y) r为半径, 绘制一个圆。
为圆心,线宽为w,
2. 以坐标(x,y)为圆心,r为半径,绘制一个实心圆。
2
规则通常为“当……” 或“如果…… 则……” 。例如,对绘制形状的问题来说,算法中有
一些圆是不需要填充的,其实隐含着使用背景颜色填充这样的圆。因此,可归纳出一条规
则:如果绘制的圆不是实心的,则其内部用背景的颜色填充。
3.5
小结
3.
分解与归纳是相关的概念,分解将问题拆分成小问题,而归纳是将解决方案中的小步
骤组合成较大的步骤。归纳的目的是改进问题的解,使其更易于处理,适用于更多的相似
问题。
3.抽象与建模
4
抽象是计算思维的核心概念,对问题求解有非常大的作用,它会让人们聚焦于求解问
题相关的细节,而避免无用细节的干扰。对抽象出来的结果,建模是用另一种方式对其进
行描述,包括其静态的属性和动态的行为,利用前面所学的逻辑思维和算法思维,可以在
建模的基础上构建出计算的解。
第
3
章计算思维
37