专升本计算机-教学课件-2-计算思维(新版大纲新增内容)

计算思维考纲要求：（一）掌握计算思维的概念；了解计算思维在社会生活中的应用。（二）了解计算机求解问题的基本方法；掌握利用计算思维解决简单计算问题的方法。（三）掌握计算机算法的基本知识；了解典型问题求解策略、算法复杂度分析及对应

用程序进行时间优化和空间优化的实现方法与思路。（四）掌握计算机程序的基本结构（顺序结构、分支结构、循环结构）、程序流程表

达与分析方法（程序流程图、伪代码等）；了解面向对象程序设计的思想与方法。一、计算思维概述二、算法与数据结构

三、程序设计语言

四、面向对象程序设计目录一、计算思维概述1.1计算思维概念

计算思维是运用计算机科学的基础概念进行问题求解、系统设计，以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。计算思维由周以真于2006年3月首次提出。2010年，周以真教授又指出计算思维是与形式化问题及其解决方案相关的思维过程，其解决问题的表示形式应该能有效地被信息处理代理执行。

计算思维的本质是抽象和自动化。就是如何利用计算机去求解问题，确定合适的抽象；自动化是最终目标，选择合适的方法去解释执行该抽象，让机器去做计算的工作。1.2计算思维在社会生活中的应用

当我们早晨去学校时，会把当天需要的东西放进背包，这就是预置和缓存；

当有人弄丢他的手套时，你建议他沿走过的路寻找，这就是回溯；在超市付帐时，你应当去排哪个队呢？这就是多服务器系统的性能模型；

为什么停电时手机仍然可用？这就是失败的无关性和设计的冗余性；1.3计算思维的基本特征

1）是概念化，而不是程序化

像计算机科学家那样去思维意味着远不止能为计算机编程，还要求能够在抽象的多个层次上思维。2）是根本的，不是刻板的技能。

是一种根本技能，是人为了在现代社会中发挥职能所必须掌握的，刻板技能意味着机械的重复3）是人的，不是计算机的思维

计算思维是人类求解问题的途径，但决非要使人类像计算机那样思考。比如计算思维使用海量数据来加速计算，在时间和空间、处理能力和存储容量之间进行权衡，人并不需要具备这样的能力。1.3计算思维的基本特征

4）是数学和工程思维的互补与融合

计算机科学本质上源自数学思维和工程思维，像其它科学一样，其基础源自数学学科，但其实现过程又基于工程思维，计算机系统的目标是创造能与现实世界互相的系统。5）是思想，不是人造物

计算思维不只是我们生产的软硬件以物理形式到处呈现并时刻触及我们的生活，更重要的是还体现了人类用以接近和求解问题，管理日常生活、与他人交流互动的计算思想。1.4利用计算思维求解问题的一般方法

1、把实际的应用问题转化为数学问题，建立数学模型；2、设计算法；3、将算法编程实现；4、在计算机中运行求解

前两步是计算思维中的抽象，后两步是计算思维中的自动化。真题解析

二、算法与数据结构2.1概念与特征

数据结构+算法=程序，算法通俗讲就是解决某种问题所采用的一系列的方法和步骤。

算法可以看作是由有限个步骤组成的用来解决问题的过程，其实质反映的是解决问题的思路和步骤。2.1概念与特征

算法的特征：有穷性、确定性、可行性。

有穷性：一个算法应包含有限个操作步骤，也就是说，解决过程必须是可终止的。

确定性：算法的每一个步骤都必须明确定义，不应该产生二义性。

可行性：算法的每一个步骤都是可以在有限时间内完成的基本操作，并能得到确定的结果。

输入：有零个或多个输入，执行算法有时需要从外界取得必要的信息。

输出：有一个或多个输出。没有输出的算法是没有意义的。2.2算法的3种基本的控制结构1、顺序结构

是最简单、最基本的控制结构，其操作步骤是按照设置的先后顺序，一步一步的执行。2、选择结构

也叫分支结构，它首先需要判断给定条件的真假，然后选择执行方向和顺序3、循环结构

也叫重复结构，它在给定条件成立时，需要反复重复执行同一操作或类似操作。

2.3算法的表示方法常见的算法表示方法有：自然语言、流程图、N-S图、伪代码等。1、自然语言

（1）优点

通俗易懂

（2）缺点：

容易产生歧义，导致执行的不确定性。

当算法循环和分支较多时，很难清晰的表示出来。

自然语言表示的算法不便翻译成计算机程序设计语言。2.3算法的表示方法2、用流程图表示算法

