C语言程序设计 第2章程序的灵魂--算法.ppt

C语言编程基础语言编程基础主讲：主讲：联系方式：联系方式：第三讲第三讲 程序的灵魂程序的灵魂算法算法 第三讲第三讲 算法算法 C语言编程基础语言编程基础回顾：回顾：回顾：回顾：什么是程序和编程语言什么是程序和编程语言什么是程序和编程语言什么是程序和编程语言程序的结构和上机步骤程序的结构和上机步骤程序的结构和上机步骤程序的结构和上机步骤目标：目标：目标：目标：1 1 1 1 理理理理解什么是算法，算法的特性解什么是算法，算法的特性解什么是算法，算法的特性解什么是算法，算法的特性2 2 2 2 简简简简单算法的举例单算法的举例单算法的举例单算法的举例3 3 3 3 了解描述一个算法了解描述一个算法了解描述一个算法了解描述一个算法的不同方法的不同方法的不同方法的不同方法4 4 4 4 掌握结构化程序设计方法掌握结构化程序设计方法掌握结构化程序设计方法掌握结构化程序设计方法 第三讲第三讲 目标目标 C语言编程基础语言编程基础算法引言算法引言第三讲算法引言第三讲算法引言完整的程序设计应该是:著名计算机科学家沃思提出一个公式数据结构算法程序设计方法语言工具数据结构算法程序设计方法语言工具数据结构算法数据结构算法=程序程序 C语言编程基础语言编程基础什么是算法什么是算法广义：广义：为解决一个问题而采用的方法和步骤为解决一个问题而采用的方法和步骤计算机算法：计算机算法：给定初始状态或输入数据，经给定初始状态或输入数据，经过计算机程序的有限次运算，能够得出所要过计算机程序的有限次运算，能够得出所要求或期望的终止状态或输出数据。包含数值求或期望的终止状态或输出数据。包含数值运算算法和非数值运算算法运算算法和非数值运算算法第三讲第三讲 什么是算法什么是算法 C语言编程基础语言编程基础算法的特性算法的特性第三讲第三讲 算法的特性算法的特性（1 1）有穷性：）有穷性：有限的操作步骤且在合理的范围内有限的操作步骤且在合理的范围内 （2 2）确定性：）确定性：算法的描述必须无歧义，以保证算法算法的描述必须无歧义，以保证算法的执行结果是确定的的执行结果是确定的。（3 3）有效性：）有效性：又称可行性，每个步骤都能有效地执又称可行性，每个步骤都能有效地执行，并得到确定的结果行，并得到确定的结果（4 4）输入：）输入：一个算法必须有零个或多个输入量一个算法必须有零个或多个输入量（5 5）输出：）输出：个算法应有一个或多个输出量个算法应有一个或多个输出量 C语言编程基础语言编程基础算法示例算法示例我我们们需需要要将将华华氏氏温温度度转转换换成成摄摄氏氏温温度度。完完成成这这个转换的算法如下：个转换的算法如下：第第一一步步：获获取取一一个个以以华华氏氏温温度度输输入入的的数数值值。让让我们称其为我们称其为 fahrenheitfahrenheit。第第 二二 步步：通通 过过 公公 式式 celsiuscelsius =5 5*(fahrenheitfahrenheit-32)/9 -32)/9 将之转化成摄氏温度值。将之转化成摄氏温度值。第三讲第三讲 算法示例算法示例 C语言编程基础语言编程基础有关各种类型算法的分类将帮助我们选择一个有关各种类型算法的分类将帮助我们选择一个合适的方法来评价一个算法的效率和正确性。合适的方法来评价一个算法的效率和正确性。我们可以将算法分为三类：我们可以将算法分为三类：有限的、确定性算法有限的、确定性算法 有限的、非确定性算法有限的、非确定性算法无限的算法无限的算法算法的种类算法的种类第三讲第三讲 算法种类算法种类 C语言编程基础语言编程基础有限的、确定性算法有限的、确定性算法第三讲第三讲 算法种类算法种类这类算法会在有限的一段时间内终止这类算法会在有限的一段时间内终止这类算法得出的结果常取决于输入值。如果输入已这类算法得出的结果常取决于输入值。如果输入已知，那么它们就可以得出确切的结果知，那么它们就可以得出确切的结果示例：示例：1 1 求二次方程式的根求二次方程式的根 2 2 求出求出 1 1 到到 1,000,000 1,000,000 之间的所有素数之间的所有素数 C语言编程基础语言编程基础有限的非确定性算法有限的非确定性算法第三讲第三讲 算法种类算法种类这些算法也会在有限时间内终止。然而，对于给定的输入，这些算法也会在有限时间内终止。然而，对于给定的输入，这种算法的结果可能并不是唯一的或确定的。这种算法的结果可能并不是唯一的或确定的。示例：请考虑用于生成随机数的算法。示例：请考虑用于生成随机数的算法。无限算法是那些由于没有定义终止条件，或定义的条件无法由无限算法是那些由于没有定义终止条件，或定义的条件无法由输入的数据满足而不终止运行的算法输入的数据满足而不终止运行的算法示例：监控核反应堆里的温度就是一个无限算法。只要反应堆示例：监控核反应堆里的温度就是一个无限算法。只要反应堆在运行，那么这个连续的任务就会一直进行下去。此任务会在运行，那么这个连续的任务就会一直进行下去。此任务会一直运行，直至有一个外部刺激来停止它。一直运行，直至有一个外部刺激来停止它。无限算法无限算法 C语言编程基础语言编程基础算法的设计要求算法的设计要求第二章第二章 2.2 2.2 常量和变量常量和变量 正确性、正确性、可读性、可读性、健壮性、健壮性、效率与效率与低存储低存储量需求量需求;C语言编程基础语言编程基础算法的描述算法的描述自然语言自然语言日常使用的语言（通俗易懂，日常使用的语言（通俗易懂，但文字冗长，容易出现但文字冗长，容易出现“歧义性歧义性”）流流程程图图（传传统统的的流流程程图图、改改进进的的流流程程图、图、N-SN-S流程图）流程图）伪代码第三讲第三讲 算法描述算法描述计算机语言可以用不同的方法描述算法，常用的有：可以用不同的方法描述算法，常用的有：C语言编程基础语言编程基础流程图表示算法流程图表示算法第三讲第三讲 流程图流程图流程图用规定式样的图形、指向线和文字组合起来表示算流程图用规定式样的图形、指向线和文字组合起来表示算法其优点是直观、清晰、易懂，便于检查、修改和交法其优点是直观、清晰、易懂，便于检查、修改和交流流ANSIANSI规定了一些常用的流程图符号：规定了一些常用的流程图符号：起止框起止框判断框判断框处理框处理框输入输入/输出框输出框注释框注释框流向线流向线连接点连接点 C语言编程基础语言编程基础传统的流程图传统的流程图例例1 将求将求5!的算法用流程图表示的算法用流程图表示如果需要将最后结果打如果需要将最后结果打印出来，可在菱形框的印出来，可在菱形框的下面加一个输出框下面加一个输出框 C语言编程基础语言编程基础 例例2 将判定闰年将判定闰年的算法用流程的算法用流程图表示图表示 用流程图表示算法要比用文字描述算法逻辑清晰、易于理解。C语言编程基础语言编程基础第三讲第三讲 流程图流程图小结小结流程图是表示算法的较好的工具。一个流程图是表示算法的较好的工具。一个流程图包括以下几部分流程图包括以下几部分 ：(1)(1)表示相应操作的框；表示相应操作的框；(2)(2)带箭头的流程线；带箭头的流程线；(3)(3)框内外必要的文字说明。框内外必要的文字说明。C语言编程基础语言编程基础第三讲第三讲 流程图流程图三种基本结构和改进的流程图三种基本结构和改进的流程图1.1.传统流程图的弊端传统流程图的弊端 传统流程图用流程线指出各框的执行顺序，传统流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制。因此，使用者可对流程线的使用没有严格限制。因此，使用者可以毫不受限制地使流程随意地转向，使流程图变以毫不受限制地使流程随意地转向，使流程图变得毫无规律，阅读者要花很大精力去追踪流程，得毫无规律，阅读者要花很大精力去追踪流程，使人难以理解算法的逻辑。如图：使人难以理解算法的逻辑。如图：C语言编程基础语言编程基础第三讲第三讲 流程图流程图传统流程图的流程可以是：传统流程图的流程可以是：这种如同乱麻一样的算法称为这种如同乱麻一样的算法称为BSBS型算法，意为一碗面型算法，意为一碗面条条(A Bowl of Spaghetti)(A Bowl of Spaghetti)，乱无头绪。乱无头绪。缺点：难以阅读、修改，使算法的可靠性和可维护性难以保证。解决办法：必须限制箭头的滥用，即不允许无规律地使流程随意转向，只能顺序地进行下去。C语言编程基础语言编程基础算法的两大要素算法的两大要素算术运算、逻辑运算、算术运算、逻辑运算、函数运算等等；函数运算等等；控制结构控制着算法控制结构控制着算法的各操作的执行顺序的各操作的执行顺序控制结构第三讲第三讲 算法结构算法结构操作操作 C语言编程基础语言编程基础第三讲第三讲 算法结构算法结构基本控制结构基本控制结构通常一个算法只能由三种基本控制结构组成，这三种通常一个算法只能由三种基本控制结构组成，这三种基本结构是：基本结构是：顺序结构顺序结构;选择结构选择结构;循环结构循环结构;C语言编程基础语言编程基础第三讲第三讲 算法结构算法结构顺序结构：顺序结构：根据条件的不同，有选择性的执行代码根据条件的不同，有选择性的执行代码按照书写顺序依次执行选择结构：选择结构：根据条件，重复执行一些代码根据条件，重复执行一些代码循环结构：循环结构：C语言编程基础语言编程基础第三讲第三讲 算法结构算法结构三种基本结构的流程图：三种基本结构的流程图：三种基本结构的流程图：三种基本结构的流程图：顺序结构顺序结构选择结构选择结构 C语言编程基础语言编程基础第三讲第三讲 算法结构算法结构三种基本结构的流程图：三种基本结构的流程图：三种基本结构的流程图：三种基本结构的流程图：当型当型(While型型)循环结构循环结构 直到型直到型(Until型型)循环循环 C语言编程基础语言编程基础改进的流程图表示算法示例改进的流程图表示算法示例3 C语言编程基础语言编程基础第三讲第三讲 N-SN-S流程图流程图用用N-SN-S流程图表示算法流程图表示算法 19731973年美国学者年美国学者I.NassiI.Nassi和和B.ShneidermanB.Shneiderman提出了一种新的流程图形式。在这种流程图提出了一种新的流程图形式。在这种流程图中，完全去掉了带箭头的流程线。全部算法中，完全去掉了带箭头的流程线。全部算法写在一个矩形框内，在该框内还可以包含其写在一个矩形框内，在该框内还可以包含其它的从属于它的框，或者说，由一些基本的它的从属于它的框，或者说，由一些基本的框组成一个大的框。这种流程图又称框组成一个大的框。这种流程图又称N-SN-S结结构化流程图。构化流程图。C语言编程基础语言编程基础 N-SN-S流程图用以下的流程图符号：流程图用以下的流程图符号：(1)顺序结构(2)选择结构(3)循环结构 C语言编程基础语言编程基础N-SN-S流程图与改进流程图对比：流程图与改进流程图对比：C语言编程基础语言编程基础N-SN-S流程图与改进流程图对比：流程图与改进流程图对比：C语言编程基础语言编程基础例例4 将例将例1的传统流程图改画为的传统流程图改画为 N-S 流程图流程图 C语言编程基础语言编程基础例例5 5 将例将例3 3的改进流程图改为的改进流程图改为N-S N-S 流程图流程图 C语言编程基础语言编程基础用伪代码表示算法用伪代码表示算法概念：概念：伪代码是用介于自然语言和计算机语言之伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。间的文字和符号来描述算法。特点：特点：它如同一篇文章一样它如同一篇文章一样 ，自上而下地写下，自上而下地写下来。每一行来。每一行(或几行或几行)表示一个基本操作。它不用表示一个基本操作。它不用图形符号，因此书写方便图形符号，因此书写方便 、格式紧凑，也比较、格式紧凑，也比较好懂，也便于向计算机语言算法好懂，也便于向计算机语言算法(即程序即程序)过渡。过渡。用处：用处：适用于设计过程中需要反复修改时的流程适用于设计过程中需要反复修改时的流程描述。描述。C语言编程基础语言编程基础用计算机语言表示算法用计算机语言表示算法概念：概念：用计算机实现算法。计算机是无法识别流用计算机实现算法。计算机是无法识别流程图和伪代码的。只有用计算机语言编写的程序程图和伪代码的。只有用计算机语言编写的程序才能被计算机执行。因此在用流程图或伪代码描才能被计算机执行。因此在用流程图或伪代码描述出一个算法后，还要将它转换成计算机语言程述出一个算法后，还要将它转换成计算机语言程序。序。特点：特点：用计算机语言表示算法必须严格遵循所用用计算机语言表示算法必须严格遵循所用的语言的语法规则，这是和伪代码不同的。的语言的语法规则，这是和伪代码不同的。用处：用处：要完成一件工作，包括设计算法和实现算要完成一件工作，包括设计算法和实现算法两个部分。设计算法的目的是为了实现算法。法两个部分。设计算法的目的是为了实现算法。C语言编程基础语言编程基础#include void main()int i,t;t=1;i=2;while(i=5)t=t*i;i=i+1;printf(%dn,t);例例6 将例将例4用流程图表示的用流程图表示的算法（求算法（求5!）用）用C语言表语言表示。示。C语言编程基础语言编程基础应当强调说明：应当强调说明：写出了写出了C C程序，仍然只是程序，仍然只是描述了算法，并未实现算法。只有运行程描述了算法，并未实现算法。只有运行程序才是实现算法。应该说，用计算机语言序才是实现算法。应该说，用计算机语言表示的算法是计算机能够执行的算法。表示的算法是计算机能够执行的算法。