C语言程序设计基础电子教案 第3章 算法初步

第3章算法初步教案教学任务1.计算机求解问题的基本过程。2.算法的概念。3.描述算法的主要方法。4.常用算法。授课课时总时长：学时包括：课堂讲授学时；实训学习学时一、教学分析教学重点算法的描述方法和常见的算法设计教学难点抽象与具体、特殊与一般的辩证关系教学方法讲授法+导例教学二、教学基本内容（一）算法的基本概念算法是为解决某个特定问题而采取的准确而完整的方法和步骤，其中有个著名的公式：数据结构+算法=程序其中，数据结构是对数据的描述，也就是在程序中数据的类型和组织形式，而算法则是对操作步骤的描述。算法是程序设计的灵魂，是问题求解过程中的精确描述。学习C语言，不仅要熟练掌握C语言语法规则等，还要掌握分析问题、解决问题的方法。解决一个具体问题时通常有多种算法供选用，要对算法执行效率进行分析比较，再做选择。（二）算法的特性算法具有以下特性：（1）有穷性：算法中的每个步骤执行的次数及时间是有限的，即不能无限执行。（2）确定性：算法中的每条指令必须清楚严格地规定确切的含义，无二义性。（3）有效性：算法中描述的每个步骤都应能有效地执行，并得到确定的结果。（4）算法有零个或多个输入。（5）算法通常有一个或多个输出。（三）算法的描述方法算法可以用各种描述方法进行描述，历史上已经使用过的描述方法有自然语言、流程图、N-S图、伪代码和计算机语言程序5种。下面我们以计算1+2+3+…+100为例，使用不同的算法给予描述。（1）自然语言描述步骤1：i=1，sum=0；步骤2：如果i不大于100，顺序执行步骤3；否则，执行步骤5；步骤3：sum加上i，相加后的值仍放在sum中，即sum=sum+i；步骤4：使i的值增1得到下一个加数，即i=i+1；执行步骤2；步骤5：变量sum中的值就是所要得到的结果，输出结果，算法结束。此方法口语化，易懂，但不够直观、不利于编程。（2）流程图描述流程图直观地描述一个工作过程的具体步骤。用传统的流程图表示算法的优点是直观易懂、简单方便；缺点是传统流程图对于流程线的走向没有任何限制，可以任意转向，绘制流程图时费时费力且不易修改和阅读。（3）N-S图描述在这种流程图中，完全去掉了带箭头的流程线，全部算法写在一个矩形框内，在该框内还可以包含其它从属于它的框。用N-S图表示算法的优点是去掉了流程线，直观易懂，容易让学习者养成利用结构化方法构造算法的习惯，但修改流程图仍显麻烦。（4）伪代码描述（又称为类语言描述）伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。这种方法比较易于理解，但描述较冗长。（5）计算机语言程序描述另外，算法还可以使用计算机程序来描述。（四）问题求解的过程用计算机求解问题即用计算机程序解决问题。一个程序包括两方面的内容：数据与对数据的操作。程序中对处理数据的描述也就是程序要指定用到哪些数据及其相应的数据类型和组织形式。操作也就是计算机要进行处理的步骤，其实就是算法。用计算机解决一个问题时，实际上就是要确定：（1）确定问题中处理的数据，即操作的对象。分析这些操作对象的数据类型，用合适的组织形式来描述。（2）确定问题处理的流程。计算机处理问题有3种基本的流程，即顺序结构、选择结构、循环结构。对于选择结构来说，关键在于确定其分支的条件，以及满足该条件要进行的操作。如果确定一个问题的解决方法为循环结构，关键在于确定两方面：循环条件与循环体。任何一个循环结构从这两方面来入手分析，就可以确定解决问题的步骤。以3.1.1节导例为例，解决这个问题，首先分析处理的数据。在这个问题中涉及的数据包括所猜测价格的最低值与最高值、正确价格、猜测价格，这几个数据的类型都是整型；接下来分析问题的控制结构。解决这个问题采用的方法是取价格区间的中间值与正确价格比较，很显然这是一个循环结构，接下来再确定其循环体与循环条件，用流程图描述出来。（五）算法的要求与评价对一个算法的评价主要是对算法效率的衡量，从时间复杂度和空间复杂度来衡量。（1）时间复杂度：执行算法所需要的时间。（2）空间复杂度：执行算法需要消耗的最大内存空间。对于同一个问题，根据不同的算法写出的程序放在计算机上运行时，所需要的时间和空间是不同的，两者都与问题的规模有关。（六）结构化设计结构化程序设计是进行以模块功能和处理程序设计为主的详细设计的基本原则。它主要采用自顶向下、逐步求精及模块化的程序设计方法，任何程序都可由顺序、选择、循环三类基本控制结构构造。1.自顶向下程序设计时，首先考虑总体，再考虑细节；先考虑全局目标，后考虑局部目标。首先从最上层总目标开始设计，不要一开始就追求细节。2.逐步求精逐步精细化。对复杂问题，应设计一些子目标作为过渡，逐步细化。3.模块化设计：模块化就是把程序要解决的总目标分解为子目标，再进一步分解为具体的小目标，小目标又称为模块。为了使模块尽可能独立，要求模块内聚程度要尽量高，且模块间的耦合程度要尽量弱。4.结构化程序设计的三种基本结构（1）顺序结构顺序结构是最基本的构造结构，当执行由这些语句构成的程序时，按照这些语句在程序中的先后顺序执行，没有分支，没有转移，没有步骤之间的相互约束。（2）选择结构选择结构根据不同的条件去执行不同分支中的语句。（3）循环结构循环结构就是根据给定的条件，判断是否要重复执行某一相同的或类