第四章 算法、程序与编程问题的提出：人是如何来处理问题的？人是如何处理复杂问题的？计算机如何来处理问题的？问题的处理计算机算法、程序与编程第四章 算法、程序与编程学习目的和要求：了解算法与程序概念了解算法的复杂性与NP问题熟习根本算法知道数据和数据构造熟习高级言语掌握程序设计规划了解程序实际和软件工程 一种逐渐处理问题或完成义务的方法一种逐渐处理问题或完成义务的方法输入列表输入列表输出列表输出列表算法算法寻觅最大值的一个算法(1)输入5个数，输出其中的最大值1.输入：算法接受一组5个整数的数据。2.过程第一步 检查第一个整数，把这个整数赋给变量Largest第二步 把第二个数与Largest中的数进展比较，如大于Largest中的数就将该数赋予它，否那么，Largest中的数不变第三步 把第三个数与Largest中的数进展比较，如大于Largest中的数就将该数赋予它，否那么，Largest中的数不变。此时13大于12，所以，变量Largest中变为13。 寻觅最大值的一个算法(2)第四步第四步 把第四个数与把第四个数与Largest中的数进展比较，中的数进展比较，如大于如大于Largest中的数就将该数赋予它，否那中的数就将该数赋予它，否那么，么，Largest中的数不变。此时第四个数是中的数不变。此时第四个数是9，小于，小于13，所以，所以Largest中的数不变。中的数不变。第五步第五步 把第四五个数与把第四五个数与Largest中的数进展比中的数进展比较，如大于较，如大于Largest中的数就将该数赋予它，中的数就将该数赋予它，否那么，否那么，Largest中的数不变。此时第五个数中的数不变。此时第五个数是是11，小于，小于13，所以，所以Largest中的数不变。中的数不变。3.输出输出 最大值最大值13 终了终了算法的例子表示图算法的精化算法的泛化三三 种种 结结 构构 算法的根本构造算法的根本构造 流程图算法的表示算法的表示算法的表示算法的表示伪代码：是在编写算法时，为了更好地表示算法本身，不在一些小的细节上纠缠，而采用类似于英语或其他自然言语表示算法的算法表示方法。伪代码用伪代码写出一个求两个数的平均值的算法例例1AverageOfTwoInput: Two numbersAdd the two numbersDivide the result by 2Return the result by step 2EndAlgorithm 8.1:Average of twoPass/NoPassGradeInput: One numberif (the number is greater than or equal to 60)then 1.1 Set the grade to “passelse 1.2 Set the grade to “nopassEnd ifReturn the gradeEndAlgorithm 8.2:Pass/no pass Grade 用伪代码写出一个可以把不同数值成果分成及格或不及格的算法例例2LetterGradeInput: One number1. if (the number is between 90 and 100, inclusive)then 1.1 Set the grade to “AEnd if2. if (the number is between 80 and 89, inclusive)then 2.1 Set the grade to “BEnd ifAlgorithm 8.3:Letter grade 用伪代码写出一个可以把数字型成果变成字母等级成果的算法例例3Algorithm :Letter grade (continued)Continues on the next slide3. if (the number is between 70 and 79, inclusive)then 3.1 Set the grade to “CEnd if4. if (the number is between 60 and 69, inclusive)then 4.1 Set the grade to “DEnd if算法的定义算法定义1：算法是一组明确步骤的有序集合，它产生结果，并在有限的时间内终止。有序集合明确步骤产生结果在有限的时间内终了算法定算法定义2：1给定定问题和和设备，一个算法是用，一个算法是用该设备可了可了解的言解的言语表示的，表示的，处理理这个个问题的一种方法是准确的一种方法是准确描写。特描写。特别地，算法具有以下特征属性：地，算法具有以下特征属性： 算法运用于一个算法运用于一个详细的的输入集合或入集合或问题描画将在描画将在有有穷步步动作之后得到作之后得到结果；果； 该序列有一个独一的初始序列有一个独一的初始动作：作： 该序列中的每一个序列中的每一个动作有一个独一的后作有一个独一的后继动作作 该序列序列终止止时或者得到或者得到这个个问题的解，或者因的解，或者因该问题不可解而不可解而获得不可得不可讲解明。解明。算法定义算法定义3：一个算法，就是一个有穷规那么的集：一个算法，就是一个有穷规那么的集合，其中之规那么确定了一个处理某一特定型问题合，其中之规那么确定了一个处理某一特定型问题的运算序列。此外，算法的规那么序列必需满足以的运算序列。此外，算法的规那么序列必需满足以下下5个重要条件，即具有以下五个特性：个重要条件，即具有以下五个特性：1有穷性。算法必需总是在执行有穷步之后终有穷性。算法必需总是在执行有穷步之后终了了2确定性。算法的每一个步骤必需是确切地定确定性。算法的每一个步骤必需是确切地定义的；义的；3输入。算法有零个或多个输入输入。算法有零个或多个输入4输出。算法有一个或多个输出，即与输入有输出。算法有一个或多个输出，即与输入有某个关系的量。某个关系的量。5能行性。算法中有待执行的运算和操作必需能行性。算法中有待执行的运算和操作必需是相当根本的，即是说，它们原那么上是可以准确是相当根本的，即是说，它们原那么上是可以准确地进展的，而且用笔和纸做有穷次就可以完成。地进展的，而且用笔和纸做有穷次就可以完成。计计算的复算的复算的复算的复杂杂性与性与性与性与NPNP问题问题计算的复杂性算法的复杂性的概念计算的复杂性算法的复杂性的概念计算空间的复杂性计算空间的复杂性计算时间的复杂性计算时间的复杂性类似性与对偶原理：计算空间与计算时间的互换性类似性与对偶原理：计算空间与计算时间的互换性算法复杂性的描画：算法在执行过程中总共所需求的算法复杂性的描画：算法在执行过程中总共所需求的初等运算的步数来表示算法用于求解任一问题的某一初等运算的步数来表示算法用于求解任一问题的某一例子时所需的时间。例子时所需的时间。计算的复杂性与NP问题2算法复杂性的表示多项式时间算法：是指存在某个以输入长度n为变量的多项式函数中(n)，使其时间复杂性函数为O(p(n)的算法。因此复杂性为O(n)、O(106n3)、O(5n8)等算法均为多项式时间算法。指数时间算法：是指任何其时间复杂性函数不能够如上用多项式函数去界定的算法，例如O2n、O(n!)、O(nn)、O(2n2)等都在算法上是不可接受的。计算的复杂性与NP问题3时间复杂性的表示O1称为常数级；Ologn称为对数级；On称为线性级；O (nc)称为多项式级，C为常数； O Cn称为指数级，C为常数；O (n!)称为阶乘级；计算的复杂性与NP问题4P类与类与NP类问题：一个算法假设存在图灵机可计算的类问题：一个算法假设存在图灵机可计算的多项式时间计算复杂性算法，就将该算法归入多项式时间计算复杂性算法，就将该算法归入P类；假类；假设存在非确定性图灵机可计算的多项式时间计算复杂设存在非确定性图灵机可计算的多项式时间计算复杂性算法，就将其归入性算法，就将其归入NP类。类。 P=NP?构造图构造图：是程序员运用的高层设计工具。构造图能很好地表示程序设计者的逻辑思想的过程；把算法中各个模块之间的关系表示的更加清楚。构造图的常用图标：构造图的常用图标：递递 归归、迭代与分治算法、迭代与分治算法、迭代与分治算法、迭代与分治算法递归、迭代算法：递归算法是算法自我调用的过程。迭代的定义：算法中没有包含算法本身，只是 利用上一步计算的结果得出最后答案的算法递归的定义：算法中包含了算法本身的调用的 算法。分治算法：就是将一个难以直接处理的大问题，经过分析，分解为一些规模较小的一样问题，进而对各个小问题进展处理，最后到达整个问题的处理。迭代算法的例子递归算法的例子递归算法中递归调用表示图Iterative factorialIterative factorialFactorialInput: 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迭代算法迭代算法FactorialInput: A positive integer numif (num is equal to 0)then 1.1 return 1else1.2 return num x Factorial (num 1) End ifEndRecursive factorialRecursive factorial递归算法递归算法数据与数据构造数据与数据构造数据与数据构造数据与数据构造简简介介介介简单数据构造类型：表41 简单数据类型数据与数据构造简介2数据构造：二元组 Data-structure=(D,R),称为数据D的数据构造。其中D为数据元素的集合，R是D上关系的集合。根本数据构造数组(Array)一维数组二维数组2.Two-dimensional array(二维数组二维数组)记录：是一组相关元素的集合，它们能够是不同类型的，但整个记录是相关的，有一个一致的称号。域：具有含义的记录中命名数据的最小元素；它可以有类型且存在于内存中；它能被赋值，也可以被选择和操作。它与变量不同之处在于它是记录的一个部分。数组与记录的区别：数组中的元素必需是同一类型，而记录中的元素那么可以一样或不同类型，只需相关即可。在设计记录时记录中的数据必需都与一个对象关联。记录中的元素可以是一中的元素可以是一样或不一或不一样的的类型，但型，但记录中的一切元素必需是相关的中的一切元素必需是相关的记录的操作的操作访问记录 访问单个域个域 访问整个整个记录读入入写入写入记录成成员Linked lists链表链表链表：是一个有序的集合，其中每一个元素都包含链表：是一个有序的集合，其中每一个元素都包含 下一个元素的地址；即数据和指针地址。下一个元素的地址；即数据和指针地址。几个典型的常用的笼统数据类型线性列表Linear list 线性列表的操作 1插入 2删除 3检索 4遍历Insertion in a linear listDeletion from a linear list栈栈是一种限制性列表，对其的操作添加、删除只能在一端实现。(LIFO)Three representations of a stack栈的操作入栈出栈空Push operation in a stackPop operation in a stack队列队列是一种线性列表，对其的操作只能从一端进入，另一端删除。只能按存入的顺序进展处置。(FIFO)树节点：组成树的有限的元素。节点：组成树的有限的元素。分支：衔接各节点的有向或无向线段。分支：衔接各节点的有向或无向线段。度：与节点衔接的分支的数目。有出度和入度之度：与节点衔接的分支的数目。有出度和入度之分，指向节点的称入度，分开节点的称出度。分，指向节点的称入度，分开节点的称出度。Subtrees二叉树二叉树二叉树的前序遍历二叉树的前序遍历二叉树的后序遍历二叉树的广度优先遍历数组方式AFCEDB概念性的树实践的存储构造这种存储方式在二叉树不是平衡的情况下会浪费存储空间二叉树的运用网络最小生成树衔接一切节点的最短途径图图的运用网络最小生成树高级程序设计言语程序设计言语开展的历史机器言语汇编言语高级言语计算机言语过程化言语FORTRANCOBOLPascalCAda阐明性言语PROLOG公用言语HTMLXMLSQL PERL函数型言语LISPSchenme面向对象言语C+JavaVC+程序的构建编程与执行程序编写编辑程序链接程序文本编写编译程序链接程序程序系统库程序的执行预处置程序编译翻译程序程序规划与设计程序规划与设计(1)程序程序规划划步步骤1:分析分析问题并制定概要并制定概要设计方案。方案。编程人程人员必必需需对问题有完全、准确的了解，用准确的言有完全、准确的了解，用准确的言语对问题进展描画，主要思索以下几个方面；展描画，主要思索以下几个方面；问题的的输入是什么？知的是什么？入是什么？知的是什么？还要要给什么，什么，运用什么格式。运用什么格式。期望的期望的输出是什么？需求什么出是什么？需求什么类型的型的报告、告、图表或信息。表或信息。从从给定的定的输入到期望的入到期望的输出，必要的出，必要的处置步置步骤是什么？是什么？步步骤2:制定制定详细设计：算法：算法设计必需制定一必需制定一组准确的步准确的步骤，即，即编写提写提纲。这些步些步骤应该是明确、是明确、详细和有限的，并能在合理的和有限的，并能在合理的时间内完成；同内完成；同时选定定实现各步各步骤的言的言语。程序规划与设计程序规划与设计(2)步步骤3:用用编程言程言语编写程序代写程序代码及其文档。及其文档。在步在步骤2中越中越详细清楚用程序代清楚用程序代码就越容易。就越容易。在用程序代在用程序代码“翻翻译的的过程一定要准确、程一定要准确、完好。特完好。特别是是对文档的文档的编写，写，对各条各条语句功句功能的注能的注释，往往会被忽，往往会被忽视，现代代编程是一种程是一种团体的体的协作行作行为，让他人能容易地看懂他的他人能容易地看懂他的程序，程序，对整个系整个系统的的编写是写是绝对必要的。同必要的。同时对程序的修正程序的修正维护都有很大的都有很大的协助。助。程序规划与设计程序规划与设计(3)步骤步骤4:测试程序：这是一个在前几个步骤进测试程序：这是一个在前几个步骤进展过程中一个不断反复的过程。对于编写出展过程中一个不断反复的过程。对于编写出来的每一部分代码，都应该进展测试，以确来的每一部分代码，都应该进展测试，以确保程序运转的正确性。保程序运转的正确性。步骤步骤5:验证程序：一旦程序编写完并进展一验证程序：一旦程序编写完并进展一定的测试后，就应该经过大范围的测试来验定的测试后，就应该经过大范围的测试来验证。验证时必需根据用户的要求，不断进展证。验证时必需根据用户的要求，不断进展修正调整到用户称心为止。修正调整到用户称心为止。程序规划与设计程序规划与设计(4)程序设计和调试程序设计和调试养成良好的编程风格养成良好的编程风格错误定位设计错误修复程序错误修复程序重测软件工程软件工程：在大型的软件开发中，引入软件工程：在大型的软件开发中，引入工程管理的一整套的管理方法，对软件工程管理的一整套的管理方法，对软件开发过程进展规划、设计、监控和检测，开发过程进展规划、设计、监控和检测，以确保开发的过程、开发时间和软件质以确保开发的过程、开发时间和软件质量都在人的控制管理之下，从而使软件量都在人的控制管理之下，从而使软件开发的顺利进展。所以，对软件开发过开发的顺利进展。所以，对软件开发过程和软件质量的管理、监控的方法措施程和软件质量的管理、监控的方法措施就构成了软件工程学。就构成了软件工程学。程序设计实际程序设计实际 程序设计实际：经过对程序设计的各种问题进程序设计实际：经过对程序设计的各种问题进展了系统研讨，进展了规范总结，如在程序设展了系统研讨，进展了规范总结，如在程序设计中的自顶向下逐渐求精的程序设计方法，自计中的自顶向下逐渐求精的程序设计方法，自底向上的程序设计方法、程序推导的设计方法、底向上的程序设计方法、程序推导的设计方法、程序变换的设计方法、函数式程序设计技术、程序变换的设计方法、函数式程序设计技术、逻辑程序设计技术、面向对象的程序设计、程逻辑程序设计技术、面向对象的程序设计、程序验证技术、约束程序设计技术和并发程序设序验证技术、约束程序设计技术和并发程序设计技术等，一系列规范的，好的程序开发方法、计技术等，一系列规范的，好的程序开发方法、构成了丰富的程序设计实际，极大地推进了程构成了丰富的程序设计实际，极大地推进了程序设计技术的开展。序设计技术的开展。 本章义务：1. 他以为什么是程序和程序设计？用实践生活的例子阐明。2.论述一下软件的生命周期。3、查阅资料：请他经过互联网或者书籍文献查找“计算机言语相关内容。本章义务：4、思索题：P117 1-35、讨论: 围绕以下问题，组织学生分组讨论，然后让每组代表论述他们的看法和思想。(1)怎样养成良好的算法思想？(2)如何成为一个优秀的程序开发人员？(3)学习良好的软件开发习惯。(4)软件工程的功能及运用。(5)如何学好一门根本的编程言语。4、撰写小论文：解析软件工程流程与方法。