第二章-程序的灵魂——算法.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * ◆算法描述语言：是为了说明程序的流程而专门规定的某种语言。它一般介于自然语言与程序设计语言之间，它具有自然语言灵活的特点，同时又接近于程序设计语言的描述。 ◆注意：算法描述语言所描述的流程，一般不能直接作为程序来使用，最后还需转换成用某种程序设计语言所描述的程序。 ◆与程序设计语言的区别： 前者比较自由，不象后者那样受语法的约束，只要描述得人们能理解就行，而不必考虑计算机处理时所要遵循的规定或其它一些细节。 算法描述语言 在程序设计过程中，一般不可能在一开始就用某种程序设计语言编制计算机程序，而是先用某种简单、直观、灵活的描述工具来描述处理问题的流程。当方案确定以后，再将这样的流程转换成计算机程序，这种转换往往是机械的，已经不涉及功能的重新设计或控制流程的变化，而只需考虑程序设计语言所规定的语法要求以及一细节问题。 一、流程的描述 2.4.2 用流程图表示算法 流程图：用一些约定的几何图形来描述算法。用某种图框表示某种操作，用箭头表示算法流程 ★流程图（的符号及意义）美国标准化协会ANSI规定了一些常用的流程图符号，已为世界各国程序工作者普遍采用： 启止框 输入输出框 判断选择框 处理框 流程线 连接点 …… 注释框 l起止框：表示算法的开始和结束。一般内部只写“开始”或“结束”。 l 处理框：表示算法的某个处理步骤，一般内部常常填写赋值操作。 l输入输出框：表示算法请求输入输入需要的数据或算法将某些结果输出。一般内部常常填写“输入…”,“打印/显示…” l菱形框（判断框）：作用主要是对一个给定条件进行判断，根据给定的条件是否成立来决定如何执行其后的操作。它有一个入口，两个出口。 l连接点：用于将画在不同地方的流程线连接起来。同一个编号的点是相互连接在一起的，实际上同一编号的点是同一个点，只是画不下才分开画。使用连接点，还可以避免流程线的交叉或过长，使流程图更加清晰。 l注释框：注释框不是流程图中必须的部分，不反映流程和操作，它只是对流程图中某些框的操作做必要的补充说明，以帮助阅读流程图的人更好地理解流程图的作用。 例： 求5！ t=1 i=2 t=t*i i=i+1 i5 结束 N Y 开始 传统流程图采用流程线指出各框的执行顺序，对流程线的使用没有严格限制。因此，使用者可以不受限制地使流程转来转去，使流程图变得毫无规律。人们对这种流程图进行改进，规定几种基本的结构，然后由这些基本结构按一定规律组成算法结构，整个算法结构是由上而下地将各个基本结构顺序排列起来。这样可以在一定程度上，提高算法的质量。 ★三种基本结构是： （1）顺序结构 按指令的顺序依次执行 （2）判断选择结构： 根据判别条件有选择地改变 执行流程 （3）循环结构： 有条件的重复地执行某个程序块 2.4.3 三种基本结构和改进的流程图 (1)顺序结构程序设计 依次顺序执行程序语句 执行a块 执行b块 a块 b块 A B 例如，令a、b的值 分别为5、10； a = 5； b = 10； (2)判别选择结构程序设计 首先判别条件，若条件满足，程序执行a块，否则，执行b块； 举例，求a、b两个 数中的最大值； 满足条件否 满足 不满足 执行a块 执行b块 条件成立？ 执行a块 执行b块 成立 不成立 b max？ Max = a； max = b； Y N (3)循环结构程序设计 循环又分“当型循环”和“直到型循环” 举例，求1~100的累加和。 int i，sum=0； while（i =100) { sum=sum+i; i=i+1; } 直到条件满足为止 执行循环中的指令 当条件满足时 执行循环中指令 i=100？ sum=sum+i; i=i+1; Y sum=0; N 三种基本结构，有以下共同点： l?只有一个入口：不得从结构外随意转入结构中某点。 l?只有一个出口：不得从结构内某个位置随意转出（跳出）。 l?结构中的每一部分都有机会被执行到。（没有“死语句”） l?结构内不存在“死循环”（无终止的循环） 已经证明：由三种基本结构顺序组成的算法结构，可以解决任何复杂问题。由基本结构组成的算法属于“结构化”算法。 2.4.4 用N-S流程图表示算法 基本结构的顺序组合可以表示任何复杂的算法结构，那么，基本结构之间的流程线就属于多余的了，于是美国学者I.Nasii和B.shneiderman 于1973年提出了一种新的流程图形式。 全部算法写