程序设计基础第六章ppt课件.ppt

《程序设计基础第六章ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法和问题求解第六章算法与问题求解算法是程序的核心算法的描述算法设计中的基本方法算法设计的要求与评价6.1算法是程序的核心—算法的概念算法用于求解某个特定问题的一些指令的集合。即用计算机所能实现的操作或指令来描述问题的求解过程，就是这一特定问题的计算机算法。算法设计的任务找到尽快解决问题的办法。6.1算法是程序的核心—算法的性质有穷性算法必须在执行了有限的步骤之后结束。确定性算法的每一步必须有确切地定义，不允许有二义性出现。可行性对于算法的每一步，指令必须是可执行的。输入性算法必须有零个或多个的输入。输出性算法必须有一个或多个的输入。

2、6.1算法是程序的核心—算法、数据结构与程序设计算法与程序设计算法是程序设计的核心。算法设计是人类智慧的结晶，计算机科学中的知识创新，主要就是算法的创新。数据结构与程序设计程序设计中，数据的组织和存储会直接影响算法的实现方式和效率。程序设计与程序设计方法程序设计方法影响程序设计的成败与质量。6.1算法是程序的核心—算法的操作与控制算法的操作计算机最基本的功能操作有：1)逻辑运算2)算术运算3)数据比较4)数据传送算法的操作就是将问题的实现通过这四种操作形式组合来实现。在算法分析与算法设计阶段，不用关心计算机的具体特性，不用

3、考虑算法在某类型计算机上的具体实现方式。算法的控制结构操作的执行顺序是算法的重要组成部分，算法的控制结构给出算法的执行框架，决定算法中各种操作的执行顺序。1)顺序结构最基本的控制结构，从算法入口开始到算法出口结束，算法操作顺序执行，具有单入单出性质。2)选择结构通过逻辑或关系表达式结果，算法有选择地执行相应的操作，进行条件分支。选择结构也具有单入单出性质，而且是开放型的。可分为：单选结构、双选结构和多选结构。3)循环结构算法中某组操作要求执行多次时采用的结构。具有单入单出性质，但它是封闭型的。可分为：先判断后执行先执行后判断

4、6.2算法的描述算法描述形式算法的描述形式可以归结为两类：1、文字描述常用的文字描述形式有自然语言和伪码。2、图形描述常用的图形描述形式有流程图和N-S图等6.2算法的描述——自然语言自然语言用自然语言对算法进行描述，就是使用日常语言进行描述。最大特点就是通俗易懂，容易掌握；但与计算机语言差距大，且容易出现二义性，不容易表达分支与循环。下例用自然语言描述1到n(n<=1000)的累加。S1：输入n(要求n<=1000);S2：累加和sum置初值0;S3：自然数i置初值1;S4：若i<=n，则重复执行：S41：i+

5、sum—>sum;S42：i+1—>i;S5：输出sum，结束。6.2算法的描述——伪代码伪代码伪代码是一种介于自然语言与计算机语言之间的算法描述方法。它结构性较强，比较容易书写和理解，修改起来也相对方便。其特点是不拘泥于语言的语法结构，而着重以灵活的形式表现被描述对象。它利用自然语言的功能和若干基本控制结构来描述算法。伪代码没有统一的标准，可以自己定义，也可以采用与程序设计语言类似的形式。6.2算法的描述——传统流程图流程图流程图也叫框图，它是用各种几何图形、流程线及文字说明来描述计算过程的框图。用流程图描述算法的优点是：直

6、观，设计者的思路表达得清楚易懂，便于检查修改。用流程图描述算法的缺点是：严密性不如程序设计语言，描述的灵活性不如自然语言。流程图常用符号处理框(过程框)：描述基本操作功能数据输入/输出框两分支判断框：判断框中条件是否满足开始/结束框连接符：连接图中不同位置的流程线流程线：表示流程的路径和方向12……n多分支判断框注释框用流程图描述算法应注意1、应根据解决问题的步骤从上至下顺序地画出流程图，各图框中的文字要尽量简洁。2、为避免流程图的图形显得过长，图中的流程线要尽量短。3、用流程图描述算法时，流程图的描述可粗可细，总的原则是：根据

7、实际问题的复杂性，流程图达到的最终效果应该是，依据此图就能用某种程序设计语言实现相应的算法（即完成编程）。流程图描述算法示例输入整数（输入0表示停止输入），分别计算输入的正整数和负整数之和。Start0->sum1,sum2输入整数aa==0sum1+=aNa>0sum2+=a输入整数aYYN输出结果End6.2算法的描述——N-S结构化流程图N-S流程图N-S结构化流程图主要特点是取消了流程线，全部算法由一些基本的矩形框图顺序排列组成一个大矩形表示，即不允许程序任意转移，而只能顺序执行，从而使程序结构化。N-S流程图对基本控制结构的

8、描述S1S2顺序结构选择结构TF条件S2S1循环结构直到条件满足S1当条件满足S1N-S流程图描述算法示例输入一个正整数m，判断是否为素数。（若m不能被2~sqrt(m)之间的数整除，则m是素数。）读入mk=sqrt(m