第六讲 计算思维之问题求解思想—2

1、第六讲 计算思维之问题求解思想 主题一 探讨问题求解过程 主题二 相关知识的认识与了解 主题三 关于算法的理解 主题四 算法策略大搜罗 主题五 几个经典案例的算法实现主题二相关知识的认识与了解 数学建模 数据结构 程序设计数学建模 我们对具体问题进行分析、抽象、归纳和推理，从中发现可以用数学语言来描述的关系或规律，然后把这个实际问题化成一个数学问题，这就称为数学模型，而建立数学模型的整个过程就称为数学建模。数学建模 数学模型的定义 数学模型（Mathematical Model）是一种模拟，是用数学符号、数学式子、程序、图形等对实际问题本质属性的抽象而又简洁的刻划，它或能解释某些客观现象，或能

2、预测未来的发展规律，或能为控制某一现象的发展提供某种意义下的最优策略或较好策略。数学建模 数学模型的定义 数学建模是一种数学的思考方法，是运用数学的语言和方法，通过抽象、简化建立能近似刻画并“解决”实际问题的一种强有力的数学手段。 数学建模和计算机技术的相互辅佐和融合在知识经济时代的作用可谓是如虎添翼。数学建模 建立数学模型的方法和步骤 模型准备（问题的提出与分析）、模型假设与符号说明、模型的建立与求解、模型的分析与检验、模型的完善与推广模型的完善与推广模型的分析与检验模型的建立与求解模型假设与符号说明模型准备（问题的提出与分析）主题二相关知识的认识与了解 数学建模 数据结构 程序设计数据结构

3、 众所周知，计算机的算法和程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。数据的结构，直接影响问题求解算法的策略选择和程序的执行效率。数据结构定义 数据结构的定义 数据结构（Data Structure）是计算机存储、组织数据的方式。 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。 一般认为，一个数据结构是由数据元素依据某种逻辑联系组织起来的。数据结构定义数据结构的定义 数据结构主要包括三个组成成分：数据的逻辑结构，数据的物理（存储）结构和数据的运算结构。 数据的逻辑结构 数据的逻辑结构指反映数据元素

4、之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后件关系，而与它们在计算机中的存储位置无关。 逻辑结构有以下基本类型：集合结构、线性结构、非线性结构（树状结构和图形结构）。数据结构定义数据结构的定义 数据结构主要包括三个组成成分：数据的逻辑结构，数据的物理（存储）结构和数据的运算结构。 数据的物理结构 数据的物理（存储）结构指数据的逻辑结构在计算机存储空间的存放形式，是数据在计算机中的表示（又称映像）。它所研究的是数据结构在计算机中的实现方法，包括数据结构中元素的表示及元素间关系的表示。 数据的存储结构通常采用顺序存储或链式存储的方法。数据结构定义数据结构的定义 数据结构主要包括三

5、个组成成分：数据的逻辑结构，数据的物理（存储）结构和数据的运算结构。 数据结构的运算 数据的运算是数据结构的一个重要方面，讨论任一种数据结构时都离不开对该结构上的数据运算及其实现算法的讨论。 不同数据结构有其相应的若干运算。数据的运算是在数据的逻辑结构上定义的操作算法，如检索、插入、删除、更新和排序等。数据结构选择意义数据结构的选择意义 在许多类型的程序设计算法中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。 算法的设计取决于数据的逻辑结构，而算法的实

6、现依赖于数据采用的物理存储结构。 通常情况下，精心选择的数据结构可以给算法和程序带来更高的运行或者存储效率。数据结构常用数据结构 常用数据结构数组(Array) 在程序设计算法中，为了处理方便，把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。数据结构常用数据结构 常用数据结构栈(Stack) 栈是只能在某一端插入和删除数据的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。数据结构常用数据结构常用数据结构队列(Queue) 队列是一种特殊的线性表，它只允许

7、在表的前端（Front）进行删除操作，而在表的后端（Rear）进行插入操作。 进行插入操作的端称为队尾，进行删除操作的端称为队头。队列是按照“先进先出”或“后进后出”的原则组织数据的。队列中没有元素时称为空队列。数据结构常用数据结构常用数据结构链表(Linked list)数据结构常用数据结构常用数据结构链表(Linked list) 链表是一种物理存储单元上非连续、非顺序的存储结构，它既可以表示线性结构，也可以用于表示非线性结构。数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。 每个结点包括两个部分：一个是存储

