算法和程序设计复习.doc

教案： 算法和程序设计复习 学校：上海市市南中学 授课年级：高一年级 执教：蒋 钦 教学目标 知识与技能： 1、复习使用计算机解决问题的一般过程、一个程序组成部分、算法的概念及特征、算法的表示方法、变量和变量的用途、算法的执行流程； 2、复习枚举算法、解析算法、排序算法、查找算法、递推算法。 教学重点 　　知识要点的梳理。 第一章 算法和算法的表示 [知识要点] 使用计算机解决问题的一般过程： 分析问题→设计算法→编写程序→运行程序获得问题的解 一个程序由如下两部分组成： 1）指令部分：由一系列的指令构成，每条指令都是要求计算机执行的一个动作。由适当的指令构成的一个序列，描述了解决这个问题的计算过程。 2）数据部分：用来存贮计算所需的原始数据、计算的中间结果或最终结果。 算法的概念 用计算机解题前，需要将解题方法转换成一系列具体的、在计算机上可执行的步骤，这些步骤能清楚地反映解题方法一步步“怎样做”的过程，这个过程就是通常所说的算法。 一个算法应该具有如下的特征： 有穷性。一个算法必须保证在有限个操作步骤执行后终止，即，操作步骤不能是无限的。 确定性。算法中的每个步骤必须有确切的含义，而不应当是含糊的、模棱两可的。 能行性。算法中的每一个步骤都要足够简单，是实际能做的，而且能在有限的时间内完成。 有0个或多个输入。所谓输入是指算法在执行时需要从外界取得信息，其目的是为算法的某些阶段建立初始状态。如果建立初始状态所需的信息已经包含在算法中了，那就不再需要输入。 有一个或多个输出。算法的目的是用来求解问题，问题解决的结果应以一定的方式输出。 算法的表示 1）流程图(flowchart)是一种比较直观易用的、用图形来描述算法的方法。 被普遍使用的《信息处理用流程图符号标准》是由美国国家标准化学会(ANSI)制定的，这套标准中最基本、最常用的成分有： ①处理框(矩形框)：框中指出要处理的内容，该框有一个入口和一个出口。 ②判断框(菱形框)：用来表示分支情况，菱形框的四个顶点中，通常用上面的顶点表示入口，视需要用其余两个顶点来表示出口。 ③连接框(圆形框)：用于连接因画不下而断开的流程线。 ④流程线(有向线段)：指出流程控制方向，即，动作的次序。 ⑤开始、结束符(椭圆框)：用来表示算法的开始和结束。一个算法只能有一个开始处，但可以有多个结束处。 2）使用自然语言，例如汉语，加上一些必要的数学符号，来描述解决问题的算法。自然语言的主要缺点是有时会存在二义性 3）用“伪代码”(pseudo code)来描述算法。伪代码使用某些程序设计语言中的控制结构，来描述算法中各步骤的执行次序和模式，使用自然语言、数学符号或其他符号，来表示计算步骤要完成的处理或需要涉及的数据。使用伪代码可以免去许多绘图的麻烦，但前提是必须熟悉某种程序设计语言。 变量和变量的用途 程序中的变量是计算过程中要用到的数据的存贮单元，通过输入指令的执行，程序将外界输入的数据存贮到指定的变量中，程序计算的结果也可以存贮到指定的变量中。 1）计数器(counter) 算法执行过程中，用来记录某种事件发生次数的变量。假定变量c作为计数器。 计数器的典型用法： a.在算法执行的准备阶段中，应预置初值0。向计数器c预置初值0的动作为： c ← 0。 b.算法执行过程中，每当指定的事件发生时，对计数器c计数， 即，把事件已经发生的次数(在计数器c中)加1后，结果仍然送回到计数器c中。 计数器c的计数动作为: c ← c+1。 2)累加器(accumulator) 算法执行过程中，用来形成并存贮数据之和的变量。假定变量sum作为累加器，变量d中存贮了符合要求的一个数据。 累加器的典型用法： a.在求和开始前的准备阶段中，应预置初值0。向累加器sum预置初值0的动作为：sum ← 0。 b.算法执行过程中，每遇到一个符合要求的数据时，把这个数据累加到累加器中，即，计算累加器与该数据之和，并把结果重新存贮到累加器中。数据d累加到sum的动作为：sum ← sum + d。 算法的执行流程 1).顺序模式：执行完一个处理步骤step1后，接着执行下一个处理步骤step2。 2).选择模式：对某个情况e进行判断，当结果为真时，执行处理步骤step1，否则执行处理步骤step2。选择模式使算法能根据情况的不同，在准备好的两个处理步骤中，选择执行一个适当的处理步骤。 3).重复模式：对某个情况e进行判断，当结果为真时，执行处理步骤step，然后再次判断这个情况e，当结果为真时，再次执行处理步骤step，并继续判断情况e。总是重复上述过程，直到情况判断的结果为假。 这三种不同的流程模式通常会被组合起来使用，以表示各种较为的复杂问题的算法。 第二章 算法实例 [知识要点]