大学计算机 课件 【ch07】计算机问题求解与计算思维

大学计算机计算机问题求解与计算思维第七章计算机问题求解与计算思维概述011.1计算机问题求解随着科技的发展和计算机的普及，越来越多的人会使用计算机，利用计算机来帮助解决问题。计算机和人脑不一样，计算机是如何去“理解”人们需要解决的问题，找到解决问题的策略，从而完成问题的求解的呢？（1）把具体的问题抽象化，即建立合适的数学模型（2）对建立的数学模型进行求解，即设计可行的算法。(3）选择一种语言进行编程，使用计算机来执行算法得到问题的求解结果。(4）对编写完的代码进行调试运行，对算法的复杂性进行评价，在解决问题的基础上实现代码优化。1.2计算思维计算思维是一种思维过程，可以脱离计算机、互联网、人工智能等技术独立存在

。这种思维是人的思维

，而不是计算机的思维

，人用计算思维来控制计算设备

，从而更高效

、快速地完成单纯依靠人力无法完成的任务

，解决之前无法想象的问

题

，它是未来世界认

知、思考的常态思维方式

。也就是说

，计算思维教育不需要人人成为程序员

、工程师

，而是在未来拥有一种适配未来的思维模式

。计算思维是人类在未

来社会求解问题的重要手段，而不是让人像计算机一样机械运转。算法与数据结构022.1算法有穷性算法必须能在执行有限个步骤之后终止，且应该在可以接受的时间内结束。确定性算法中的每一个步骤都必须是确切定义的，不能产生二义性。2.1算法输入一个算法可以有零个或多个输入，以刻画运算对象的初始情况，零个输入是指算法本身定义了初始条件。输出一个算法有一个或多个输出，以反映对输入数据加工的结果。没有输出的算法是毫无意义的。可行性算法中执行的任何计算步骤都是可以被分解为基本的、可以被计算机理解和执行的操作步骤。2.2数据结构数据结构就是同一类数据元素中各元素之间的相互关系，是计算机存储、组织数据的方式，包括逻辑结构和物理结构。数据的逻辑结构和物理结构是数据结构两个密切相关的方面，同一逻辑结构可以对应不同的存储结构。算法的设计取决于数据的逻辑结构，而算法的实现依赖于指定的存储结构。数据结构的逻辑结构指的是前后数据元素之间的关系，而与它们在计算机中的存储位置无关。逻辑结构有集合、线性、树和图4种。2.2数据结构集合结构在集合结构中

，数据元素之间除了有“同属一个集合”

的相互关系，无其他关系

，所以说集合是元素关系最为松散的一种结构。线性结构在线性结构中

，数据元素存在

一对一的相互关系

，除第

l

个元素无直接前驱，最后一个元素无直接后继之外，其他每个数据元素都有一个前驱和后继。2.2数据结构树结构在树结构中，数据元素存在一对多的相互关系，直观来看

，树是以分支关系定义的层次结构

。树结构在客观世界中广泛存在

，如人类社会的族谱和各种

社会组织机构都可

用树来形象的表示

。图结构在图结构中

，数据元素存在多对多的相互关系

，图中任意两个元素之间都可能相关

，是一种比较复杂的数据结构

。图的应用极为广泛，已渗入如物理、化学、电子信息、计算机科学以及数学等分支

。2.3算法描述自然语言描述自然语言就是人们通常使用的语言，用自然语言描述算法通俗易懂

，但是容易产生歧义。所以用自然语言描述时要语言简练

、层次清晰。如计算1+2+3＋切，其中n是正整数，从键盘输入，用自然语言描述算法如下。Stepl：从键盘输入正整数lloStep2：设计算结果用s表示，且s初始化为OoStep3：设变量i的初值为loStep4：把i累加到s中。Step5:i的值加1。Step6：如果i＜「1，转Step4，否则转Step7oStep7：输出s的值。Step8：结束。2.3算法描述流程图描述流程图是采用一些图框来表示算法，各种操作内容写在框内

，流程线表示操作执行的顺序

。流程图

比文字方式更能直观明确地说明解决问题的

步骤。2.3算法描述N-S图描述1973年美国学者I.Nassi和B.Scheidennan

提出了一种符合结构化程序设计原则的图形描述工具，称为N-S图。在N-S图中，去掉了带箭头的流程线，全部算法写在一个矩形框

内，在该框内可以包含其他从属于它的框，或由一些基本的框组成一个大的框。结构化程

序中

3

种控制结构的

N-S

图如图

7.3

所示。2.3算法描述伪代码描述用流程图和N-S

图描述算法直观易懂，但是画起来都比较费

事。在设计一个算法过程中，因为需要对算法反复修改，所以用

图形描述算法不是很理想

。为了设计算法时方便

，常用一种称为

伪代码的描述方法。伪代码是用介于自然语言和程序设计语言之间

的文字和符号来描述算法的

。伪代码不使用图形

，在书写上方便

，格式紧凑

，比较好懂，同时伪代码更接近程序设计语言

，对算法的描述也更具体，因此，也更容易实现编码

。2.4算法评价一个特定问题的算法在大部分情况下都不是唯一的，也就是说，同一个问题

，可以有多种解决问题的算法，而一个算法的质量优劣将影响到算法乃至程序的执行效率

。通过对算法进行分析可以评价一个算法的优劣，所以算法分析的目的在于选择合适的算法和改进算法。评价一个算法需要从算法的正确性、可读性、健壮性和高效性几个方面来进行，算法的高效性分析又可分为时间复杂度分析和空间复杂度分析。算法的正确性、可读性、健壮性是在算法设计实现时应遵守的基本原则，而通过对算法高效性的分析，使得算法代码能进一步优化，尽量满足时间效率高和空间存储量低的需求。2.4算法评价空间复杂度一般情况下

，一个程序在机器上执行时

，除需要寄存本身所用的指令、常数、变量和

输入数据外，还需要一些对数据进行操作的辅助存储空间。其中，输入数据所占的具体存储空间取决于问题本身，与算法无关，所以分析算法的空间复杂度只需分析该算法在实现

时所需要的辅助空间就可以了

。算法的空间复杂度

，类似于算法的时间复杂度，采用渐进空间复杂度

C

Space

Complexity

）

作为算法所需存储空间的量度

，它也是问题规模n

的函数，记为

S(n)

=

Of

（n)

。

2.4算法评价可读性一个好的算法，首先应便于人们理解和交流，其次才是机器可执行。时间复杂度算法的时间复杂度是指执行算法所需要的计算工作量。正确性正确性是评价一个算法好坏最重要的标准，是指算法至少应该具有输入、输出和加工处理无歧义性，能正确反映问题的需求和得到问题的正确答案。健壮性当输入数据非法时，好的算法不会产生莫名其妙的输出结果，而是能恰当地做出正确反应或进行相应处理。算法评价算法评价算法评价算法评价010203042.5典型算法枚举算法又称穷举算法

，是最简单、最基础也是效率最低的算法

。作为一个应用比较广泛的算法之一

，枚举算法的优点很明显

：首先枚举具有很高的准确性

，只要时间足够，正确的枚举得到的结论是绝对正确的；其次枚举具有全面性

，因为它对所有方案全面搜索，所以它能得出所有的解。2.5典型算法递归算法：指一种通过重复将问题分解为同类子问题而解决问题

的方法。递归被用于解决很多的计算机科学问题

，因此它是计算机科学中十分重要的一个概念

。绝大多数编程语言支

持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。递归策略只需少量的代

码就可描述出解题过程所需要的多次重复计算，大大地减少了程序

的代码量。如汉诺塔问题

。有n

个盘子和

3

根柱子

：A

（源）、B

C

备用〉、c

c

目的〉，盘子的大小不同且中间有一孔，可以将盘子

“串”

在柱子上

，每个盘子只能放在比它

大的盘子上面

。

起初，所有盘子在

A

柱子上，目的是将盘子一个一个地从

A

柱子移动到

C

柱子上

。移动过

程中，可以使用

B

柱子，但盘子也只能放在比它大的盘子上面。2.5典型算法分治算法：是一种很重要的算法

，宇面上的解释是

“分而治之”，就是把一个难以直接解决的复杂问题分成两个或更多相同或相似的子问题

，再把子问题分成更

小的子问题．．．．．直到最后子问题可以简单地直接求解

，子问题的解或者子问题解的合并即

为原问题的解

。在这个过程中

，反复应用分治手段

，可以使子问题与原问题类型

一致而其规模却不断缩小

，最终使子问题缩小到很容易直接求出

其解

。这个技巧是很多高效

算法的基础

，如二分查找、排序算法

〈快速排序

、归并排序），傅里叶变换

（

快速傅里叶变换

〕

等。如给定一个有序数组array，要在这个数组中找一个值为x

的元素。这个元素可能存

在，也可能在数组中没有。2.5典型算法递推法：是一种重要的数学方法，在数学的各个领域中都有广泛的运用

，也是计算机用于数值计算的一个重要算法

。递推是指从己知的初始条件出发

，依据某种递推关系，逐次推出所要求的各中间结果

及最后结果。其中，初始条件、问题本身已经给定，或是通过对