《幼儿教育22213》由会员分享，可在线阅读，更多相关《幼儿教育22213（73页珍藏版）》请在金锄头文库上搜索。
1、目 录前言第一篇 引入篇第一章 算法概述第二章 算法分析基础第二篇 基础篇第三章 算法基本工具和优化技巧第三篇 核心篇第四章 基本的算法策略第五章 图的搜索算法第四篇 应用篇第六章 算法设计实践引 入 篇第一章 算法概述11 用计算机求解问题问题求解(problem solving)是个大课题，它涉 及归约、推断、决策、规划、常识推理、定理证明 和相关过程的核心概念我们学习算法设计的重点就是把人类找到的求 解问题的方法、步骤，以过程化、形式化、机械化 的形式表示出来，以便让计算机执行。（当然人工 智能软件系统也离不开“算法设计”这个最基本的 软件设计环节。）就把我们学习的目标定为“用计 算机求
2、解问题”。111 用计算机求解问题的步骤现实中，在解决一个问题时，根据不同的 经验，不同的环境会采用不同的方法，用计 算机解决现实中的问题，同样也有很多不同 的方法，但解决问题的基本步骤是相同的。 下面给出用计算机求解问题的一般步骤。1. 问题分析准确、完整地理解和描述问题是解决问题的第 一步。要做到这一点，必须注意以下一些问题：在 未经加工的原始表达中，所用的术语是否都明白其 准确定义？题目提供了哪些信息？这些信息有什么 用？题目要求得到什么结果？题目中作了哪些假定 ？是否有潜在的信息？判定求解结果所需要的中间 结果有哪些？等等。针对每个具体的问题，必须认 真审查问题描述，理解问题的真实要求
3、。2、数学模型建立用计算机解决实际问题必须有合适的数学模型 ，因为在现实问题面前，计算机是无能为力。对一 个实际问题建立数学模型，可以考虑这样两个基本 问题：最适合于此问题的数学模型是什么？是否有 已经解决了的类似问题可借鉴？如果上述第二个问题的答复是肯定的,那么通过 类似的问题的分析、比较和联想，可加速问题的解 决。 3、算法设计与选择算法设计是指设计求解某一特定类型问题的一 系列步骤，并且这些步骤是可以通过计算机的基本 操作来实现的。算法设计要同时结合数据结构的设 计，简单说数据结构的设计就是选取存储方式。算 法的设计与模型的选择更是密切相关的，但同一模 型仍然可以有不同的算法，而且它们的
4、有效性可能 有相当大的差距。* 在这些步骤中，算法设计是解决问题的核心。 4、算法分析算法分析的目的，首先为了对算法的某些特定 输入，估算该算法所需的内存空间和运行时间；其 次是为了建立衡量算法优劣的标准，用以比较同一 类问题的不同算法。通常将时间和空间的增长率作 为衡量的标准。另参见114算法及其设计的评价5、算法表示对于复杂的问题，确定算法后可以通过图形准 确表示算法。算法的表示方式很多如：算法流程图 、盒图、PAD图和伪码（类似于程序设计语言）等。 6、算法实现根据选用的程序设计语言，要解决下列一些问 题：有哪些变量，它们是什么类型？需要多少数组 ，规模有多大？用什么结构来组织数据？需要
5、哪些 子算法？等等。算法的实现方式，对运算速度和所需内存容量 都有很大影响。7、程序调试算法测试的实质是对算法应完成任务的实验证 实，同时确定算法的使用范围。测试方法一般有两 种：白盒测试对算法的各个分支进行测试；黑盒测 试检验对给定的输入是否有指定输出。如何选择算法测试中的输入，还没有一般答案 。通常采用的方法是，对输入数据做有代表性的采 样，使之对被测试算法的各个语句、分支和路径尽 可能都被检查到。对输入集中的边界点也要进行测 试。经测试验证是否正确的算法，在较大程度上是 可以相信它的正确性。、结果整理文档编制编制文档的目的是让人了解你编写的算法。首 先要把代码编写清楚。代码本身就是文档。
6、同时还 要采用注释的方式，另外还包括算法的流程图，自 顶向下各研制阶段的有关记录，算法的正确性证明 （或论述），算法测试结果，对输入/输出的要求及 格式的详细描述等。112 算法及其要素和特性、算法的定义算法是指在解决问题时，按照某种机械步骤一 定可以得到问题结果的处理过程。当面临某个问题 时，需要找到用计算机解决这个问题的方法和步骤 ，算法就是对解决这个问题的方法和步骤的描述。机械步骤是指，算法中有待执行的运算和操作 ，必须是相当基本的。换言之，它们都是能够精确 地运行的算法，执行者甚至不需要掌握算法的含义 ，即可根据该算法的每一步骤要求，进行操作并最 终得出正确的结果。2算法的要素算法由操
7、作、控制结构、数据结构三要素组成 。1）操作算术运算：加、减、乘、除 关系比较：大于、小于、等于、不等于逻辑运算：与、或、非 数据传送：输入、输出, 赋值2）控制结构 各操作之间的执行次序。顺序结构：各操作依次执行选择结构：由条件是否成立来选择 执行 循环结构：有些操作要重复执行，直到功能满 足某个条件时结束。又称重复或迭 代结构。注意：模块间的调用也是一种控制结构，特别 地模块 自身的直接或间接调用递归结构，是一种功能很 强的控制结构。3）数据结构算法操作的对象是数据，数据间的逻辑关系、 数据的存储方式及处理方式就是数据的数据结构。 它与算法设计是紧密相关的。注意： 算法是把人类找到的求解问
8、题的方法 ，用以上要素过程化、形式化、机械化地表示出 来。在算法的表示中要满足以下的性质：目的性 算法有明确的目的，能完成赋予它的功能分步性 算法为完成其复杂的功能，由一系列计算机可执行的步骤组成 有序性 算法的步骤是有序的，不可随意改变算法步骤的执行顺序 有限性 算法是有限的指令序列，所包含步骤也是有限的 操作性 算法是有限的指令序列，算法所包含的步骤是有限的 3. 算法的基本性质4. 算法的地位算法是计算机学科中最具有方法论性质的核心 概念，也被誉为计算机学科的灵魂。5. 算法的基本特征有穷性一个算法在执行有穷步之后必须结束。也就是说一个算 法它所包含的计算步骤是有限的而且每个步骤都能在有
9、限时 间内完成。 确定性 对于每种情况下所应执行的操作，在算法中都有确切的 规定，使算法的执行者或阅读者都能明确其含义及如何执行 。并且在任何条件下，算法都只有一条执行路径。可行性 算法中描述的操作都可以通过已经实现的基本 操作运算有限次实现。 算法有零个或多个的输入有些输入量需要在算法执行过程中输入，而有 的算法表面上可以没有输入，实际上已被嵌入算法 之中。算法有一个或多个的输出它是一组与输入有确定关系的量值，是算法进 行信息加工后得到的结果。113 算法设计及基本方法1. 算法设计的概念算法设计作为用计算机解决问题的一个步骤,其 任务是对各类具体问题设计良好的算法;作为一门课 程，是研究设
10、计算法的规律和方法。2算法设计应注意的问题1）正确性（Correctness） 一切合法的输入数据都能得出满足要求的结果 ；典型、苛刻的几组输入数据也能够得出满足要求 的结果。2）可读性(Readability)算法应该易于人的理解；晦涩难读的算法易于 隐藏较多错误而难以调试。3）健壮性（Rubustness）算法的异常情况。处理出错的方法是返回一个 表示错误或错误性质的值，以便在更高的抽象层次 上进行处理。4）高效率与低存储量需求效率指的是算法执行时间；存储量指的是算法 执行过程中所需的最大存储空间。3算法设计的基本方法1）结构化方法“自顶向下, 逐步求精”结构化方法总的指导思想是自顶向下、
11、逐步求精。 它的基本原则是功能的分解与模块化所谓“自顶向下” 是将现实世界的问题经抽象转 化为逻辑空间或求解空间的问题。是将复杂且大的问题 划分为较小问题，找出问题的关键和重点，然后抽象、 概括地描述问题。所谓“逐步求精” 是将复杂问题经抽象化处理变 为相对比较简单的问题。经若干步精化处理，最后细化 到用“三种基本结构”及基本操作去描述算法。结构算法设计技术的优越性: 符合人类解决复杂问题的普遍规律 。 用先全局后局部、先整体后细节、先抽象后具体的逐步求精过程开发出的算法有清晰的层次结构 。2) 面向对象方法对象=数据+对数据操作的代码实体面向对象算法设计方法的过程包括以下步骤： 在给定的抽象
12、层次上识别类和对 象 识别这些对象和类的语义 识别类和对象之间的关系 实现类和对象面向对象方法的特征主要包括:抽象化 将各种独立的操作分解成为可以用命名区 分的单元。封装性 不同的操作具有不同的作用范围。多态性 对于不同数据类型的相似操作使用相同的名 。继承性 类可以被继承。重用是面向对象的一个重要优点。最大特点是能够 大幅度的提高软件项目的成功率，减少日后的维护 费用，提高软件的可移植性和可靠性。3）本书采用的设计方法结构化设计方法 （1）自顶向下从抽象到具体 把一个较大的算法划分为若干子模块 每一个模块可继续划分为更小的子模块 直到用三种控制结构和具体操作表示算法 注：运用这种编程方法，考
13、虑问题必须先进行 整体分析。（2）模块划分的基本要求 模块的功能尽可能地单一化、明确化 模块间的联系及相互影响尽可能地小 模块的规模应当足够小，以便于调试原则是简单性、独立性和完整性。（3）模块间的接口问题传递方式一般有以下几种： 按名共享：全局变量 子模块返回调用模块信息：子模块名 调用模块传递给子模块信息：值参数传递 调用模块与子模块互相传递信息：变量参数 传递(C语言没有此种传递方,Pascal、C+语言提供 此类参数) 按地址共享变量：地址参数传递（参数为指 针变量名、数组名，变量地址）（4）算法细节设计的基本方法从具体到抽象设计算法“如何做”的细节是比较容易出错的， 如：循环变量的初
14、始值或终值，数组的下标与循环变 量间的关系等算法细节的确定。最基本的方法是通过 “枚举”一些真实数据，从具体的实例中，抽象“归 纳”出算法的这些细节。 （5）算法的正确性算法的正确性不容易证明。即使可以证明，所 涉及的数学理论和推导证明过程也很复杂。 设计算法时力争严谨、考虑周全，可能的情况 下，分析论证算法设计的合理性，最后在算法实现 后，靠大量的测试，以保证算法的正确性。1.1.4 从算法到实现从算法到实现应注意的问题有：1. 数据类型的选择类型的选择主要取决于你解决问题中数据的实 际情况。 这部分知识不属于本书的必要内容。在此进行简 述是为了让读者在学习算法设计过程中上机实验时， 不要走
15、太多弯路。 2 计算过程的差异 运算符号的差异运算符优先级的差异标识符命名方式的差异循环方式的差异3. 结果的输出格式如：矩阵输出时上、下行的数据应该对齐。 4. 算法实现后的测试、调试测试就是要发现算法是否存在问题。测试就是 要找到出现问题的原因并改正它。然后还需要进行 回归测试，以确保算法的正确性。1.2 算法描述 121 算法描述简介算法是对解题过程的精确描述。算法 = 控制结构 + 原操作表示算法的语言主要有：自然语言、流程图、 盒图、PAD图、伪代码和计算机程序设计语言等。1自然语言自然语言是人们日常所用的语言。其缺点是： 由于自然语言的歧义性容易导致算法执行的 不确定性。 自然语言
16、的语句一般太长从而导致了用自然 语言描述的算法太长。 当一个算法中循环和分支较多时就很难清晰 地表示出来。 自然语言表示的算法不便翻译成计算机程序 设计语言理解的语言。2流程图流程图可以表示任何算法的逻辑结构。1) 基本组件算法的 加工、处理 条件 控制流 连接点入口和出口2）三种基本控制结构 顺序结构： 选择结构IF THEN ELSE型分支 DOCASE型多分支 循环结构DOWHILE型循环 DOUNTIL循环结构3) 算法流程图的主要缺点 不是逐步求精的好工具，它诱使算法员过早 地考虑算法的控制流程，而不去考虑算法的全局结 构。 随意性太强，结构化不明显。 不易表示数据结构。 流程图的层次感不明显3盒图（NS流程图）（1）盒图具有以下优点： 层次感强、嵌套明确 支持自顶向下、逐步求精。
