算法程序与编程

第四章算法、程序与编程问题的提出：人是如何来解决问题的？人是如何解决复杂问题的？计算机如何来解决问题的？问题的解决——计算机算法、程序与编程第四章算法、程序与编程学习目的和要求：了解算法与程序概念理解算法的复杂性与NP问题熟悉基本算法知道数据和数据结构熟悉高级语言掌握程序 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 规划了解程序理论和软件 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 一种逐步解决问题或完成任务的方法输入列表输出列表算法寻找最大值的一个算法(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:TwonumbersAddthetwonumbersDividetheresultby2Returntheresultbystep2EndAlgorithm8.1:AverageoftwoPass/NoPassGradeInput:Onenumberif(thenumberisgreaterthanorequalto60)then1.1Setthegradeto“pass”else1.2Setthegradeto“nopass”EndifReturnthegradeEndAlgorithm8.2:Pass/nopassGrade用伪代码写出一个可以把不同数值成绩分成及格或不及格的算法例2LetterGradeInput:Onenumber1.if(thenumberisbetween90and100,inclusive)then1.1Setthegradeto“A”Endif2.if(thenumberisbetween80and89,inclusive)then2.1Setthegradeto“B”EndifAlgorithm8.3:Lettergrade用伪代码写出一个可以把数字型成绩变成字母等级成绩的算法例3Algorithm:Lettergrade(continued)Continuesonthenextslide3.if(thenumberisbetween70and79,inclusive)then3.1Setthegradeto“C”Endif4.if(thenumberisbetween60and69,inclusive)then4.1Setthegradeto“D”Endif算法的定义算法定义1：算法是一组明确步骤的有序集合，它产生结果，并在有限的时间内终止。有序集合明确步骤产生结果在有限的时间内结束算法定义2：（1）给定问题和设备，一个算法是用该设备可理解的语言表示的，解决这个问题的一种方法是精确刻画。特别地，算法具有以下特征属性：①算法应用于一个具体的输入集合或问题描述将在有穷步动作之后得到结果；②该序列有一个唯一的初始动作：③该序列中的每一个动作有一个唯一的后继动作④该序列终止时或者得到这个问题的解，或者因该问题不可解而获得不可解说明。算法定义3：一个算法，就是一个有穷规则的集合，其中之规则确定了一个解决某一特定型问题的运算序列。此外，算法的规则序列必须满足以下5个重要条件，即具有以下五个特性：（1）有穷性。算法必须总是在执行有穷步之后结束（2）确定性。算法的每一个步骤必须是确切地定义的；（3）输入。算法有零个或多个输入（4）输出。算法有一个或多个输出，即与输入有某个关系的量。（5）能行性。算法中有待执行的运算和操作必须是相当基本的，即是说，它们原则上是能够精确地进行的，而且用笔和纸做有穷次就可以完成。计算的复杂性与NP问题计算的复杂性（算法的复杂性）的概念计算空间的复杂性计算时间的复杂性相似性与对偶原理：计算空间与计算时间的互换性算法复杂性的描述：算法在执行过程中总共所需要的初等运算的步数来表示算法用于求解任一问题的某一例子时所需的时间。计算的复杂性与NP问题（2）算法复杂性的表示多项式时间算法：是指存在某个以输入长度n为变量的多项式函数中(n)，使其时间复杂性函数为O(p(n))的算法。因此复杂性为O(n)、O(106n3)、O(5n8)等算法均为多项式时间算法。指数时间算法：是指任何其时间复杂性函数不可能如上用多项式函数去界定的算法，例如O（2n）、O(n!)、O(nn)、O(2n2)等都在算法上是不可接受的。计算的复杂性与NP问题（3）时间复杂性的表示·O（1）称为常数级；·O（logn）称为对数级；·O（n）称为线性级；·O(nc)称为多项式级，（C为常数）；·O（Cn）称为指数级，（C为常数）；·O(n!)称为阶乘级；计算的复杂性与NP问题（4）P类与NP类问题：一个算法如果存在图灵机可计算的多项式时间计算复杂性算法，就将该算法归入P类；如果存在非确定性图灵机可计算的多项式时间计算复杂性算法，就将其归入NP类。P=NP?结构图结构图：是程序员使用的高层设计工具。结构图能很好地表示程序设计者的逻辑思维的过程；把算法中各个模块之间的关系表示的更加清楚。结构图的常用图标：递归、迭代与分治算法递归、迭代算法：递归算法是算法自我调用的过程。迭代的定义：算法中没有包含算法自身，只是利用上一步计算的结果得出最后答案的算法递归的定义：算法中包含了算法自身的调用的算法。分治算法：就是将一个难以直接解决的大问题，通过 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ，分解为一些规模较小的相同问题，进而对各个小问题进行解决，最后达到整个问题的解决。迭代算法的例子递归算法的例子递归算法中递归调用示意图IterativefactorialFactorialInput:ApositiveintegernumSetFactNto0SetitoIwhile(iislessthanorequaltonum)3.1SetFactNtoFactNxI3.2IncrementiEndwhileReturnFactNEnd迭代算法FactorialInput:Apositiveintegernumif(numisequalto0)then1.1return1else1.2returnnumxFactorial(num–1)EndifEndRecursivefactorial递归算法数据与数据结构简介简单数据结构类型：表4—1简单数据类型数据与数据结构简介（2）数据结构：二元组Data-structure=(D,R),称为数据D的数据结构。其中D为数据元素的集合，R是D上关系的集合。基本数据结构数组(Array)一维数组二维数组…2.Two-dimensionalarray(二维数组)记录：是一组相关元素的集合，它们可能是不同类型的，但整个记录是相关的，有一个统一的名称。域：具有含义的记录中命名数据的最小元素；它可以有类型且存在于内存中；它能被赋值，也能够被选择和操作。它与变量不同之处在于它是记录的一个部分。数组与记录的区别：数组中的元素必须是同一类型，而记录中的元素则可以相同或不同类型，只要相关即可。在设计记录时记录中的数据必须都与一个对象关联。记录中的元素可以是相同或不相同的类型，但记录中的所有元素必须是相关的记录的操作访问记录·访问单个域·访问整个记录读入\写入记录（成员）Linkedlists（链表）链表：是一个有序的集合，其中每一个元素都包含下一个元素的地址；即数据和指针（地址）。几个典型的常用的抽象数据类型线性列表（Linearlist）线性列表的操作（1）插入（2）删除（3）检索（4）遍历InsertioninalinearlistDeletionfromalinearlist栈栈是一种限制性列表，对其的操作添加、删除只能在一端实现。(LIFO)Threerepresentationsofastack栈的操作入栈出栈空PushoperationinastackPopoperationinastack队列队列是一种线性列表，对其的操作只能从一端进入，另一端删除。只能按存入的顺序进行处理。(FIFO)树节点：组成树的有限的元素。分支：连接各节点的有向（或无向）线段。度：与节点连接的分支的数目。有出度和入度之分，指向节点的称入度，离开节点的称出度。Subtrees二叉树二叉树的前序遍历二叉树的后序遍历二叉树的广度优先遍历数组形式AFCEDB概念性的树实际的存储结构这种存储形式在二叉树不是均衡的情况下会浪费存储空间二叉树的应用网络最小生成树（连接所有节点的最短路径）图图的应用网络最小生成树高级程序设计语言程序设计语言发展的历史机器语言汇编语言高级语言计算机语言过程化语言FORTRANCOBOLPascalCAda说明性语言PROLOG专用语言HTMLXMLSQLPERL函数型语言LISPSchenme面向对象语言C++JavaVC++程序的构建（编程）与执行程序编写编辑程序链接程序文本编写编译程序链接程序程序系统库程序的执行预处理程序编译\翻译程序程序规划与设计(1)程序规划步骤1:分析问题并制定概要设计方案。编程人员必须对问题有完全、准确的了解，用准确的语言对问题进行描述，主要考虑以下几个方面；·问题的输入是什么？已知的是什么？还要给什么，使用什么格式。·期望的输出是什么？需要什么类型的报告、图表或信息。·从给定的输入到期望的输出，必要的处理步骤是什么？步骤2:制定详细设计：（算法设计）必须制定一组精确的步骤，即编写提纲。这些步骤应该是明确、详细和有限的，并能在合理的时间内完成；同时选定实现各步骤的语言。程序规划与设计(2)步骤3:用编程语言编写程序代码及其文档。在步骤2中越详细清楚用程序代码就越容易。在用程序代码“翻译”的过程一定要准确、完整。特别是对文档的编写，对各条语句功能的注释，往往会被忽视，现代编程是一种团体的合作行为，让别人能容易地看懂你的程序，对整个系统的编写是绝对必要的。同时对程序的修改维护都有很大的帮助。程序规划与设计(3)步骤4:测试程序：这是一个在前几个步骤进行过程中一个不断重复的过程。对于编写出来的每一部分代码，都应该进行测试，以确保程序运行的正确性。步骤5:验证程序：一旦程序编写完并进行一定的测试后，就应该通过大范围的测试来验证。验证时必须根据用户的要求，不断进行修改调整到用户满意为止。程序规划与设计(4)程序设计和调试养成良好的编程风格错误定位设计错误修复程序错误修复程序重测软件工程软件工程：在大型的软件开发中，引入工程管理的一整套的管理方法，对软件开发过程进行规划、设计、监控和检测，以确保开发的过程、开发时间和软件质量都在人的控制管理之下，从而使软件开发的顺利进行。所以，对软件开发过程和软件质量的管理、监控的方法 措施 《全国民用建筑工程设计技术措施》规划•建筑•景观全国民用建筑工程设计技术措施》规划•建筑•景观软件质量保证措施下载工地伤害及预防措施下载关于贯彻落实的具体措施 就构成了软件工程学。程序设计理论程序设计理论：通过对程序设计的各种问题进行了系统研究，进行了规范总结，如在程序设计中的自顶向下逐步求精的程序设计方法，自底向上的程序设计方法、程序推导的设计方法、程序变换的设计方法、函数式程序设计技术、逻辑程序设计技术、面向对象的程序设计、程序验证技术、约束程序设计技术和并发程序设计技术等，一系列规范的，好的程序开发方法、形成了丰富的程序设计理论，极大地推进了程序设计技术的发展。本章任务：1.你认为什么是程序和程序设计？用实际生活的例子说明。2.论述一下软件的生命周期。3、查阅资料：请你通过互联网或者书籍文献查找“计算机语言”相关内容。本章任务：4、思考题：P1171-35、讨论:围绕以下问题，组织学生分组讨论，然后让每组代表阐述他们的看法和思想。(1)怎样养成良好的算法思想？(2)如何成为一个优秀的程序开发人员？(3)学习良好的软件开发习惯。(4)软件工程的功能及应用。(5)如何学好一门基本的编程语言。4、撰写小论文：解析软件工程流程与方法。