8、数据元素的数据域，另一个是存储下个结点地址的指针域。导座员3排4座小明4排1座小强4排5座小红3排7座小丽1排2座小荣2排2座小佳2排6座小军3排13座小宇4排9座小伟3排10座小峰Null数据结构常用数据结构 常用数据结构树(Tree)校长教学副校长A分院教学副院长教学部主任家偶尔不叫事研究所所长研究所教师B分院教学副院长C分院教学副院长行政副校长A分院院长B分院院长C分院院长后勤副校长校医院院长校食堂负责人校环境保安负责人数据结构常用数据结构 常用数据结构树(Tree) 树是包含N（N0）个结点的有穷集合K，且在K中定义了一个关系N，N满足以下条件： 有且仅有一个结点K0，它对于关系N来说

9、没有前驱，称K0为树的根结点。简称为根（Root）。 除K0外，K中的每个结点，对于关系N来说有且仅有一个前驱。 K中各结点，对关系N来说可以有M个后继（M=0）。数据结构常用数据结构 常用数据结构图(Graph) 图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。小明小强小红小丽小军小峰朋友圈数据结构常用数据结构 常用数据结构堆(Heap)745颗糖果320颗糖果135颗糖果50颗糖果20颗糖果（原始袋）30颗糖果（原始袋）85颗糖果40颗糖果（原始袋）45颗糖果（原

10、始袋）185颗糖果90颗糖果（原始袋）95颗糖果（原始袋）425颗糖果205颗糖果100颗糖果（原始袋）105颗糖果（原始袋）225颗糖果 110颗糖果（原始袋）115颗糖果（原始袋）有10袋糖果，两两合并装到一个新袋子中，按每次确保糖果数最少的策略来组合合并装袋。数据结构常用数据结构 常用数据结构堆(Heap) 堆是一种特殊的树形数据结构，每个结点都有一个值。 通常我们所说的堆的数据结构，是指二叉堆。 堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。 堆总是一颗完全树。数据结构常用数据结构常用数据结构散列表(Hash)数据结构常用数据结构 常用数据结构散列表(Hash)3排

11、4座（304房号）小明4排1座（401房号）小强4排5座（405房号）小红3排7座（307房号）小丽1排2座（102房号）小荣2排2座（202房号）小佳2排6座（206房号）小军3排13座（313房号）小宇4排9座（409房号）小伟3排10座（310房号）小峰数据结构常用数据结构 常用数据结构散列表(Hash) 散列表是根据关键码值（Keyvalue）而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。 这个映射函数叫做散列函数，存放记录的数组叫做散列表。由此，不需比较便可直接取得所查记录。主题二相关知识的认识与了解 数学建模 数据结构 程序设计

12、程序设计在运用计算思维理念求解问题时，虽然需要经历分析抽象出数学模型、选择合适的数据结构以及整理归纳出解题算法等一系列阶段过程，但最终都要将算法转换成计算机可计算执行的计算机程序，经过程序的编辑和运行并进行测试、调整直至问题得到最终解答。程序设计计算机程序计算机程序 计算机程序（Computer Program）就是按照实际解决问题的算法步骤而事先编制好的、具有特殊功能的指令序列。序列由一串CPU能够识别并执行的基本指令组成，每一条指令规定了计算机应该进行什么操作（如加、减、乘、除、判断等）及操作需要的有关数据。计算机程序主要涉及两部分内容，即数据的描述和数据的处理。 数据的描述是指各种变量的

13、定义，也称数据结构描述； 数据的处理是指对变量的操作，这些操作按解决问题的步骤要求有一定的先后顺序和规则，也称为求解算法。程序设计计算机程序计算机程序 算法是程序的核心，它在程序编制、软件开发及整个计算机科学中占据重要地位。 数据结构是算法加工的对象，一个程序要进行计算或处理总是以某些数据为对象的，要设计一个好的程序就需要将这些数据按要求组成合适并高效的数据结构。 所以，可以说：数据结构+计算算法=程序数据结构计算算法程序程序设计计算机程序设计计算机程序设计 计算机程序设计（Computer Programming）是指设计、编制、调试程序的方法和过程。 程序设计通常分为问题建模，算法设计，编