流程图是一种常用的算法描述工具，主要采用一些图框表示各种操作，用箭头表示算法流程，其特点是直观形象，结构清晰，易于理解。

美国标准化协会ANSI规定了一些常用的流程图符号，已为世界各国程序工作者普遍采用。

2.3算法的表示方法2、用流程图表示算法inti=0;i

<20?输出i成立

不成立

i=i+1i是偶数?不成立

成立

结束开始i=0,cnt=0;i

<=100?cnt

=

cnt

+

i成立

不成立

i=i+1开始输出cnt结束inti=0;i

<20?输出i成立

不成立

i=i+1i是偶数?不成立

成立

结束开始i=0,cnt=0;i

<=100?cnt

=

cnt

+

i成立

不成立

i=i+1开始输出cnt结束2.3算法的表示方法3、N-S图表示法N-S图也称N-S流程图，这种流程图完全去掉了带箭头的流程线，对算法的每一步描述都用一个矩形框表示。

优点：

比文字描述更直观、形象、易于理解

比传统的流程图紧凑易画

废除流程线，整个算法结构是由各个基本结构按顺序组成，N-S图的上下顺序就是执行的时顺序。

2.3算法的表示方法4、伪代码表示法

伪代码是介于自然语言和计算机语言之间的文字和符号来描述算法的工具。1）优点：

书写方便、格式紧凑，易于理解，便于向计算机程序设计语言过渡2）缺点

由于语言的种类繁多，伪代码的语句不容易规范。2.3算法的表示方法4、伪代码表示法真题解析

2.4典型问题求解策略

算法策略就是在问题空间中搜索所有可能的解决问题的方法，直到选择一种有效的方法解决问题，策略是面向问题的，算法是面向实现的。

经典的算法策略主要包括：枚举算法、递推算法、递归算法、分治算法、贪心算法、回溯算法等。1、枚举算法

也叫穷举法，其思路就是对问题的所有可能的解空间逐一尝试，直到找到最终解。针对于要解决的问题，列举出它所有可能的情况，逐个判定哪些是符合问题所要求的约束条件，从而得到问题的解。

枚举算法的示例：百钱买百鸡

2.4典型问题求解策略2、递推算法

递推算法是通过已知条件，利用特定关系得出中间结论，直到得到结果的算法。

递推算法分为顺推和逆推两种。顺推就是从已知条件出发，逐步推算出要解决的问题的方法。逆推从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，是顺推法的逆过程。

示例：

斐波拉契数列，设它的函数为f(n),已知f(1)=1，f(2)=1;f(n)=f(n-2)+f(n-1)(n>=3,n∈N)。则我们通过顺推可以知道：f(3)=f(1)+f(2)=2,f(4)=f(2)+f(3)=3……直至我们要求的解

2.4典型问题求解策略3、递归算法递归算法是把问题转化为规模缩小了的同类问题的子问题，然后通过递归调用函数或过程来表示问题的解。

递归算法是一个程序或函数直接或间接调用自己本身。

示例：

汉诺塔问题

斐波拉契数列2.4典型问题求解策略4、分治算法

分治算法是将一个规模较大的问题，分解为若干个规模较小的子问题，这些子问题相互独立且与原问题性质相同，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解即为子问题的解的合并。

示例：

二分搜索

2.4典型问题求解策略5、贪心算法

是指在对问题求解时，总是做出在当前看来是最好的选择，也就是说，不从整体最优加以考虑，仅是局部最优解。贪心算法常常用于组合优化问题，它的求解过程是多步判断的过程。

示例：合并排序问题6、回溯算法

也称试探法，是一种优选搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。解决一个回溯问题，实际上就是一个决策树或回溯树的遍历过程。

示例：全排列问题、N皇后问题2.5算法评价

评价算法优劣的指标或条件：正确性、可读性、健壮性、复杂性1、正确性

算法应当能正确求解问题。正确性是评价算法的首要条件，一个正确的算法是指在合理的输入数据下，能在有限的运行时间内得到正确的结果。2、可读性

好的算法应当具有良好的可读性，容易理解3、健壮性（鲁棒性）

当输入非法数据时，算法也能适当的做出反应或进行处理，而不会产生莫名其妙的输出结果2.5算法评价4、复杂性

算法复杂性分为时间复杂度和空间复杂度，用于评价算法在运行时间和占用空间上的程度。

通常把算法中所消耗的时间的多少称为“算法的时间复杂度”，算法的时间效率是问题规模n的函数。可记作T(n)=O(f(n))，比如，算法的执行时间为3*n2+3n+1，则它的时间复杂度为T(n)=O(n2)

