算法程序与编程课件.ppt

第四章 算法、程序与编程,1,a,第四章 算法、程序与编程1a,问题的提出：人是如何来解决问题的？人是如何解决复杂问题的？计算机如何来解决问题的？问题的解决计算机算法、程序与编程,2,a,问题的提出：2a,第四章 算法、程序与编程,学习目的和要求：了解算法与程序概念理解算法的复杂性与NP问题熟悉基本算法知道数据和数据结构熟悉高级语言掌握程序设计规划了解程序理论和软件工程,3,a,第四章 算法、程序与编程学习目的和要求：3a,一种逐步解决问题或完成任务的方法,输入列表,输出列表,算法,4,a,一种逐步解决问题或完成任务的方法输入列表输出列表算法4a,寻找最大值的一个算法(1),输入5个数，输出其中的最大值1.输入：算法接受一组5个整数的数据。2.过程第一步 检查第一个整数，把这个整数赋给变量Largest第二步 把第二个数与Largest中的数进行比较，如大于Largest中的数就将该数赋予它，否则，Largest中的数不变第三步 把第三个数与Largest中的数进行比较，如大于Largest中的数就将该数赋予它，否则，Largest中的数不变。此时13大于12，所以，变量Largest中变为13。,5,a,寻找最大值的一个算法(1)输入5个数，输出其中的最大值5a,寻找最大值的一个算法(2),第四步 把第四个数与Largest中的数进行比较，如大于Largest中的数就将该数赋予它，否则，Largest中的数不变。此时第四个数是9，小于13，所以Largest中的数不变。第五步 把第四五个数与Largest中的数进行比较，如大于Largest中的数就将该数赋予它，否则，Largest中的数不变。此时第五个数是11，小于13，所以Largest中的数不变。3.输出 最大值13 结束,6,a,寻找最大值的一个算法(2)第四步 把第四个数与Larges,算法的例子示意图,7,a,算法的例子示意图7a,算法的精化,8,a,算法的精化8a,算法的泛化,9,a,算法的泛化9a,三 种 结 构,10,a,三 种 结 构10a,算法的基本结构,11,a,算法的基本结构 11a,流程图,12,a,流程图12a,算法的表示,13,a,算法的表示13a,伪代码：是在编写算法时，为了更好地表示算法本身，不在一些小的细节上纠缠，而采用类似于英语（或其他自然语言）表示算法的算法表示方法。,14,a,伪代码：是在编写算法时，为了更好地表示算法本身，不在一些小的,伪代码,15,a,伪代码15a,用伪代码写出一个求两个数的平均值的算法,例1,AverageOfTwoInput:Two numbersAdd the two numbersDivide the result by 2Return the result by step 2End,Algorithm 8.1:,Average of two,16,a,用伪代码写出一个求两个数的平均值的算法例1AverageO,Pass/NoPassGradeInput:One numberif(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 ifReturn the gradeEnd,Algorithm 8.2:,Pass/no pass Grade,用伪代码写出一个可以把不同数值成绩分成及格或不及格的算法,例2,17,a,Pass/NoPassGradeAlgorithm 8.2,LetterGradeInput:One number1.if(the number is between 90 and 100,inclusive)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,Algorithm 8.3:,Letter grade,用伪代码写出一个可以把数字型成绩变成字母等级成绩的算法,例3,18,a,LetterGradeAlgorithm 8.3:Lett,Algorithm:,Letter grade(continued),Continues on the next slide,3.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)then 4.1 Set the grade to“D”End if,19,a,Algorithm:Letter grade(conti,算法的定义,算法定义1：算法是一组明确步骤的有序集合，它产生结果，并在有限的时间内终止。有序集合明确步骤产生结果在有限的时间内结束,20,a,算法的定义算法定义1：算法是一组明确步骤的有序集合，它产生结,算法定义2：（1）给定问题和设备，一个算法是用该设备可理解的语言表示的，解决这个问题的一种方法是精确刻画。特别地，算法具有以下特征属性：算法应用于一个具体的输入集合或问题描述将在有穷步动作之后得到结果；该序列有一个唯一的初始动作：该序列中的每一个动作有一个唯一的后继动作 该序列终止时或者得到这个问题的解，或者因该问题不可解而获得不可解说明。,21,a,算法定义2：21a,算法定义3：一个算法，就是一个有穷规则的集合，其中之规则确定了一个解决某一特定型问题的运算序列。此外，算法的规则序列必须满足以下5个重要条件，即具有以下五个特性：（1）有穷性。算法必须总是在执行有穷步之后结束（2）确定性。算法的每一个步骤必须是确切地定义的；（3）输入。算法有零个或多个输入（4）输出。算法有一个或多个输出，即与输入有某个关系的量。（5）能行性。算法中有待执行的运算和操作必须是相当基本的，即是说，它们原则上是能够精确地进行的，而且用笔和纸做有穷次就可以完成。,22,a,算法定义3：一个算法，就是一个有穷规则的集合，其中之规则确定,计算的复杂性与NP问题,23,a,计算的复杂性与NP问题23a,计算的复杂性（算法的复杂性）的概念计算空间的复杂性计算时间的复杂性相似性与对偶原理：计算空间与计算时间的互换性算法复杂性的描述：算法在执行过程中总共所需要的初等运算的步数来表示算法用于求解任一问题的某一例子时所需的时间。,24,a,计算的复杂性（算法的复杂性）的概念24a,计算的复杂性与NP问题（2）,算法复杂性的表示多项式时间算法：是指存在某个以输入长度n为变量的多项式函数中(n)，使其时间复杂性函数为O(p(n)的算法。因此复杂性为O(n)、O(106n3)、O(5n8)等算法均为多项式时间算法。指数时间算法：是指任何其时间复杂性函数不可能如上用多项式函数去界定的算法，例如O（2n）、O(n!)、O(nn)、O(2n2)等都在算法上是不可接受的。,25,a,计算的复杂性与NP问题（2）算法复杂性的表示25a,计算的复杂性与NP问题（3）,时间复杂性的表示O（1）称为常数级；O（logn）称为对数级；O（n）称为线性级；O(nc)称为多项式级，（C为常数）；O（Cn）称为指数级，（C为常数）；O(n!)称为阶乘级；,26,a,计算的复杂性与NP问题（3）时间复杂性的表示26a,计算的复杂性与NP问题（4）,P类与NP类问题：一个算法如果存在图灵机可计算的多项式时间计算复杂性算法，就将该算法归入P类；如果存在非确定性图灵机可计算的多项式时间计算复杂性算法，就将其归入NP类。P=NP?,27,a,计算的复杂性与NP问题（4）P类与NP类问题：一个算法如果存,结构图,结构图：是程序员使用的高层设计工具。结构图能很好地表示程序设计者的逻辑思维的过程；把算法中各个模块之间的关系表示的更加清楚。,结构图的常用图标：,28,a,结构图结构图：是程序员使用的高层设计工具。结构图能很好地表示,递 归、迭代与分治算法,29,a,递 归、迭代与分治算法29a,递归、迭代算法：递归算法是算法自我调用的过程。迭代的定义：算法中没有包含算法自身，只是 利用上一步计算的结果得出最后答案的算法递归的定义：算法中包含了算法自身的调用的 算法。分治算法：就是将一个难以直接解决的大问题，通过分析，分解为一些规模较小的相同问题，进而对各个小问题进行解决，最后达到整个问题的解决。,30,a,递归、迭代算法：递归算法是算法自我调用的过程。30a,迭代算法的例子,31,a,迭代算法的例子31a,递归算法的例子,32,a,递归算法的例子32a,递归算法中递归调用示意图,33,a,递归算法中递归调用示意图33a,Iterative factorial,FactorialInput:A positive integer numSet FactN to 0Set i to Iwhile(i is less than or equal to num)3.1 Set FactN to FactN x I 3.2 Increment iEnd whileReturn FactNEnd,迭代算法,34,a,Iterative factorialFactorial迭,FactorialInput:A positive integer numif(num is equal to 0)then 1.1 return 1else1.2 return num x Factorial(num 1)End ifEnd,Recursive factorial,递归算法,35,a,FactorialRecursive factorial,数据与数据结构简介,36,a,数据与数据结构简介36a,简单数据结构类型：,表41 简单数据类型,37,a,简单数据结构类型：表41 简单数据类型37a,数据与数据结构简介（2）,数据结构：二元组 Data-structure=(D,R),称为数据D的数据结构。其中D为数据元素的集合，R是D上关系的集合。,38,a,数据与数据结构简介（2）数据结构：二元组 38a,基本数据结构,数组(Array)一维数组二维数组,39,a,基本数据结构数组(Array)39a,2.Two-dimensional array(二维数组),40,a,2.Two-dimensional array(二维数组)4,记录：是一组相关元素的集合，它们可能是不同类型的，但整个记录是相关的，有一个统一的名称。域：具有含义的记录中命名数据的最小元素；它可以有类型且存在于内存中；它能被赋值，也能够被选择和操作。它与变量不同之处在于它是记录的一个部分。数组与记录的区别：数组中的元素必须是同一类型，而记录中的元素则可以相同或不同类型，只要相关即可。在设计记录时记录中的数据必须都与一个对象关联。,41,a,记录：是一组相关元素的集合，它们可能是不同类型的，但整个记录,记录中的元素可以是相同或不相同的类型，但记录中的所有元素必须是相关的,记录的操作访问记录 访问单个域 访问整个记录读入写入记录（成员）,42,a,记录中的元素可以是相同或不相同的类型，但记录中的所有元素必须,Linked lists（链表）,链表：是一个有序的集合，其中每一个元素都包含 下一个元素的地址；即数据和指针（地址）。,43,a,Linked lists（链表）链表：是一个有序的集合，其中,几个典型的常用的抽象数据类型,线性列表（Linear list）,44,a,几个典型的常用的抽象数据类型线性列表（Linear list,线性列表的操作（1）插入（2）删除（3）检索（4）遍历,45,a,线性列表的操作45a,Insertion in a linear list,46,a,Insertion in a linear list46a,Deletion from a linear list,47,a,Deletion from a linear list47a,栈,栈是一种限制性列表，对其的操作添加、删除只能在一端实现。(LIFO),Three representations of a stack,48,a,栈栈是一种限制性列表，对其的操作添加、删除只能在一端实现。(,栈的操作入栈出栈空,Push operation in a stack,49,a,栈的操作Push operation in a stack4,Pop operation in a stack,50,a,Pop operation in a stack50a,队列,队列是一种线性列表，对其的操作只能从一端进入，另一端删除。只能按存入的顺序进行处理。(FIFO),51,a,队列队列是一种线性列表，对其的操作只能从一端进入，另一端删除,树,节点：组成树的有限的元素。分支：连接各节点的有向（或无向）线段。度：与节点连接的分支的数目。有出度和入度之分，指向节点的称入度，离开节点的称出度。,52,a,树节点：组成树的有限的元素。52a,Subtrees,53,a,Subtrees53a,二叉树,54,a,二叉树54a,二叉树的前序遍历,55,a,二叉树的前序遍历55a,二叉树的后序遍历,56,a,二叉树的后序遍历56a,二叉树的广度优先遍历,57,a,二叉树的广度优先遍历57a,数组形式,A,F,C,E,D,B,概念性的树,实际的存储结构,这种存储形式在二叉树不是均衡的情况下会浪费存储空间,58,a,数组形式AFCEDB概念性的树实际的存储结构这种存储形式在二,二叉树的应用网络最小生成树（连接所有节点的最短路径）,59,a,二叉树的应用59a,图,60,a,图60a,图的应用网络最小生成树,61,a,图的应用61a,高级程序设计语言,62,a,高级程序设计语言62a,程序设计语言发展的历史,机器语言汇编语言高级语言,63,a,程序设计语言发展的历史机器语言63a,64,a,计算机语言过程化语言说明性语言专用语言函数型语言面向对象语言,程序的构建（编程）与执行,程序编写编辑程序链接程序,文本编写,编译程序,链接程序,程序系统库,程序的执行,预处理程序,编译翻译程序,65,a,程序的构建（编程）与执行程序编写文本编写编译程序链接程序程序,程序规划与设计(1),程序规划步骤1:分析问题并制定概要设计方案。编程人员必须对问题有完全、准确的了解，用准确的语言对问题进行描述，主要考虑以下几个方面；问题的输入是什么？已知的是什么？还要给什么，使用什么格式。期望的输出是什么？需要什么类型的报告、图表或信息。从给定的输入到期望的输出，必要的处理步骤是什么？步骤2:制定详细设计：（算法设计）必须制定一组精确的步骤，即编写提纲。这些步骤应该是明确、详细和有限的，并能在合理的时间内完成；同时选定实现各步骤的语言。,66,a,程序规划与设计(1)程序规划66a,程序规划与设计(2),步骤3:用编程语言编写程序代码及其文档。在步骤2中越详细清楚用程序代码就越容易。在用程序代码“翻译”的过程一定要准确、完整。特别是对文档的编写，对各条语句功能的注释，往往会被忽视，现代编程是一种团体的合作行为，让别人能容易地看懂你的程序，对整个系统的编写是绝对必要的。同时对程序的修改维护都有很大的帮助。,67,a,程序规划与设计(2)步骤3:用编程语言编写程序代码及其文档。,程序规划与设计(3),步骤4:测试程序：这是一个在前几个步骤进行过程中一个不断重复的过程。对于编写出来的每一部分代码，都应该进行测试，以确保程序运行的正确性。步骤5:验证程序：一旦程序编写完并进行一定的测试后，就应该通过大范围的测试来验证。验证时必须根据用户的要求，不断进行修改调整到用户满意为止。,68,a,程序规划与设计(3)步骤4:测试程序：这是一个在前几个步骤进,程序规划与设计(4),程序设计和调试养成良好的编程风格,69,a,程序规划与设计(4)程序设计和调试错误定位设计错误修复程序错,软件工程,软件工程：在大型的软件开发中，引入工程管理的一整套的管理方法，对软件开发过程进行规划、设计、监控和检测，以确保开发的过程、开发时间和软件质量都在人的控制管理之下，从而使软件开发的顺利进行。所以，对软件开发过程和软件质量的管理、监控的方法措施就构成了软件工程学。,70,a,软件工程软件工程：在大型的软件开发中，引入工程管理的一整套的,程序设计理论,程序设计理论：通过对程序设计的各种问题进行了系统研究，进行了规范总结，如在程序设计中的自顶向下逐步求精的程序设计方法，自底向上的程序设计方法、程序推导的设计方法、程序变换的设计方法、函数式程序设计技术、逻辑程序设计技术、面向对象的程序设计、程序验证技术、约束程序设计技术和并发程序设计技术等，一系列规范的，好的程序开发方法、形成了丰富的程序设计理论，极大地推进了程序设计技术的发展。,71,a,程序设计理论 程序设计理论：通过对程序设计的各种问题进行了系,本章任务：,1.你认为什么是程序和程序设计？用实际生活的例子说明。2.论述一下软件的生命周期。3、查阅资料：请你通过互联网或者书籍文献查找“计算机语言”相关内容。,72,a,本章任务：1.你认为什么是程序和程序设计？用实际生活的例子,本章任务：,4、思考题：P117 1-35、讨论:围绕以下问题，组织学生分组讨论，然后让每组代表阐述他们的看法和思想。(1)怎样养成良好的算法思想？(2)如何成为一个优秀的程序开发人员？(3)学习良好的软件开发习惯。(4)软件工程的功能及应用。(5)如何学好一门基本的编程语言。4、撰写小论文：解析软件工程流程与方法。,73,a,本章任务：4、思考题：P117 1-373a,