14、写代码，编译调试和整理并写出文档资料五个阶段。 程序设计过程就是通过分析问题、确定算法、编程求解等步骤来解决问题的过程，其中，算法具有重要的作用，它能够提供一种思考问题的方向和方法。程序设计计算机程序设计计算机程序设计 在计算机中，把解决具体问题的过程准确完整地描述出来就形成解决该问题的算法。 在程序设计中，我们要考虑数据的结构和类型、变量的定义，要用到算法语句，要考虑使用顺序结构、选择结构和循环结构来控制程序等等，最终将一个具体的实际问题用程序设计语言表示出来并由计算机去执行完成。程序设计程序设计语言程序设计语言 程序设计语言（Programming Language）是用来编写计算机程序的

15、语言，是用户与计算机交流信息的工具。 程序设计语言的发展过程是伴随整个计算机技术的发展而进行，从最初的机器语言到汇编语言，再到各种结构化的高级语言，最后到支持面向对象技术的面向对象语言。这个发展过程，使程序设计者更容易学习掌握语言，能以更接近问题本质的方式去思考和描述问题。 常用高级语言包括：C语言系列（C+、C#、基本C）、JAVA语言、Visual BASIC语言等。程序设计程序构成元素 程序构成元素 虽然各种高级程序设计语言的应用领域不同，功能和风格也存在差异，但是一门语言所包含的主要内容却是类似的，程序设计语言的程序代码组成元素一般包括： 数据类型 语言元素 控制结构 程序模块等程序设

16、计程序构成元素 程序构成元素控制结构循环结构选择结构顺序结构语句元素表达式运算符常量变量函数赋值程序设计程序构成元素数据类型 计算机使用数据类型的目的是： 决定了该类型数据在计算机中的存储与表示方式； 决定了该类型数据的取值范围； 决定了该类型数据所能执行的操作； 不同程序设计语言所提供的数据类型的种类是不尽相同的。 提供的数据类型越多，解决处理实际问题时就方便容易，但这也增加了学习编程的难度。程序设计程序构成元素数据类型 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 在计算机中，数据就是各种数字、字符及所有能输入到计算机中，并能被计算机识别和处理的符号的集合。 常用的数据类型一

17、般有：整数类型、浮点数类型、字符类型、逻辑类型、指针类型、数组类型、记录类型、枚举类型、集合类型和文件等。程序设计程序构成元素数据类型 一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。可以认为，数据类型是在程序设计中已经实现了的数据结构。 另一方面，在程序设计过程中，当需要引入某种新的数据结构时，总是借助编程语言所提供的数据类型来描述数据的存储结构。程序设计程序构成元素语言元素 高级程序设计语言使用我们的日常文字、数学符号和表达式来书写程序，内容包括字母符号、数字符号、变量、常量、表达式、运算符、特殊字符和标准函数等。

18、这些用来表示书写程序的符号就是程序设计语言中的语言元素，不同的程序设计语言所使用的语言元素是不尽相同的，但基本一致。掌握和理解程序设计语言中的语言元素是正确书写程序的基础。程序设计程序构成元素语言元素变量 变量实际上是内存中的一个临时存储区域的编号或别名，用于存放程序中的数据和结果，是程序的基本操作对象。 程序设计时根据实际要求必须先定义好所需的变量，明确变量的类型和名称，程序运行时，语言处理程序根据定义好的变量数据类型，会在内存分配相应的存储空间，用于存放该变量的值。程序设计程序构成元素语言元素运算符 计算机可以进行各种运算，包括算术运算、逻辑运算、关系运算、字符运算和特殊运算。不同的程序设

