资源描述
2.1 算法的概念 2.2 简单算法举例 2.3 算法的特性 2.4 怎样表示一个算法 2.5 结构化程序设计方法 ,第2章 程序的灵魂算法,程 序 包 括 对数据的描述 指定数据的类型、组织形式，即数据结构。 对操作的描述 即操作步骤，也称算法(algorithm)。 著名计算机科学家沃思(Nikilaus Wirth)提出：,程 序 设 计 包 括 采用某种程序设计方法 使用某种计算机语言工具,程序设计人员所应具备和综合运用的知识,算法,加工对象,设计方法,设计工具,为解决问题而采取的方法和步骤，称为“算法”。 尽量采用简单、有效的算法。,保证算法正确 考虑算法的质量,本书所考虑的只限于计算机能执行的算法。,算 法 必 备 条 件：,2.1 算 法 的 概 念,计算机算法分两类： 数值算法（目的是求数值解） 有比较成熟的算法可供选用。 常常把这些算法汇编成册(写成程序形式)，或者将这些程序存放在磁盘或磁带上，供用户调用。,非数值算法（常用于事务管理领域）,涵盖面很广：计算机在非数值运算方面的应用远多于在数值运算方面的应用。难以规范化，只能对一些典型的算法作比较深入的研究。,2.1 算 法 的 概 念,算 法 一： 步骤1： 先求12，得到2。 步骤2： 将得到的2再乘以3，得到6。 步骤3： 将6再乘以4，得到24。 步骤4： 将24再乘以5，得到120。 算法虽然正确，但太繁琐。 每次都直接使用上一步骤的数值结果，不方便。应找到 一种通用的表示方法。,例2.1 求12345。,2.2 简单算法举例,设两个变量：变量p代表被乘数，变量i代表乘数。 将每一步的乘积放在被乘数变量p中，算法改写如下： S1： 使p=1 S2： 使i=2 S3： 使pi，乘积放在p中（pi=p） S4： 使i的值加1（i+1 = i） S5： 若i不大于5，重新执行S3、S4和S5； 否则，算法结束。,算 法 二 ：,计算机的优势 在此得以体现,2.2 简单算法举例,如果题目改为： 求1357999。 则算法二只需作很少改动： S1： 1=p S2： 3=i S3： pi=p S4： i+2=i S5： 若i100，返回S3； 否则，结束。,可见，算法二具有通用性、灵活性，更为简单有效。,2.2 简单算法举例,例2.3 判定20002500年中的每一年是否闰年，将结果输出。 闰 年 的 条 件 ： 能被4整除，但不能被100整除的年份是闰年， 如1996年，2004年； 能被100整除，又能被400整除的年份是闰年， 如1600年、2000年。 不符合这两个条件的年份不是闰年。,2.2 简单算法举例,设 y 为被检测的年份，算法如下： S1：2000=y S2：y不能被4整除，则输出y “不是闰年”，转到S6 S3：若y能被4整除，不能被100整除，则输出y “是闰年”， 转到S6 S4：若y能被100整除，又能被400整除，输出y“是闰年”； 转到S6 S5：输出y “不是闰年” S6：y+1=y S7：当y2500时，转S2继续执行，如y2500，算法停止。,2.2 简单算法举例,图 2.1,图2.1,能被4整除，又能被100整除，而不能被400整除的那些年份 如100，200，1000,如，1600,如，4040,2.2 简单算法举例,一 个 算 法 应 具 有 以 下 特 点： 1.有穷性 一个算法应包含有限步操作。并且还应该“在合理的范围 之内”。究竟什么算“合理限度”，并无严格标准，由人们的 常识和需要而定。 2.确定性 算法中的每一个步骤都应当是确定的，而不应当是含糊的、 模棱两可的。,2.3 算法的特性,3.有零个或多个输入 所谓输入是指在执行算法时需要从外界取得的必要的信息。 一个算法也可以没有输入。 4.有一个或多个输出 算法的目的是为了求解，“解” 就是输出。没有输出的算法 是没有意义的。 5.有效性 算法中的每一个步骤都应能有效地执行，并得到确定的结 果。,2.3 算法的特性,程序员：必须设计算法， 并根据算法编写程序。,普通用户：只需给以必要 的输入，就能得到结果。,2.3 算法的特性,自然语言表示 传统流程图表示 N-S流程图表示 伪代码表示 计算机语言表示（对算法的实现）,2.4 怎样表示一个算法,2.4.1 用自然语言表示算法 优点：通俗易懂 缺点：文字冗长， 容易出现“歧义性”。不方便描述包含分 支和循环的算法。 2.4.2 用流程图表示算法 是指用一些图框来表示算法中的各种操作。 美国国家标准化协会ANSI(American National Standard Institute)规定了一些常用的流程图符号(见图2.3)。,对给定的条件进行判断，根据判断结果决定其后的操作， 单入口，双出口，见图2.4,连接画在不同地方的流程线，避免流程图交叉或过长。见图2.5,常 用 的 流 程 图 符 号,图 2.4 菱形框示意图,图 2.5 连接点示意图,常 用 的 流 程 图 符 号,求5!,流 程 图 举 例,求5!并输出,流 程 图 举 例,判断是否为润年,传统流程图的构成： 操作框 (起止、I/O、判断、处理、注释) 流程线 （箭头表示执行顺序） 文字说明 传统流程图的优缺点： 优点：直观，逻辑关系明确，易于理解。 缺点：占用篇幅多，表示复杂算法时，费时费力。,传统流程图的构成及特点,算法的重要性（4要素之一） 算法的特性（有穷、确定、有效、 0或多个I，1或多个O） 自然语言表示算法 通俗易懂 不方便表示分支和循环 传统流程图表示算法 直观形象 占用篇幅较多,要 点 回 顾,1.传统流程图的弊端 对流程线的使用无限制，使流程毫无规律。如图2.13。 难以保证算法可靠性和可维护性。 那么，如何表示分支和循环这些非顺序的流程呢？ 规定出几种基本结构，顺序排列组成一个算法。,2.4.3 三种基本结构和改进的流程图,图2.13,图2.13,2.4.3 三种基本结构和改进的流程图,2. 三种基本结构 1966，Bohra和Jacopini提出以下三种结构： (1) 顺序结构，图2.14。 (2) 选择结构，又称分支结构，图2.15 。 两个分支中可以有一个是空，图2.16 。 (3) 循环结构，又称重复结构，分两类： 当(While)型循环结构 直到(Until)型循环结构,2.4.3 三种基本结构和改进的流程图,图2.14,Return,顺 序 结 构,图2.15 图2.16,Return,分 支 结 构, 当型(While型)循环 先判断条件p1，当条件p1成立时，执行A，条件 p1不成立时终止循环，见图2.17(a)。 直到型(Until型)循环 先执行A，然后判断条件p2是否成立，当条件p2不 成立时，执行A，条件p2成立时终止循环， 见图2.17(b) 。,循 环 结 构,图2.17（a）,Return,循 环 结 构,图2.17（b）,“当” 型循环的例子: 打印1，2，3，4，5,循 环 结 构,“直到” 型循环的例子: 打印1，2，3，4，5,循 环 结 构,三 种 基 本 结 构 的 特 点 ： 只有一个入口。 只有一个出口。 结构内的每一部分都有机会被执行到。图2.20 结构内不存在“死循环”(无终止的循环)。图2.21,2.4.3 三种基本结构和改进的流程图,菱形判断框,选择结构,图2.20 图2.21,Return,2.4.3 三种基本结构和改进的流程图,由基本结构派生出的基本结构,N-S流程图由三种基本结构顺序组合而成，无流程线。 N-S流程图所用符号：,2.4.4 用N-S流程图表示算法,顺 序 结 构,分 支 结 构,A或B，可以是一个简单操作，也可以是3个基本结构之一。,当 型 循 环 结 构,直 到 型 循 环 结 构,2.4.4 用N-S流程图表示算法,2.4.4 用N-S流程图表示算法,A框：选择结构,B框：循环结构,例2.11 求5的阶乘算法用N-S图表示。,N-S 流 程 图 举 例,例2.13 判定闰年的算法用N-S图表示。,N-S 流 程 图 举 例,N-S流程图的优点： 比文字描述直观、形象、 易于理解 比传统流程图紧凑易画 整个算法由各个基本结构顺序组成，N-S图中的上下顺序就是执行时的顺序 用N-S图表示的算法都是结构化的算法,2.4.4 用N-S流程图表示算法,特点：流程的转移只存在于一个基本结构范围之内,思考：结构化的算法有何特点？,传统流程图和N-S图： 直观易懂，但画起来较费事，适合用来表示算法。 伪代码：书写方便 、格式紧凑，也比较好懂， 适合用来设计算法。,2.4.5 用伪代码表示算法,伪代码是指用介于自然语言和计算机语言之间的文字和符号来描述算法。,中英文混用：,用英文表示伪代码：,IF x is positive THEN print x ELSE print x,用汉字表示伪代码：,若 x为正 打印 x 否则 打印 x,IF x 为正 print x ELSE print x,2.4.5 用伪代码表示算法,用伪代码表示“打印x的绝对值”的算法,用伪代码表示求5! 算法如下：,开始 置t的初值为1 置i的初值为2 当i=5，执行下面操作： 使t=ti 使i=i+1 (循环体到此结束) 打印t的值 结束,2.4.5 用伪代码表示算法,BEGIN(算法开始) 1=t 2=i while it i+1=i print t END(算法结束),BEGIN(算法开始) 2000=y while yy END(算法结束),用伪代码表示判断闰年的算法如下：,伪代码写算法的优点： 书写格式自由，容易表达出设计者的思想； 算法容易修改； 容易写出结构化的算法。 伪代码写算法的缺点： 不如流程图直观； 可能会出现逻辑上的错误(如循环范围搞错等)。,2.4.5 用伪代码表示算法,结构化程序用高级语言表示的结构化的算法。 结构化程序的特点： 便于编写、阅读、修改和维护，程序的可靠性高； 强调程序设计风格和程序结构的规范化，提倡清晰的结构 结构化程序设计方法的基本思路： 将一个复杂的问题分解成若干个简单的问题来进行处理。,2.5 结构化程序设计方法,结构化程序设计方法： 自顶向下； 逐步细化； 模块化设计； 结构化编码。 完成一个任务有两种方法： 自顶向下，逐步细化； 自下而上，逐步积累。,（提倡使用此方法）,2.5 结构化程序设计方法,图2.36,图2.38,图2.39,将这三部分进一步细化为： A部分细化为图2.40。 B部分细化为图2.41。,图2.40 图2.41,图2.41B1处理的方法是：使x1=0，即哪个数不是素数， 就使 它等于0，以后把不等于零的数打印出来就是所求的素数表。 图2.41中的B3中的D部分细化为图2.42。 图2.42中的E部分细化为图2.43。 图2.43中的F部分细化为图2.44。因为首先要判断某一个xj 是否已被挖掉，如已被挖掉则不必考虑被xi除。 至此，B已不需要再分解了。 C部分细化为图2.45。 图2.45中的G部分进行细化，得图2.46。,图2.45 图2.46,图2.42 图2.43 图2.44,图2.47,什么是算法？结构化的算法有何特点？,思考题,作业,用N-S流程图表示教材课后习题2.4第（8）小题算法。,
展开阅读全文