算法程序与编程课件.ppt

1、第四章 算法、程序与编程a 问题的提出：人是如何来解决问题的？人是如何解决复杂问题的？计算机如何来解决问题的？问题的解决计算机算法、程序与编程a第四章 算法、程序与编程 学习目的和要求：了解算法与程序概念 理解算法的复杂性与NP问题 熟悉基本算法 知道数据和数据结构 熟悉高级语言 掌握程序设计规划 了解程序理论和软件工程 a一种逐步解决问题或完成任务的方法一种逐步解决问题或完成任务的方法输入列表输入列表输出列表输出列表算法算法a寻找最大值的一个算法(1)输入5个数，输出其中的最大值1.输入：算法接受一组5个整数的数据。2.过程第一步第一步 检查第一个整数，把这个整数赋给变量Largest第二步

2、第二步 把第二个数与Largest中的数进行比较，如大于Largest中的数就将该数赋予它，否则，Largest中的数不变第三步第三步 把第三个数与Largest中的数进行比较，如大于Largest中的数就将该数赋予它，否则，Largest中的数不变。此时13大于12，所以，变量Largest中变为13。a寻找最大值的一个算法(2)第四步第四步 把第四个数与Largest中的数进行比较，如大于Largest中的数就将该数赋予它，否则，Largest中的数不变。此时第四个数是9，小于13，所以Largest中的数不变。第五步第五步 把第四五个数与Largest中的数进行比较，如大于Largest

3、中的数就将该数赋予它，否则，Largest中的数不变。此时第五个数是11，小于13，所以Largest中的数不变。3.输出 最大值13 结束a算法的例子示意图a算法的精化a算法的泛化a三三 种种 结结 构构a 算法的基本结构算法的基本结构 a流程图aa 伪代码：是在编写算法时，为了更好地表示算法本身，不在一些小的细节上纠缠，而采用类似于英语（或其他自然语言）表示算法的算法表示方法。a伪代码a用伪代码写出一个求两个数的平均值的算法AverageOfTwoInput:Two numbers1.Add the two numbers2.Divide the result by 23.Return t

4、he result by step 24.EndaPass/NoPassGradeInput:One number1.if(the number is greater than or equal to 60)then 1.1 Set the grade to“pass”else 1.2 Set the grade to“nopass”End if2.Return the grade3.End 用伪代码写出一个可以把不同数值成绩分成及格或不及格的算法aLetterGradeInput:One number1.if(the number is between 90 and 100,inclusiv

5、e)then 1.1 Set the grade to“A”End if2.if(the number is between 80 and 89,inclusive)then 2.1 Set the grade to“B”End if 用伪代码写出一个可以把数字型成绩变成字母等级成绩的算法aContinues on the next slide3.if(the number is between 70 and 79,inclusive)then 3.1 Set the grade to“C”End if4.if(the number is between 60 and 69,inclusive

6、)then 4.1 Set the grade to“D”End ifa算法的定义 算法定义1：算法是一组明确步骤的有序集合，它产生结果，并在有限的时间内终止。有序集合 明确步骤 产生结果 在有限的时间内结束a 算法定义算法定义2 2：（1）给定问题和设备，一个算法是用该设备可理解的语言表示的，解决这个问题的一种方法是精确刻画。特别地，算法具有以下特征属性：算法应用于一个具体的输入集合或问题描述将在有穷步动作之后得到结果；该序列有一个唯一的初始动作：该序列中的每一个动作有一个唯一的后继动作 该序列终止时或者得到这个问题的解，或者因该问题不可解而获得不可解说明。a 算法定义算法定义3 3：一个算

7、法，就是一个有穷规则的集合，其中之规则确定了一个解决某一特定型问题的运算序列。此外，算法的规则序列必须满足以下5个重要条件，即具有以下五个特性：（1）有穷性。算法必须总是在执行有穷步之后结束（2）确定性。算法的每一个步骤必须是确切地定义的；（3）输入。算法有零个或多个输入（4）输出。算法有一个或多个输出，即与输入有某个关系的量。（5）能行性。算法中有待执行的运算和操作必须是相当基本的，即是说，它们原则上是能够精确地进行的，而且用笔和纸做有穷次就可以完成。aa 计算的复杂性（算法的复杂性）的概念计算的复杂性（算法的复杂性）的概念 计算空间的复杂性 计算时间的复杂性 相似性与对偶原理：计算空间与计