19、计语言提供的运算符种类不同，表示形式也可能不同。一般有： 算术运算加、减、乘、除、整除和求余等； 字符运算合并字符串、取子字符串等。 关系运算大于、大于等于、小于、小于等于、等于、不等于等。 逻辑运算与、或、非等。程序设计程序构成元素语言元素标准函数 一般高级程序设计语言都提供许多常用的标准函数，供用户在程序中直接使用。这些标准函数实际上就是为完成某一特定任务而专门设计的一段程序。 标准函数一般分为：数学函数、字符串函数、类型转换函数、随机数函数、日期和时间函数和文件函数等。程序设计控制结构控制结构 通常，结构化的程序设计都包括顺序结构、选择结构和循环结构三类，它们构成了程序的主体。只是不同的

20、程序设计语言，具体表示的语句命令形式有所不同。程序设计控制结构 控制结构 在实际的应用程序开发中，顺序结构、选择结构和循环结构往往是综合在一起的使用的，从总体看一个应用程序可能很庞大很复杂，但如果从局部看却都是由这三种基本结构的嵌套和组合而成。程序设计控制结构控制结构顺序结构顺序结构是指程序的执行按语句的排列顺序从上到下依次执行，每条语句均被执行一次，直至结束。其为最常用、最简单、最基本的控制结构。控制结构选择结构选择结构是指程序中的某些语句的执行会受到某一条件的制约，当条件成立时，执行一部分语句，否则执行另外一些语句，也就是说，有些语句可能被跨过未被执行。选择结构又可分为：二路分支结构和多路

21、分支结构。程序设计控制结构控制结构循环结构 循环结构是指程序中的某些语句在某一条件成立时，需要重复执行，直到条件不成立时，才结束重复执行。 循环结构要特别注意的是在重复执行语句过程中，要有控制条件的语句，以避免出现死循环现象。程序设计程序过程模块程序过程模块 从软件开发的角度，一个功能丰富繁多、规模庞大复杂的项目，通常需要团队的合作，才能最大限度的缩短软件开发研制的周期。 同时，为了使整个程序结构清晰明了，避免代码冗余率，便于程序的调试维护和代码重复使用，通常会根据应用程序的规模和功能，将问题总体模块划分为若干个相对独立的子模块，使其中每个部分解决一个相对简单的功能。程序设计程序过程模块程序过

22、程模块 简单地说，这种程序设计思想就是“自顶向下、化整为零、逐步细化”的设计方法，即把一个庞大复杂的程序划分成若干个功能相对简单的子模块，这些子模块之间尽可能彼此独立，然后再通过过程调用语句把这些子模块联系起来，最终形成一个完整的程序。项目总模块项目分模块1项目子模块11项目子模块12项目分模块2项目子模块21项目子模块22项目子模块23项目分模块3项目子模块31项目子模块32项目分模块4项目子模块41项目子模块42项目子模块43项目子模块44项目子模块45程序设计程序过程模块程序过程模块 一个子程序即为一个程序模块。一个程序模块可以借助调用的方法与其他程序模块来建立彼此的联系，进而完成整个程

23、序功能。 这种程序设计的方法，称为模块化的程序设计高级程序设计语言都提供设计子程序模块的功能，一般将子程序模块称为过程或函数。 过程和函数的主要区别是过程没有返回值，函数可带回返回值。过程和函数需要先定义设计好后，才能被主程序调用。程序设计程序过程模块 程序过程模块程序设计程序设计方法程序设计方法结构化程序设计 结构化程序设计（Structured Programming）是一种程序设计的原则和方法。用几种标准的控制结构（顺序、分支和循环）通过重复和嵌套来表示。 结构化程序设计思想采用“自顶向下、逐步求精”的方法。按结构化程序设计的要求设计出的高级程序设计语言称为结构化程序设计语言。 利用结构化程序设计语言，或者说按结构化程序设计思想编写出来的程序称为结构化程序。结构化程序具有结构清晰、容易理解、容易修改、容易验证等特点。缺点就是代码的可重用性差；可维护性差；稳定性差；难以实现。程序设计程序设计方法程序设计方法面向对象程序设计 面向对象程序设计（Object Oriented Programming，OOP）是一种计算机编程架构。OOP的一条基本原则是计算机程序是由单个能够起到子程序作用的单元或对象组合而成。OOP达到了软件工程的三