第2章算法及其描述

1、第二章第二章 算法及其描述算法及其描述n教学目的：教学目的：通过本章的学习，要求能理解算法的概念通过本章的学习，要求能理解算法的概念和算法的特性，能熟练使用程序流程图或和算法的特性，能熟练使用程序流程图或n-s流程图描述程序的设计步骤和方法，学习程序流程图描述程序的设计步骤和方法，学习程序设计的算法及其描述之后，为编写高质量的程设计的算法及其描述之后，为编写高质量的程序奠定基础。序奠定基础。第二章第二章 算法及其描述算法及其描述 n教学内容教学内容算法的概念算法的概念算法引例算法引例算法的特性算法的特性算法的描述算法的描述结构化程序设计方法结构化程序设计方法n重点重点:(1)理解算法的概念理解

2、算法的概念(2)熟悉算法的特性熟悉算法的特性 (3)熟练运用算法的描述方法熟练运用算法的描述方法 (4)掌握结构化程序设计方法掌握结构化程序设计方法 (1)算法的描述方法算法的描述方法 n难点难点:(2)结构化程序设计方法结构化程序设计方法 第二章第二章 程序设计的算法及其描述程序设计的算法及其描述 n求解问题的步骤求解问题的步骤 （1 1）分析问题。）分析问题。 （2）算法分析。）算法分析。 （3）程序设计。）程序设计。 （4）程序调试。）程序调试。 （5）运行与维护。）运行与维护。 2.1 2.1 算法的概念算法的概念算法（算法（algorithmalgorithm）: :简单地说，算法是

3、为解决一个简单地说，算法是为解决一个特定问题而采取的确定的、有限的方法和步骤。特定问题而采取的确定的、有限的方法和步骤。 计算机算法分为两类：一类是数值计算算法，另一计算机算法分为两类：一类是数值计算算法，另一类是非数值计算算法。类是非数值计算算法。 【例【例2-12-1】求解一个一元二次方程】求解一个一元二次方程 第一步：将方程化简为标准方程。即：第一步：将方程化简为标准方程。即：axax2 2+bx+c=0 +bx+c=0 利用利用 它的值来判断方程无解、有一个解或有两它的值来判断方程无解、有一个解或有两个解。个解。第二步：如果第二步：如果 b b2 2-4ac0 -4ac0-4ac0此题

4、有两个解此题有两个解 . .第五步：解题结束。第五步：解题结束。2.2 2.2 算法引例算法引例【例【例2-22-2】输入】输入1010个整数，求出其中的最大值。个整数，求出其中的最大值。 取最小整数取最小整数-32768-32768为最大值，并把它放在变量为最大值，并把它放在变量maxmax中。中。计数器的值置计数器的值置0 0。输入一个整数输入一个整数x x，且计数器加，且计数器加1 1。若若x x大于大于maxmax，则将，则将x x的值赋给的值赋给maxmax；否则；否则maxmax的值不变。的值不变。 若计数器的值小于若计数器的值小于1010，则重新执行第，则重新执行第3 3步步 第

5、第5 5步；否则执行第步；否则执行第6 6步。步。输出最大值输出最大值maxmax。(7) (7) 算法结束算法结束. .【例【例2-32-3】输入】输入1010个整数，求出其中的最大值。个整数，求出其中的最大值。(c(c语言语言) )# include # include void main ( )void main ( ) int max = -32768, i, x = 0;int max = -32768, i, x = 0;for ( i = 0; i 10 ; i +)for ( i = 0; i max )if ( x max )max = x;max = x; printf (

6、 printf ( 最大值最大值 max = %dn, max );max = %dn, max );2.3 2.3 算法的特性算法的特性（1 1）有穷性。）有穷性。 （2 2）确定性。）确定性。 （3 3）可行性。）可行性。 （4 4）输入。）输入。 （5 5）输出。）输出。 （1 1）自然语言）自然语言（2）框图语言）框图语言用人们日常使用的语言来描述算法，称为算法的自然用人们日常使用的语言来描述算法，称为算法的自然语言描述法。语言描述法。 2.4 2.4 算法的描述算法的描述框图语言是用一些特殊符号来描述算法流程的语言。框图语言是用一些特殊符号来描述算法流程的语言。 （3）n-s 框图语

7、言框图语言（4）伪代码）伪代码 （5）计算机语言）计算机语言 用一个矩形框来描述一个独立功能的算法，称为用一个矩形框来描述一个独立功能的算法，称为n-s 框图语言描述法。框图语言描述法。 伪代码是用介于自然语言和计算机语言之间的文字伪代码是用介于自然语言和计算机语言之间的文字符号来描述算法符号来描述算法 .计算机语言描述方法是直接用计算机高级语言书写计算机语言描述方法是直接用计算机高级语言书写算法算法 2.5 2.5 结构化程序设计方法结构化程序设计方法n1 自顶向下自顶向下n2 逐步细化逐步细化n3 模块化设计模块化设计n4 结构化编码结构化编码算法就是为解决一个具体的问题而使用的确定算法就

8、是为解决一个具体的问题而使用的确定的、有限的方法和步骤。的、有限的方法和步骤。在选择算法的描述方法时，要注意以下几个方在选择算法的描述方法时，要注意以下几个方面：面：遵循行业惯例和软件人员使用的普遍性，使其遵循行业惯例和软件人员使用的普遍性，使其易于学习和交流。易于学习和交流。易于表达逻辑条件及其相应的处易于表达逻辑条件及其相应的处理，能有效地表达各种数据类型和数据结构。使算法理，能有效地表达各种数据类型和数据结构。使算法结构清晰，思路明了，无他义性。结构清晰，思路明了，无他义性。便于转换成机器便于转换成机器能接受的代码，易于进行逻辑验证和便于修改。能接受的代码，易于进行逻辑验证和便于修改。使使用三种基本结构设计算法。使功能尽量独立化。提高用三种基本结构设计算法。使功能尽量独立化。提高算法的可靠性和可维护性。算法的可靠性和可维护性。小结小结习题习题: :1.1.简述算法的概念。简述算法的概念。2.2.算法应具备哪些特性？算法应具备哪些特性？3.3.分别说明什么是自然语言描述法？什么是分别说明什么是自然语言描述法？什么是框图语言描述法？什么是伪语言描述法？框图语言描述法？什么是伪语言描述法？什么是