- 1、本文档共54页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
2.1 算法的概念 2.2 简单算法举例 2.3 算法的特性 2.4 怎样表示一个算法 ★ 2.5 结构化程序设计方法 ★ 程 序 包 括 对数据的描述 指定数据的类型、组织形式,即数据结构。 对操作的描述 即操作步骤,也称算法(algorithm)。 著名计算机科学家沃思(Nikilaus Wirth)提出: 程 序 设 计 包 括 采用某种程序设计方法 使用某种计算机语言工具 为解决问题而采取的方法和步骤,称为“算法”。 ——尽量采用简单、有效的算法。 计算机算法分两类: 数值算法(目的是求数值解) 有比较成熟的算法可供选用。 常常把这些算法汇编成册(写成程序形式),或者将这些程序存放在磁盘或磁带上,供用户调用。 算 法 一: 步骤1: 先求1×2,得到2。 步骤2: 将得到的2再乘以3,得到6。 步骤3: 将6再乘以4,得到24。 步骤4: 将24再乘以5,得到120。 算法虽然正确,但太繁琐。 每次都直接使用上一步骤的数值结果,不方便。应找到 一种通用的表示方法。 设两个变量:变量p代表被乘数,变量i代表乘数。 将每一步的乘积放在被乘数变量p中,算法改写如下: S1: 使p=1 S2: 使i=2 S3: 使p×i,乘积放在p中(p×i=p) S4: 使i的值加1(i+1 = i) S5: 若i不大于5,重新执行S3、S4和S5; 否则,算法结束。 如果题目改为: 求1×3×5×7×9×…×99。 则算法二只需作很少改动: S1: 1=p S2: 3=i S3: p×i=p S4: i+2=i S5: 若i≤100,返回S3; 否则,结束。 例2.3 判定2000—2500年中的每一年是否闰年,将结果输出。 闰 年 的 条 件 : ① 能被4整除,但不能被100整除的年份是闰年, 如1996年,2004年; ② 能被100整除,又能被400整除的年份是闰年, 如1600年、2000年。 不符合这两个条件的年份不是闰年。 设 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:当y≤2500时,转S2继续执行,如y>2500,算法停止。 图 2.1 一 个 算 法 应 具 有 以 下 特 点: 1.有穷性 一个算法应包含有限步操作。并且还应该“在合理的范围 之内”。究竟什么算“合理限度”,并无严格标准,由人们的 常识和需要而定。 2.确定性 算法中的每一个步骤都应当是确定的,而不应当是含糊的、 模棱两可的。 3.有零个或多个输入 所谓输入是指在执行算法时需要从外界取得的必要的信息。 一个算法也可以没有输入。 4.有一个或多个输出 算法的目的是为了求解,“解” 就是输出。没有输出的算法 是没有意义的。 5.有效性 算法中的每一个步骤都应能有效地执行,并得到确定的结 果。 自然语言表示 传统流程图表示 N-S流程图表示 伪代码表示 计算机语言表示(对算法的实现) 2.4.1 用自然语言表示算法 优点:通俗易懂 缺点:文字冗长, 容易出现“歧义性”。不方便描述包含分 支和循环的算法。 2.4.2 用流程图表示算法 是指用一些图框来表示算法中的各种操作。 美国国家标准化协会ANSI(American National Standard Institute)规定了一些常用的流程图符号(见图2.3)。 传统流程图的构成: 操作框 (起止、I/O、判断、处理、注释) 流程线 (箭头表示执行顺序) 文字说明 传统流程图的优缺点: 优点:直观,逻辑关系明确,易于理解。 缺点:占用篇幅多,表示复杂算法时,费时费力。 算法的重要性(4要素之一) 算法的特性(有穷、确定、有效、 0或多个I,1或多个O) 自然语言表示算法 通俗易懂 —— 不方便表示分支和循环 传统流程图表示算法 直观形象 —— 占用篇幅较多 1.传统流程图的弊端 对流程线的使用无限制,使流程毫无规律。如图2.13。 难以保证算法可靠性和可维护性。 那么,如何表示分支和循环这些非顺序的流程呢? 规定出几种基本结构,顺序排列组成一个算法。 图2.13 2. 三种基本结构 1966,Bohra和Jacopini提出以下三种结构: (1) 顺序结构,图2.14。 (2) 选择
文档评论(0)