算法的时间复杂度一般有：O(1)常数级、O(logn)对数级、O(n)线性级、O(nc)多项式级（c为常数）、O(cn)指数级（c为常数）、O(n!)阶乘级

2.5算法评价4、复杂性算法在运行过程中所消耗的内存空间的大小被称为“算法的空间复杂度”。用S(n)表示。与算法的时间复杂度相同。

算法的空间复杂度也可表示为：S(n)=O(g(n))，表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。2.6数据结构

数据结构是从问题中抽象出来的数据之间的关系，代表信息的一种组织方式，用来反映一个数据的内部结构。

典型的数据结构包括线性表、树和图。

线性表是最基本、最简单也是最常用的一种数据结构。

堆栈和队列是两种特殊的线性表数据结构，前者是一种后进先出（FILO），后者是一种先进先出（FIFO）的集合。

2.6数据结构-堆栈2.6数据结构-队列

2.6数据结构-树

2.6数据结构-图

真题解析

2.7算法的时间和空间优化算法复杂度的优化，就是要将可行解提高到更优解，其最终目标是：要采用尽可能低的时间复杂度和空间复杂度，去完成一个算法的设计。1、无效操作剔除处理为了降低算法复杂度，一个首要的思路是：清理算法中的无效计算或无效存储。即首先尝试将代码中的无效计算、无效存储剔除。

比如，在一个穷举算法中，可以尝试缩小可用的穷举空间，以减少无用的穷举操作。或者尽量提高变量或数据结构的复用性，减少内存的使用。

2.7算法的时间和空间优化2、使用合理的算法和数据结构对于同一问题，可用的算法或数据结构可以有很多种，都能实现相同的目的，为了减少算法的时间和空间复杂性，可以选用最优的方案。

降低空间复杂度的核心思路就是，尽可能用低复杂度的数据结构，而不用高复杂度的数据结构；尽可能复用现有内存，而不是重新分配新的内存。降低时间复杂度常用的方法有递归、二分法、排序算法、动态规划等。2.7算法的时间和空间优化3、时间换空间或空间换时间由于系统资源是有限的，为了在有限的资源内，达成某些特定的性能目标，还可以使用时间换空间或者空间换时间的方法。

性能优化的关键在于掌握各部分组件的性能平衡点，如果系统CPU资源有空闲，但是内存使用紧张，便可以使用用时间换空间的策略，达到整体的性能改良；反之，CPU资源紧张，内存资源有空闲，则可以使用空间换时间的策略，提升整体性能。

时间换空间通常用于嵌入式设备，或者内存、硬盘空间不足的情况，通过使用牺牲CPU的方式，获得原本需要更多内存或者硬盘空间才能完成的工作。2.7算法的时间和空间优化2、时间换空间或空间换时间与时间换空间的方法相反，空间换时间则是尝试使用更多的内存或者磁盘空间换取CPU资源或者网络资源等，通过增加系统的内存消耗，来加快程序的运行速度。典型应用就是缓存的使用，缓存是一块额外的系统内存区，如果没有缓存，程序依然可以正常工作，但是在一般情况下，缓存中总是保存那些来之不易的数据，重新取得这些数据会花费大量的资源和时间，而通过缓存这块额外的内存，避免了频繁的资源消耗，加快了程序的运行速度。

三、程序设计语言

程序设计语言可以分为三类：机器语言、汇编语言、高级语言。其中，机器语言和汇编语言都属于低级语言。1、机器语言

机器语言是计算机系统唯一能直接识别、不需要翻译直接供机器使用的程序设计语言。

机器语言实际上是一串二进制指令代码，其中的每条语句称为指令。

机器语言的缺点：编写难掌握、编程繁琐、可读性差、容易出错、修改和调试均不方便。依赖于具体的机器，所以通用性和移植性很差。

机器语言的优点：能充分发挥硬件功能的特点，程序运行速度非常快，程序也可以编写的非常简洁。2、汇编语言是机器语言的“符号化”。

汇编语言和机器语言基本上一一对应的，但在表示方法上作了改进，用一种助记符来代替操作码，用符号来表示操作数地址（地址码）。例如用“ADD”表示加操作，用“MOV”来表示数据传送等。用助记符和符号地址来表示指令，容易辨认，给程序的编写带来了很大的方便。

汇编语言的优点：比机器语言直观、容易记忆和理解，比机器语言程序易读、易检查、易修改。

