程式设计课件.pptVIP

第2章 算法设计基础 2.1 算法的描述 2.2 结构化算法设计初步 2.3 算法的计算复杂性 2.4 常用算法设计策略 2.1 算法的描述 2.1.1 自然语言方式 2.1.2 伪代码方式 2.1.3 程序流程图方式 2.1.4 N/S盒图方式 2.1.5 PAD图方式 2.1.1 自然语言方式 2.1.2 伪代码方式 预先规定了描述规则和关键词，以接近某程序设计语言的风格描述算法。同时具有易理解和趋于形式化的优点。 2.1.3 程序流程图方式 算法由若干张流程图描述，每张流程图由结点和有向边构成，该图描述了算法中所进行的操作以及这些操作执行的逻辑顺序。 流程图的常用结点及控制结构描述如下 ： 2.1.3 程序流程图方式 2.1.4改进的流程图-N/S流程图 略 2.1.5 PAD图（Problem Analysis Diagram）方式 PAD图结点与控制结构描述 2.1.5 PAD图方式 2.2 结构化算法设计初步 2.2.1 算法描述 2.2.2 算法设计 2.2.1 算法描述 1. 结构化算法的流程图 2.2.1 算法描述 1. 结构化算法的流程图 2.2.1 算法描述 2. 结构化算法的PAD图 2.2.2 算法设计 2.2.2 算法设计 1. 主体结构设计 2.2.2 算法设计 2. 顺序结构设计 2.2.2 算法设计 3. 选择结构设计------双分支结构 2.2.2 算法设计 3. 选择结构设计------双分支结构 2.2.2 算法设计 3. 选择结构设计------多分支结构 2.2.2 算法设计 3. 循环结构设计 思考题 [例] 将变量a, b的值互换 思考题 求任意正整数的累加和，即1+2+3+…+n 算法输入： 正整数n 算法输出： 1+2+3+…+n 注意：如果用户输入的n不是正数，则算法终止。 分别画出 流程图 和 PAD图 递归技术 一种以有限方式描述规模任意大问题的方法 递归技术 为求圆柱的侧面积，首先应该求圆柱的底面周长； 为求圆柱的体积，首先应该求圆柱的底面积。 显然，算法的结构为上到下顺序排列的模块， 每个模块的功能相对独立，由一些操作组成， 算法的执行顺序显然就是上述模块的物理排列顺序。 学习目的： ① 掌握算法的流程图和PAD图描述方式； ② 初步掌握结构化算法设计； ③ 能够进行简单的算法复杂性分析； ④ 初步了解分治与递归。 算法的描述方式很多，不同描述风格适用于不同场合，在面向对象技术出现之前，人们倾向于在算法的描述中对未来程序的层次结构进行一定程度的控制，而不仅仅是描述具体的数据处理过程。本节介绍算法的常见描述方法。 算法表示如下： S1：输入n的值 S2：2 ?i ( i 作为除数） S3: n 被 i 除，得余数 r S4: 如果 r 等于 0 ， 表示 n 能 被 i 整除，则打印 n “不是素数”，算法结束；否则执行S5 S5：i+1 ?i S6: 如果 i ? n-1, 返回S3；否则，打印 n “是素数”，算法结束。 例1：对一个大于或等于3的正整数，判断它是不是一个素数 方法：将 n (其中n ?3) 作为被除数， 将2 到（n-1) 各个整数轮流作为除数，如果都不能被整除，则n为素数。 Begin input n 2 ?i while（i ? n-1）{ n mod i ?r if(0=r) output n is not Prime； exit //退出循环 i+1 ?i } if（i=n）output n is Prime End 此地用到了循环结构 循环结构 或 是 条件 否 处理 当型循环 条件 处理 否 是 直到循环 端点符 处理 判断 预定义功能 连接符 条件 处理1 处理2 选择结构 处理1 处理2 顺序结构 流程线 开始 输入n的值 i=n-1 i=2 r=n % i r= =0 Y N i=i+1 输出 n 不是素数 输出 n 是素数 结束 Y N 此地都可采用平行四边形框 输入和输出时可采用该框 b 选择结构 d 循环结构 c 多选择结构 a 顺序结构 P1 P2 C P1 P2 Pn L1 L2 X=… Ln P A 或 while c until c P1 P2 输入输出 重复 子算法 定义 选择 语句标号 处理 i=n-1 n 算法开始 算