第6章 问题求解与程序设计

1、WLJX .KMUST.EDU.CN大学计算机基础大学计算机基础昆明理工大学昆明理工大学. .计算中心计算中心大学计算机基础大学计算机基础昆明理工大学昆明理工大学2第第6 6章章 问题求解与程序设计问题求解与程序设计6.16.1计算机求解问题的方法计算机求解问题的方法6.26.2算法及算法的描述算法及算法的描述6.36.3程序设计语言与程序设计程序设计语言与程序设计6.46.4程序设计方法程序设计方法6.56.5计算思维能力的培养计算思维能力的培养大学计算机基础大学计算机基础昆明理工大学昆明理工大学CH6 CH6 问题求解与程序设计问题求解与程序设计3计算机应用的本质计算机应用的本质就是在计算

2、能力可行的就是在计算能力可行的范围内，通过人类思维获得求解问题的方法，范围内，通过人类思维获得求解问题的方法，并通过计算机加以计算的过程。并通过计算机加以计算的过程。大学计算机基础大学计算机基础昆明理工大学昆明理工大学6.1 6.1 计算机求解问题的方法计算机求解问题的方法4计算机求解问题的关键步骤：（1）界定问题（2）分析问题（3）建模（4）建立算法（5）编程实现大学计算机基础大学计算机基础昆明理工大学昆明理工大学6.2 6.2 算法及算法描述算法及算法描述.1算法的定义算法的定义算法（算法（AlgorithmAlgorithm）是指完成某一特定任务所需要的具体）是指完成某一

3、特定任务所需要的具体方法和步骤，是有穷规则的集合。方法和步骤，是有穷规则的集合。生活中的算法生活中的算法算法无处不在：算法无处不在：超市收银超市收银旅程安排（时间、里程、花费）旅程安排（时间、里程、花费）手机话费手机话费省钱方案省钱方案如何合理安排学习和生活时间才能让学习效率最高如何合理安排学习和生活时间才能让学习效率最高5大学计算机基础大学计算机基础昆明理工大学昆明理工大学6.2 6.2 算法及算法描述算法及算法描述.1算法的定义算法的定义算法算法贯穿古今贯穿古今公元前公元前20002000年，古巴比伦人年，古巴比伦人在黏土板上记载的利息与本在黏土板上记载的利息与本金的计算金

4、的计算6公元前公元前300300年，欧几里得年，欧几里得在在几何原本几何原本中创立中创立了逻辑演绎体系了逻辑演绎体系公元公元1 1世纪，西汉张苍在世纪，西汉张苍在九章算术九章算术中创建了中创建了机械化算法体系机械化算法体系艾达艾达.拜伦（拜伦（ 1815-1852）计算机算法创始人计算机算法创始人大学计算机基础大学计算机基础昆明理工大学昆明理工大学6.2 6.2 算法及算法描述算法及算法描述6.2.2 6.2.2 算法的基本特征算法的基本特征1.1.有零个或多个输入有零个或多个输入：需要从外界获取必要的信息：需要从外界获取必要的信息2.2.有一个或多个输出有一个或多个输出：需要把求得得解进行输

5、出：需要把求得得解进行输出3.3.确定性确定性：每一步必须明确：每一步必须明确4.4.有穷性有穷性：算法要包含有限的步骤：算法要包含有限的步骤5.5.可行性可行性：算法描述的所有操作都可以通过已经实现的：算法描述的所有操作都可以通过已经实现的基本运算的有限次执行来实现。基本运算的有限次执行来实现。7大学计算机基础大学计算机基础昆明理工大学昆明理工大学6.2 6.2 算法及算法描述算法及算法描述.3算法的评价算法的评价算法除了其本身的可读性、正确性和健壮性的评价之外，算法除了其本身的可读性、正确性和健壮性的评价之外，可量化的评价指标主要是可量化的评价指标主要是时间复杂度时间复杂度