缺点：本质上仍然是面向机器的语言，依赖于具体的计算机、很难在系统间移植，这样的程序编写起来仍然比较困难，程序的可读性也比较差。

汇编语言不能直接被计算机直接识别和执行，把汇编语言源程序翻译成机器语言的过程称为汇编。3、高级语言高级语言是20世纪50年代后期开始出现的，是一种接近于人类自然语言的习惯、便于阅读理解、检查和修改。

高级语言易学易用、可读性好、表达能力强（接近自然语言）、通用性好（编写的程序能在不同的计算机系统上运行）。

高级语言不能被计算机直接识别和执行。

高级语言可以分成两类：解释型和编译型

解释型语言：有一个专门的解释程序，对源程序一边翻译、一边执行，不产生目标程序，如python。

编译型语言：需要由编译程序先翻译成目标程序以后才可以执行，会产生目标程序。如C语言、C++、Basic、Visualbasic、C#、java、Jbuilder、delphi。四、面向对象（ObjectOriented）程序设计1、概述目前程序设计方法主要有两种：结构化程序设计和面向对象程序设计。

在结构化程序设计中，任何程序段的编写都基于3种结构：顺序结构、分支结构、循环结构。程序具有明显的模块化特征，每个程序模块具有唯一的出口和入口语句。面向对象程序设计方法是尽可能模拟人类的思维方式，使得软件的开发方法与过程尽可能接近人类认识世界、解决现实问题的方法和过程，也即使得描述问题的问题空间与问题的解决方案空间在结构上尽可能一致，把客观世界中的实体抽象为问题域中的对象。

1、概述面向对象程序设计可以看作一种在程序中包含各种独立而又互相调用的对象的思想，这与传统的思想刚好相反：传统的程序设计主张将程序看作一系列函数的集合，以功能模块为中心，采用模块化自顶向下，逐步求精的设计过程。

面向对象程序设计把构成问题的事务抽象分解成各个对象，每一个对象都能够接受数据、处理数据并将数据传达给其它对象，或者调用其它对象的方法。

面向对象方法的优点：1）与人类习惯的思维方法一致；2）稳定性好；3）可重用性好；4）易于开发大型软件产品；

2、面向对象程序设计的基本思想

1）客观事物是由对象组成的，对象是在原事物基础上抽象的结果。2）对象是由属性和操作组成的，其属性反映了对象的数据信息特征，而操作则用来定义改变对象属性状态的各种操作方式。3）对象之间的联系通过消息传递机制来实现。4）对象可以按其属性来归类。5）对象具有封装、继承、多态的特性，可达到软件复用的目的。

面向对象的三（四）大特性：（抽象）、封装、继承、多态

把大象装进冰箱-结构化程序设计方法塞大象()开始结束打开冰箱门()关闭冰箱门()把大象装进冰箱-结构化程序设计方法双开门冰箱？双手开门单手开门开始结束大象愿意进？装大象揍大象()开始结束双开门冰箱？双手关门单手关门开始结束开冰箱门()关冰箱门()塞大象()是否否是否是把大象装进冰箱-面向对象程序设计方法属性：冰箱类型方法1：开门()方法2：关门()属性：意愿方法：挨揍(工具)方法3：装载(物品)冰箱对象大象对象大象.意愿=愿意？冰箱.开门()开始结束冰箱.关门()大象.挨揍(皮鞭)冰箱.装东西(大象)是否3、对象(object)

对象是面向对象方法中最基本的概念，可以用来表示客观世界中的任何实体，对象是实体的抽象。客观世界里的任何实体都可以被看作是对象。对象可以是具体的物（人、动物），也可以指某些概念（会议、课程）。

对象是构成系统的一个基本单位，任何对象都具有自己的特征和行为。所以对象由一组表示其静态特征的属性和它可执行的一组操作组成。

属性即对象所包含的信息（对象的特征），操作描述了对象执行的功能（对象具有的行为），操作也称为方法或服务。4、类（class）

类是指具有共同属性、共同方法的对象的集合。

类是对象的抽象，对象是类的一个实例（编程角度）。

类中所包含的所有东西，称为类的成员，类的成员包括类的属性和方法。

下方的代码定义了一个“狗”的类，这只狗具有毛发颜色和是否孕育两个属性，还有一个吠叫的方法。

5、消息（Message）

消息是一个对象的实例与另一个实例之间传递的信息。对象之间只能通过消息进行通信，而不允许在对象之外直接地访问它内部的属性，这是由封装原则引起的。

消息必须直接发给特定的对象，消息中包含所请求服务的必要信息，且遵守所规定的通信规格说明。