8、算时间的互换性 算法复杂性的描述算法复杂性的描述：算法在执行过程中总共所需要的初等运算的步数来表示算法用于求解任一问题的某一例子时所需的时间。a计算的复杂性与NP问题（2）算法复杂性的表示 多项式时间算法：是指存在某个以输入长度n为变量的多项式函数中(n)，使其时间复杂性函数为O(p(n)的算法。因此复杂性为O(n)、O(106n3)、O(5n8)等算法均为多项式时间算法。指数时间算法：是指任何其时间复杂性函数不可能如上用多项式函数去界定的算法，例如O（2n）、O(n!)、O(nn)、O(2n2)等都在算法上是不可接受的。a计算的复杂性与NP问题（3）时间复杂性的表示 O（1）称为常数级；O（

9、logn）称为对数级；O（n）称为线性级；O(nc)称为多项式级，（C为常数）；O（Cn）称为指数级，（C为常数）；O(n!)称为阶乘级；a计算的复杂性与NP问题（4）P P类与类与NPNP类问题：类问题：一个算法如果存在图灵机可计算的多项式时间计算复杂性算法，就将该算法归入P类；如果存在非确定性图灵机可计算的多项式时间计算复杂性算法，就将其归入NP类。P=NP?a结构图 结构图：是程序员使用的高层设计工具。结构图能很好地表示程序设计者的逻辑思维的过程；把算法中各个模块之间的关系表示的更加清楚。结构图的常用图标：结构图的常用图标：aa 递归、迭代算法：递归算法是算法自我调用的过程。迭代的定义：

10、算法中没有包含算法自身，只是 利用上一步计算的结果得出最后答案的算法 递归的定义：算法中包含了算法自身的调用的 算法。分治算法：就是将一个难以直接解决的大问题，通过分析，分解为一些规模较小的相同问题，进而对各个小问题进行解决，最后达到整个问题的解决。a迭代算法的例子a递归算法的例子a递归算法中递归调用示意图aFactorialInput:A positive integer num1.Set FactN to 02.Set i to I3.while(i is less than or equal to num)3.1 Set FactN to FactN x I 3.2 Increment

11、iEnd while4.Return FactNEnd迭代算法迭代算法aFactorialInput:A positive integer num1.if(num is equal to 0)then 1.1 return 1else1.2 return num x Factorial(num 1)End if2.End递归算法递归算法aa 简单数据结构类型：表41 简单数据类型a数据与数据结构简介（2）数据结构：二元组 Data-structure=(D,R),称为数据D的数据结构。其中D为数据元素的集合，R是D上关系的集合。a基本数据结构 数组(Array)一维数组 二维数组 a2.Two

12、-dimensional array(二维数组二维数组)a 记录：是一组相关元素的集合，它们可能是不同类型的，但整个记录是相关的，有一个统一的名称。域：具有含义的记录中命名数据的最小元素；它可以有类型且存在于内存中；它能被赋值，也能够被选择和操作。它与变量不同之处在于它是记录的一个部分。数组与记录的区别：数组中的元素必须是同一类型，而记录中的元素则可以相同或不同类型，只要相关即可。在设计记录时记录中的数据必须都与一个对象关联。a记录的操作记录的操作访问记录访问记录 访问单个域访问单个域 访问整个记录访问整个记录读入读入写入记录（成员）写入记录（成员）aLinked lists（链表）（链表）链

13、表链表：是一个有序的集合，其中每一个元素都包含是一个有序的集合，其中每一个元素都包含 下一个元素的地址；即下一个元素的地址；即数据数据和和指针指针（地址）。（地址）。a几个典型的常用的抽象数据类型 线性列表（Linear listLinear list）a 线性列表的操作 （1）插入 （2）删除 （3）检索 （4）遍历aInsertion in a linear listaDeletion from a linear lista栈 栈是一种限制性列表，对其的操作添加、删除只能在一端实现。(LIFO)Three representations of a stacka 栈的操作 入栈 出栈 空Pu

14、sh operation in a stackaPop operation in a stacka队列 队列是一种线性列表，对其的操作只能从一端进入，另一端删除。只能按存入的顺序进行处理。(FIFO)a树节点：组成树的有限的元素。节点：组成树的有限的元素。分支：连接各节点的有向（或无向）线段。分支：连接各节点的有向（或无向）线段。度：与节点连接的分支的数目。有出度和入度之度：与节点连接的分支的数目。有出度和入度之分，指向节点的称入度，离开节点的称出度。分，指向节点的称入度，离开节点的称出度。aSubtreesa二叉树二叉树a二叉树的前序遍历二叉树的前序遍历a二叉树的后序遍历a二叉树的广度优先遍

15、历a 数组形式AFCEDB概念性的树实际的存储结构这种存储形式在二叉树不是均衡的情况下会浪费存储空间a 二叉树的应用 网络 最小生成树（连接所有节点的最短路径）a图a 图的应用 网络 最小生成树a高级程序设计语言a程序设计语言发展的历史 机器语言 汇编语言 高级语言a计算机语言过程化语言FORTRANCOBOLPascalCAda说明性语言PROLOG专用语言HTMLXMLSQL PERL函数型语言LISPSchenme面向对象语言C+JavaVC+a程序的构建（编程）与执行 程序编写 编辑程序 链接程序文本编写编译程序链接程序程序系统库程序的执行预处理程序编译翻译程序a程序规划与设计程序规划

16、与设计(1)(1)程序规划程序规划 步骤步骤1:1:分析问题并制定概要设计方案。编程人员必须对分析问题并制定概要设计方案。编程人员必须对问题有完全、准确的了解，用准确的语言对问题进行描问题有完全、准确的了解，用准确的语言对问题进行描述，主要考虑以下几个方面；述，主要考虑以下几个方面；问题的输入是什么？已知的是什么？还要给什么，使用什问题的输入是什么？已知的是什么？还要给什么，使用什么格式。么格式。期望的输出是什么？需要什么类型的报告、图表或信息。期望的输出是什么？需要什么类型的报告、图表或信息。从给定的输入到期望的输出，必要的处理步骤是什么？从给定的输入到期望的输出，必要的处理步骤是什么？步骤

17、步骤2:2:制定详细设计：（算法设计）必须制定一组精确制定详细设计：（算法设计）必须制定一组精确的步骤，即编写提纲。这些步骤应该是明确、详细和有的步骤，即编写提纲。这些步骤应该是明确、详细和有限的，并能在合理的时间内完成；同时选定实现各步骤限的，并能在合理的时间内完成；同时选定实现各步骤的语言。的语言。a程序规划与设计程序规划与设计(2)(2)步骤步骤3:3:用编程语言编写程序代码及其文档。用编程语言编写程序代码及其文档。在步骤在步骤2 2中越详细清楚用程序代码就越容易。中越详细清楚用程序代码就越容易。在用程序代码在用程序代码“翻译翻译”的过程一定要准确、完的过程一定要准确、完整。特别是对文档

18、的编写，对各条语句功能整。特别是对文档的编写，对各条语句功能的注释，往往会被忽视，现代编程是一种团的注释，往往会被忽视，现代编程是一种团体的合作行为，让别人能容易地看懂你的程体的合作行为，让别人能容易地看懂你的程序，对整个系统的编写是绝对必要的。同时序，对整个系统的编写是绝对必要的。同时对程序的修改维护都有很大的帮助。对程序的修改维护都有很大的帮助。a程序规划与设计程序规划与设计(3)(3)步骤步骤4:4:测试程序：这是一个在前几个步骤进测试程序：这是一个在前几个步骤进行过程中一个不断重复的过程。对于编写出行过程中一个不断重复的过程。对于编写出来的每一部分代码，都应该进行测试，以确来的每一部分

19、代码，都应该进行测试，以确保程序运行的正确性。保程序运行的正确性。步骤步骤5:5:验证程序：一旦程序编写完并进行一验证程序：一旦程序编写完并进行一定的测试后，就应该通过大范围的测试来验定的测试后，就应该通过大范围的测试来验证。验证时必须根据用户的要求，不断进行证。验证时必须根据用户的要求，不断进行修改调整到用户满意为止。修改调整到用户满意为止。a程序规划与设计程序规划与设计(4)(4)程序设计和调试程序设计和调试 养成良好的编程风格养成良好的编程风格错误定位设计错误修复程序错误修复程序重测a软件工程 软件工程：在大型的软件开发中，引入软件工程：在大型的软件开发中，引入工程管理的一整套的管理方法

20、，对软件工程管理的一整套的管理方法，对软件开发过程进行规划、设计、监控和检测，开发过程进行规划、设计、监控和检测，以确保开发的过程、开发时间和软件质以确保开发的过程、开发时间和软件质量都在人的控制管理之下，从而使软件量都在人的控制管理之下，从而使软件开发的顺利进行。所以，对软件开发过开发的顺利进行。所以，对软件开发过程和软件质量的管理、监控的方法措施程和软件质量的管理、监控的方法措施就构成了软件工程学。就构成了软件工程学。a程序设计理论程序设计理论 程序设计理论：程序设计理论：通过对程序设计的各种问题进行了系统研究，进行了规范总结，如在程序设计中的自顶向下逐步求精的程序设计方法，自底向上的程序

21、设计方法、程序推导的设计方法、程序变换的设计方法、函数式程序设计技术、逻辑程序设计技术、面向对象的程序设计、程序验证技术、约束程序设计技术和并发程序设计技术等，一系列规范的，好的程序开发方法、形成了丰富的程序设计理论，极大地推进了程序设计技术的发展。a本章任务：1.你认为什么是程序和程序设计？用实际生活的例子说明。2.论述一下软件的生命周期。3、查阅资料：请你通过互联网或者书籍文献查找“计算机语言”相关内容。a本章任务：4、思考题：P117 1-3 5、讨论:围绕以下问题，组织学生分组讨论，然后让每组代表阐述他们的看法和思想。(1)怎样养成良好的算法思想？(2)如何成为一个优秀的程序开发人员？(3)学习良好的软件开发习惯。(4)软件工程的功能及应用。(5)如何学好一门基本的编程语言。4、撰写小论文：解析软件工程流程与方法。a