大学计算机基础(第3版)

第3章第3章计 算 思 维【学习内容】 本章介绍计算思维与计算机问题求解，主要知识点如下。 （1） 计算思维的定义及其核心概念。 （2） 逻辑思维与算法思维。 （3） 问题求解策略。 （4） 模式与归纳。 （5） 抽象与建模。 （6） 评价解决方案。 （7） 计算机问题求解的步骤。 （8） 算法、数据结构与程序设计语言的关系。 （9） 算法设计常用策略。 （10） 程序设计语言要素。 【学习目标】 通过本章的学习，读者应该掌握以下内容。 （1） 了解计算思维的定义与核心概念。 （2） 理解分解法问题求解策略。 （3） 理解模式与归纳方法。 （4） 理解科学抽象方法与原则。 （5） 理解计算机问题求解的一般步骤。 （6） 理解算法的概念、算法的描述方法。 （7） 了解常用的算法设计策略和常用典型算法。 （8） 了解常用的数据结构及其特点。 （9） 了解算法复杂度等评价标准。 （10） 了解软件开发方法及其应用。 （11） 了解典型算法的Python实现。计算思维应成为信息社会每个人必须具备的基本技能。本节将围绕计算思维的核心概念——逻辑思维、算法思维、问题求解策略、模式与归纳、抽象与建模、解的评价，以及算法、数据结构与程序等内容展开，为读者利用计算思维解决各领域问题奠定基础。 3.1概述 1.5节中简要介绍了计算思维及其重要性，但目前仍没有一个明确而统一的计算思维的定义，不同的学者从不同的角度来定义计算思维，这些定义有很多相似的地方，但也有差别。例如，周以真认为，计算思维是定义和解决问题，并将其解决方案表达为人或机器能有效执行的形式的思维过程。也有学者认为计算思维是对问题进行抽象并形成自动化解决方案的思维活动，等等。因此，理解并学习计算思维的*好可行方法，是从各类定义中提取出共有的核心概念，识别出那些外围的、不应包括在计算思维定义中的非核心概念，然后聚焦于核心概念的学习。 大学计算机基础(第3版)第3章计算思维通常认为计算思维的核心概念有以下一些，本章将在后面具体介绍。 （1） 逻辑思维。 （2） 算法思维。 （3） 分解。 （4） 泛化与模式识别。 （5） 建模。 （6） 抽象。 （7） 评估。 而以下一些概念一般不认为是计算思维的核心概念。 （1） 数据表示。 （2） 批判性思维。 （3） 计算机科学。 （4） 自动化。 （5） 模拟与可视化。 计算思维不是计算机科学家所特有的，而应该成为信息社会每个人必须具备的基本技能。计算思维已经在其他学科中产生影响，而且这种影响在不断拓展和深入。计算机科学与生物、物理、化学，甚至经济学相结合，产生了新的交叉学科，改变了人们认识世界的方法。例如，计算生物学正在改变生物学家的思考方式，计算博弈理论正在改变经济学家的思考方式，纳米计算正在改变化学家的思考方式，量子计算正在改变物理学家的思考方式。 任何人都可以应用计算思维，利用计算机来解决其领域(不止是计算机科学)的问题。计算思维的核心概念对不同领域的人来说是不同的。例如，对计算机科学家来说，算法思维指的是对算法及其在不同问题上的应用进行研究；对数学家来说，算法思维可能意味着按照运算规则进行某一种运算；对科学家来说，算法思维可能指的是按照某个流程进行一次实验。再例如，用隐喻和比喻写故事，对语言学家来说就是使用了抽象，当科学家构建了一个模型，或数学家使用代数描述问题时，就意味着使用了抽象。 考虑这样一个场景，在各类表彰大会上，一般都要给被表彰者颁发奖状或证书，由于主席台场地所限，一次只能上去一部分人。每组获奖者在领取证书后，要拍照，然后退场。为使颁奖过程尽量高效，通常在一组人上台领奖时，下一组就已经在台下等候了。上一组人一离场，下一组人直接从台下登台重复领奖过程。这就是计算思维中流水线的应用。 也可从另一个角度来理解计算思维——计算思维不是什么，通过对这个问题的讨论和研究，能深入地理解计算思维。 首先，学习计算思维不等于学习计算机科学。后者学习的主要目标是学习和运用数学计算原理，来研究与计算机科学自身紧密相关的问题。前者的学习目标不是“像计算机科学家一样思考”，而是希望能用计算思维的核心概念，帮助解决日常生活或工作中的问题。其次，学习计算思维不是学习程序设计，后者的主要目的是如何更好地写程序，产出高质量的软件。前者会包含一部分程序设计的内容，但*主要的目标是如何在使用计算机的条件下，进行问题求解。 因此，学习计算思维的*终目标不是让每个人都像计算机科学家一样思考，而是能应用计算思维的概念，在所有学科领域内或学科之间解决问题、发现新问题。 此处，用一个简单的例子来展示利用计算思维求解问题与常用数学思维的区别。 例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的倍数，这样就检测出了条形码中的错误。 具体的计算过程: 从条形码*右边的数字开始，逐个取出数字，轮流用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*左边两位数字印刷反了，变成了8976 4549，则*后的计算结果是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计算思维的核心概念在条形码例子中的体现核心概念定义本例中的体现逻辑思维逻辑是研究推理的科学，逻辑思维帮助人们理解事物、建立和检查事实逻辑让人们能读懂程序，理解其检测错误的工作原理。 推理能用于预测检查正确或不正确的条形码时会发生什么算法与算法思维算法是用于完成某个任务的一系列指令或一组规则。算法思维能让人们设计出借助计算机解决问题的算法能帮助人们理解利用公式验证条形码正确性的指令序列。也可以设计其他的算法完成同样的验证分解分解是将问题或系统拆分成更小、更易管理的小问题或小系统的过程。 它有助于人们解决复杂的问题，因为拆分出的每个小部分都可以被单独解决，组合它们的解决方案后，可以构造出整个问题的解，而不需要一次考虑整个问题的解把“在条码中查找错误”这个问题分解成多个小问题，例如，把条码解码成数字，把这些数字相乘和相加，检查运算结果，以及如果有错误或问题时给出错误信息泛化与模式使用模式意味着发现解决方案之间的相似之处和共同的差异。 通过提取模式，可以做出预测、制定规则并解决更一般的问题，这就是泛化一个算法就能发现条形码中的典型错误，算法能够发现交替乘1和3的操作模式，用循环来消除重复的交替乘操作抽象抽象是通过识别和丢弃不必要的细节来简化事物，它使人们能处理复杂的问题。数据可以通过抽象来表示(例如，用数字来表示文本、图像、声音等)。 模拟提供了真实场景的抽象不同粗细的条纹表示不同的数字，一串数字表示一种产品。 此外，该程序用交替乘1和3来构造校验和，而其他场合使用不同的校验和(例如，信用卡号码的校验和是通过乘以2来构造的，而ISBN10号码用每个数字乘以不同的数来构造校验和)，所以，可以抽象出使用不同数字构造校验和的算法评估评估指以客观的和系统的方式做出判断，并评估问题的可能解决方案。 其目标是利用现有资源实现*有效率和*有效的解决方案对该算法可以考虑这些评估问题: 是否会发现所有可能的条形码错误?用该程序发现错误要花多长时间?一台小型机器能否快速高效地执行这个检错操作?3.2逻辑思维与算法思维 逻辑思维和算法思维都是计算思维的核心概念，处于非常重要的地位。关于逻辑和算法的内容，可以写成很厚的书籍。本节不会完备地介绍逻辑与算法相关的知识，而会关注于如何使读者形成逻辑思维和算法思维习惯的一些核心要素。 3.2.1逻辑思维 简单来说，逻辑是关于推理的科学，是一种区分正确和不正确论证的系统。所谓论证，指的是从假设出发，经过一系列推理，得出结论的过程。逻辑包含一组规则，当将这组规则应用于论证时，能证明什么是成立的。下面是一个典型的逻辑论证证明。1. 苏格拉底是人。 2. 所有的人都会死。 3. 所以，苏格拉底会死。即便是没学过哲学和逻辑，也能看懂这个论证证明。这样的推理过程在日常生活中经常被使用，例如，房间里有风，房间的窗户是开着的，所以，风是从窗户吹进来的。但是，这样的推理并不能保证总是对的，有时会导致错误的结论。同时，计算思维需要利用计算机自动地完成各种推理，因此，在学习如何得出计算的解之前，要学会如何正确地运用逻辑。 在逻辑推理中，所有已知的事实称为前提。前提的表示形式是带有真假含义的陈述句，因此，每个前提都对应一个值——“真”或“假”。在前面的苏格拉底论证中，前两句话就是前提——对应着“真”的两个陈述句。 有了前提后，就可以在此基础上进行推理，得出结论。推理的方法通常分为演绎推理和归纳推理。演绎推理从前提条件开始，推导出其结论，是*强的推理形式。初中数学中的几何证明，就是典型的演绎推理，从已知条件、公理和定理出发，证明题目结论的成立。例如，三角形内角和为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个红球和1个黑球。 2. 有100个人从袋子里取球，每人只能取1个。