6、和和空间复杂度空间复杂度。8大学计算机基础大学计算机基础昆明理工大学昆明理工大学6.2 6.2 算法及算法描述算法及算法描述.3算法的评价算法的评价9时间复杂度时间复杂度：采用基本语句执行次数的数量级来近似描述。：采用基本语句执行次数的数量级来近似描述。 f(n) 是是 T(n) 的同数量级函数。的同数量级函数。把把 T(n) 表示成数量级的形式为：表示成数量级的形式为：T(n)=O(f(n)。(f(n) 为为算法的时间复杂度。算法的时间复杂度。比如比如 f(n) =n2 ，那么，那么T(n)=O(n2)100 1 2 4 8 16 32 64 128 256 nT(n)102

7、451225612864321684210 1 2 4 8 16 32 64 128 256 512 1024 nO(log2n) 常见常见的T(n)随n变化的增长率O(c)O(n)O(n*log2n)O(n2)O(n3)O(2n)随着问题规模时间的增长，期望时间杂度趋于稳定地上升随着问题规模时间的增长，期望时间杂度趋于稳定地上升,但上升幅度不能太大。但上升幅度不能太大。大学计算机基础大学计算机基础昆明理工大学昆明理工大学6.2 6.2 算法及算法描述算法及算法描述.3算法的评价算法的评价11空间复杂度空间复杂度：空间复杂度：算法所需存储空间的度量，记：空间复杂度：算法所需存储

8、空间的度量，记作：作：S(n)=O( f(n) ) ，其中，其中 n 为问题的规模。为问题的规模。一个算法所需存储空间一个算法所需存储空间 算法本身的存储空间算法本身的存储空间 输入数据的存储空间输入数据的存储空间 算法在运行过程中临时占用的存储空间算法在运行过程中临时占用的存储空间 大学计算机基础大学计算机基础昆明理工大学昆明理工大学6.2 6.2 算法及算法描述算法及算法描述6.2.4 6.2.4 算法的描述算法的描述12举例：盈亏问题的算法描述举例：盈亏问题的算法描述现有若干人合买某件商品，假设每人出现有若干人合买某件商品，假设每人出8元钱，买完商品后元钱，买完商品后还会盈余还会盈余3元

9、钱；假设每人出元钱；假设每人出7元钱，那么购买该商品还差元钱，那么购买该商品还差4元钱。求合买商品的人数和该商品的售价（元）。元钱。求合买商品的人数和该商品的售价（元）。古 法九章算术.盈不足今 法方程组联立大学计算机基础大学计算机基础昆明理工大学昆明理工大学6.2 6.2 算法及算法描述算法及算法描述6.2.4 6.2.4 算法的描述算法的描述Step 1：界定问题（整数解）Step 2：分析问题 （求解两个未知量，基于两次假设 ）Step 3：建模Step 4：分析模型建立算法13大学计算机基础大学计算机基础昆明理工大学昆明理工大学6.2 6.2 算法及算法描述算法及算法描述6.2.5 6

10、.2.5 算法的表示算法的表示流程图流程图大学计算机基础大学计算机基础昆明理工大学昆明理工大学6.2 6.2 算法及算法描述算法及算法描述6.2.5 6.2.5 算法的表示算法的表示- -盈不足流程图盈不足流程图大学计算机基础大学计算机基础昆明理工大学昆明理工大学6.2 6.2 算法及算法描述算法及算法描述6.2.5 6.2.5 算法的表示算法的表示- -伪代码伪代码伪代码（伪代码（pseudo codepseudo code）是算法的另外一种表示方法。伪代码也）是算法的另外一种表示方法。伪代码也叫虚拟代码，是一种由自然语言和没有限定的多种编程语言元叫虚拟代码，是一种由自然语言和没有限定的多种

11、编程语言元素混合而成。素混合而成。BEGIN(算法开始)READ n /输入n的值，例如输入5，则5！=54321IF （n=0 OR n=1） THEN t=1 /0!=1、1!=1作为特例ELSE tn /令t=n in-1 WHILE （i=1） tt*i ii-1 PRINT tEND(算法结束)大学计算机基础大学计算机基础昆明理工大学昆明理工大学6.3 6.3 程序设计语言与程序设计程序设计语言与程序设计.1程序设计语言程序设计语言17程序设计语言数据成分运算成分控制成分传输成分第第1代：机器语言代：机器语言第第2代：汇编语言代：汇编语言第第3代：高级语言代：高级语言

12、（面向过程、面向对象、（面向过程、面向对象、 专用语言）专用语言）第第4代：代：SQL、决策支持语言等、决策支持语言等第第5代：智能化语言、知识库语言等代：智能化语言、知识库语言等大学计算机基础大学计算机基础昆明理工大学昆明理工大学6.3 6.3 程序设计语言与程序设计程序设计语言与程序设计6.3.2 6.3.2 程序设计过程程序设计过程18大学计算机基础大学计算机基础昆明理工大学昆明理工大学6.4 6.4 程序设计方法程序设计方法6.4.1 6.4.1 结构化程序设计方法结构化程序设计方法19顺序顺序选择选择(分支分支)ABABp真假pA真循环循环pA假假真ABpG大学计算机基础大学计算机基

13、础昆明理工大学昆明理工大学6.4 6.4 程序设计方法程序设计方法6.4.2 6.4.2 面向对象程序设计方法面向对象程序设计方法面向对象的程序设计语言一般都含有三个方面的语法机制，面向对象的程序设计语言一般都含有三个方面的语法机制，即即对象和类、继承性、多态性对象和类、继承性、多态性。1对象对象(Obieot)对象是现实生活中的各种实体，具有属性、行为等特征。对象是现实生活中的各种实体，具有属性、行为等特征。2.类类(Class)类是创建对象实例的模板，对象是类的实例化。类的基本特性类是创建对象实例的模板，对象是类的实例化。类的基本特性是是封装性、继承性和多态性封装性、继承性和多态性。20大

14、学计算机基础大学计算机基础昆明理工大学昆明理工大学6.4 6.4 程序设计方法程序设计方法程序设计方法发展历程程序设计方法发展历程21大学计算机基础大学计算机基础昆明理工大学昆明理工大学计算思维计算思维2006年，卡内基.梅隆大学周以真教授提出了“计算思维”的概念。周教授认为：“计算思维涉及运用计算机科学的基础概念去求解问题、设计系统和理解人类的行为。计算思维涵盖了反映计算机科学广泛性的一系列思维活动。”2008年，ACM提出“计算思维”与计算机导论课程绑定。BCS提出欧洲行动纲领。6.5 6.5 计算思维能力的培养计算思维能力的培养大学计算机基础大学计算机基础昆明理工大学昆明理工大学1.计算思维理论远未成熟。2.计算思维一定是同其他学科交叉融合的。3.利用信息时代的特质，理解问题、解决问题是计算思维的核心所在、魅力所在。大学计算机基础大学计算机基础昆明理工大学昆明理工大学Jim GrayJim Gray人类科学发展范式人类科学发展范式1.1.科学的实证阶段科学的实证阶段 伽利略的天文观测，证实土星环伽利略的天文观测，证实土星环2.2.数学理论分析阶段数学理论分析阶段 牛顿定律、相对论牛顿定律、相对论3.3.计算模拟阶段计算模拟阶段 CAD