高级算法设计与第一章分析报告.ppt

（3）健壮性 算法的异常情况。处理出错的方法是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。 （4）高效率与低存储量需求 效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间。 6.算法设计的基本方法 （1）结构化方法——“自顶向下, 逐步求精” “自顶向下”是将复杂、大的问题划分为小问题。 “逐步求精”是将现实世界的问题经抽象转化为逻辑空间或求解空间的问题。 结构算法设计技术的优越性： ① 符合人类解决复杂问题的普遍规律。 ② 用先全局后局部、先整体后细节、先抽象后具体的逐步求精过程开发出的算法有清晰的层次结构。 （2)面向对象方法 对象=数据+对数据操作的代码实体 该方法的过程包括以下步骤： ① 在给定的抽象层次上识别类和对象 ② 识别这些对象和类的语义 ③ 识别类和对象之间的关系 ④ 实现类和对象 它的特征主要包括: 抽象化 将各种独立的操作分解成为可以用命名区分的单元。 封装性 不同的操作具有不同的作用范围。 多态性 对于不同数据类型的相似操作使用相同的名。 继承性 类可以被继承。 （3）课程采用结构化设计方法 自顶向下模块化分解过程　 ① 把一个较大的算法划分为若干子算法 ② 每一个模块可继续划分为更小的子模块 ③ 直到用三种控制结构和具体操作表示算法 注：运用这种编程方法，考虑问题必须先进行整体分析。 模块划分的基本要求 ① 模块的功能尽可能地单一化、明确化 ② 模块间的联系及相互影响尽可能地小 ③ 模块的规模应当足够小，以便于调试 原则是简单性、独立性和完整性（低耦合、高内聚） 模块间的接口问题 传递方式一般有以下几种： ①按名共享：全局变量 ②子模块返回调用模块信息：子模块名 ③调用模块传递给子模块信息：值参数传递 ④调用模块与子模块互相传递信息：变量参数传递(C语言没有此种传递方,Pascal、C++语言提供此类参数) ⑤按地址共享变量：地址参数传递（参数为指针变量名、数组名，变量地址） 算法设计的基本方法 抽象 抽象包括算法的抽象和数据抽象。算法抽象是指算法的寻求(或开发)采用逐步求精、逐层分解的方法。数据抽象也指在算法抽象的过程中逐步完善数据结构和引入新的数据及确定关于数据的操作。 枚举 “枚举”一些真实数据 归纳 “归纳”出算法的细节 7.从算法到实现 从算法到实现应注意的事项： 数据类型的选择 计算过程 整除、优先级 结果的输出格式 对齐、空行、空格、特定的分隔符等 算法实现后的测试、调试（回归测试） 三、算法描述 算法是对解题过程的精确描述。 算法 = 控制结构 + 原操作 表示算法的语言主要有：自然语言、流程图、伪代码、计算机算法设计语言等。 1.自然语言 自然语言是人们日常所用的语言。其缺点是： ① 由于自然语言的歧义性容易导致算法执行的不确定性。 ② 自然语言的语句一般太长从而导致了用自然语言描述的算法太长。 ③ 当一个算法中循环和分支较多时就很难清晰地表示出来。 ④ 自然语言表示的算法不便翻译成计算机算法设计语言理解的语言。 2．流程图 流程图可以表示任何算法的逻辑结构。 1) 基本组件 算法入口 加工 输入 条件 控制流 连接点 和出口 处理 输出 2）三种基本控制结构 ① 顺序结构： ② 选择结构 IF THEN ELSE型分支 DO CASE型多分支 ③ 循环结构 DO ─ DO WHILE型循环 DO UNTIL循环结构 3) 算法流程图的主要缺点 ① 不是逐步求精的好工具，它诱使算法员过早地考虑算法的控制流程，而不去考虑算法的全局结构。 ② 随意性太强，结构化不明显。 ③ 不易表示数据结构。 ④ 流程图的层次感不明显 3．盒图（NS流程图） （1）盒图具有以下优点： ① 层次感强、嵌套明确 ② 支持自顶向下、逐步求精。 ③ 容易转换成高级语言源算法 * 参考程序： #includestdio.h int main() { int nCase,nFeet,i; scanf(%d,nCase); for(i=1;i=nCase;i++) { scanf(%d,nFeet); if(nFeet%2 != 0) printf(0 0\n); el