烟台大学：《大学计算机基础》课程教学课件（理论讲稿）第10章 问题求解的算法基础与程序设计

第10章问题求解的算法基础与程序设计10.1计算机求解问题过程10.2算法的概念10.3算法的分类、特性和评价方法10.4算法的三种结构10.5算法的表示10.6算法的发现10.7算法举例10.8程序设计基础

第10章 问题求解的算法基础 与程序设计 10.1 计算机求解问题过程 10.2 算法的概念 10.3 算法的分类、特性和评价方法 10.4 算法的三种结构 10.5 算法的表示 10.6 算法的发现 10.7 算法举例 10.8 程序设计基础

10.1计算机求解问题过程分析问题当拿到问题之后，我们不能马上就动手编程，而是要经历一个思考、设计、编程以及调试的过程，编写程序解决问题的建立模型过程一般包括5个步骤。(1)分析问题，即确定计算机要做什么实现自然语言的逻辑建模设计算法(2)建立模型，即将原始问题转化为数学模型编写程序(3)设计算法，即形式化地描述解决问题的途径和方法。(4)编写程序，即将算法翻译成计算机程序。调试测试程序(5)调试测试，即发现和修改程序运行过程中存在的错误图9-1问题求解过程图

10.1 计算机求解问题过程  当拿到问题之后，我们不能马上就动手编程，而是要经历一 个思考、设计、编程以及调试的过程，编写程序解决问题的 过程一般包括5个步骤。 (1)分析问题，即确定计算机要做什么,实现自然语言的逻辑建模。 (2)建立模型，即将原始问题转化为数学模型。 (3)设计算法，即形式化地描述解决问题的途径和方法。 (4)编写程序，即将算法翻译成计算机程序。 (5)调试测试，即发现和修改程序运行过程中存在的错误

10.2算法的概念简单地说，算法就是解决问题的一系列步骤。广义地说，为解决问题而采用的方法和步骤就是算法。算法是程序设计的基础，算法的质量直接影响程序运行的效率。程序是与机器兼容的算法的实现，在软件开发中，核心工作就是进行算法的设计算法是求解问题步骤的有序集合，它能够产生结果并在有限时间内结束

10.2 算法的概念  简单地说，算法就是解决问题的一系列步骤。广义 地说，为解决问题而采用的方法和步骤就是算法。 算法是程序设计的基础，算法的质量直接影响程序 运行的效率。程序是与机器兼容的算法的实现，在 软件开发中，核心工作就是进行算法的设计。  算法是求解问题步骤的有序集合，它能够产生结果 并在有限时间内结束

举一个简单的算法例子，假设求两个自然数m和n的最大公约数，通常使用辗转相除的欧几里得算法，算法描述如下：①对于已知两数m、n，使得m>n。②m除以n得到余数r。③若r=0，则n即为最大公约数，算法结束；否则继续进行下一步④令m一n，n一r，转到第②步。，以上算法描述了求解两个自然数中最大公约数的解题步骤，经过多次辗转相除，总会达到余数为0的情况，所以说算法会在有限步骤、有限时间内完成，并能输出相应结果

 举一个简单的算法例子，假设求两个自然数m和n的最大公约 数，通常使用辗转相除的欧几里得算法，算法描述如下: ①对于已知两数m、n，使得m>n。 ②m除以n得到余数r。 ③若r=0，则n即为最大公约数，算法结束；否则继续进行下一步。 ④令m←n，n←r，转到第②步。  以上算法描述了求解两个自然数中最大公约数的解题步骤，经 过多次辗转相除，总会达到余数为0的情况，所以说算法会在 有限步骤、有限时间内完成，并能输出相应结果

10.3算法的分类、特性和评价方法IN10.3.1算法的分类10.3.2算法的特性10.3.3算法的评价方法

10.3 算法的分类、特性和评价方法 10.3.1算法的分类 10.3.2算法的特性 10.3.3算法的评价方法

10.3.1算法的分类算法的分类方法有许多种，按照算法所涉及的对象，一般可以把算法分成两大类：数值运算算法和非数值运算算法。数值运算算法的目的是对数值进行求解，其特点是少量的输入、输出，复杂的运算。非数值运算算法的目的是对数据进行管理，其特点是大量的输入、输出，简单的算术运算和大量的逻辑运算

10.3.1算法的分类  算法的分类方法有许多种，按照算法所涉及的对象，一般可 以把算法分成两大类：数值运算算法和非数值运算算法。  数值运算算法的目的是对数值进行求解，其特点是少量的输 入、输出，复杂的运算。  非数值运算算法的目的是对数据进行管理，其特点是大量的 输入、输出，简单的算术运算和大量的逻辑运算

10.3.2算法的特性一般地，算法应该具有以下特性。L(1)确定性。一个算法中的每一个步骤必须是精确的定义、无二义性，不会使编程者对算法中的描述产生不同的理解。(2)有穷性。一个算法必须在执行有穷步后结束，每一步必须在有穷的时间内完成。(3)可行性。算法描述的步骤在计算机上是可行的，能在一个合理的范围内有效地执行，并应能得到一个明确的结果(4)输入：一般有零个或多个输入值。(5)输出：，一个算法的执行过程中或结束后要有输出结果，或者产生相应的动作指令

10.3.2算法的特性  一般地，算法应该具有以下特性。 (1)确定性。一个算法中的每一个步骤必须是精确的定义、无二 义性，不会使编程者对算法中的描述产生不同的理解。 (2)有穷性。一个算法必须在执行有穷步后结束，每一步必须在 有穷的时间内完成。 (3)可行性。算法描述的步骤在计算机上是可行的，能在一个合 理的范围内有效地执行，并应能得到一个明确的结果。 (4)输入：一般有零个或多个输入值。 (5)输出：一个算法的执行过程中或结束后要有输出结果，或者 产生相应的动作指令

10.3.3算法的评价方法算法的正确性可读性2健壮性3.高效率和低存储量

10.3.3算法的评价方法 1．算法的正确性 2．可读性 3．健壮性 4．高效率和低存储量

10.4 算法的三种结构10.4.1顺序结构10.4.2分支结构10.4.3循环结构

10.4 算法的三种结构 10.4.1顺序结构 10.4.2分支结构 10.4.3循环结构

结构化程序设计思想包含两个方面的内容，一是程序由三种基本的逻辑结构组成，二是程序设计要自顶向下进行。三种结构分别是顺序、分支和循环。其中分支也称选择或判断。算法是程序的基础，程序是算法的实现。因此程序的逻辑结构也就是进行算法设计的三种结构

 结构化程序设计思想包含两个方面的内容，一是程 序由三种基本的逻辑结构组成，二是程序设计要自 顶向下进行。  三种结构分别是顺序、分支和循环。其中分支也称 选择或判断。  算法是程序的基础，程序是算法的实现。因此程序 的逻辑结构也就是进行算法设计的三种结构