计算机导论_算法简介_new_29001.ppt

什么是程序? ——“在数据的某些特定表示方式和结构的基础上对抽象算法的具体表述” 程序: 程序 = 数据结构 + 算法 【例2-6】 输入三个数，然后输出其中最大的数。 分析：首先要定义三个变量A、B、C，将三个数依次输入到A、B、C中，另外，再定义一个MAX保存最大数。首先把A与B比，大的数放在MAX中，再把MAX与C比，又把大的数放在MAX中，最后把MAX输出。 算法可以描述如下： 1）输入A、B、C； 2）A与B中大的一个放在MAX中； 3）把C与MAX中大的一个放入MAX中； 4）输出MAX，MAX即为最大数。 常用的算法表示有自然语言、流程图（传统流程图、结构化流程图）、伪代码、PAD图。 1、传统流程图：利用几何图形的框来代表各种不同性质的操作，用流程线来指示算法的执行方向。 1）常见的流程图符号： C、循环结构 当条件成立 A 直到条件成立 A 举例 【例2-6】 N—S图 输入A、B、C AB T F max?A max?B Cmax T F max?C 输出max 1985=y y不能被4整除 输出y“不是闰年” 是 否 y不能被100整除 是 否 输出y“是闰年” 否 是 y能被400整除 输出y“是闰年” 输出y“不是闰年” 【例2-3】 N—S图表示如下： y+1=y 直到y2500 算 法 算法概念 简单算法举例 算法表示 算 法 简 介 数据结构（data structure）：是操作的对象，在程序中指定的数据的类型和组织形式； 算法（algorithm）：对操作的描述，为解决一个问题而采取的方法和步骤。 著名计算机科学家沃思提出的公式 程序的灵魂—算法 广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。 方法1：1+2，+3，+4， 一直加到100 方法2：(100+1)+(99+2)+…+(50+51) = 50*101 对同一个问题，可有不同的解题方法和步骤 例： 求 2.1 算法的概念 计算的目的是对数据进行加工处理，以得到期望的结果。 其中算法是灵魂，解决“做什么”和“怎么做”的问题。 因此，认真考虑和设计数据结构和操作步骤（算法）就 一个程序设计任务的关键所在。 程序 = 数据结构 + 程序设计方法 + 语言工具和环境 + 算法 计算机程序是用某种程序设计语言描述的解题算法 程序 要求： 在高级语言的学习中，一方面要熟练掌握语言的 语法, 它是算法实现的基础, 另一方面必须认识到算法 的重要性，加强思维训练，以写出高质量的程序。 计算机算法 数值运算算法：求解数值 非数值运算算法：事务管理领域 算法的概念 ——为解决一个问题而采取的方法和步骤。 如：一个交响乐的乐谱就是一个乐曲的算法，菜谱… 程序设计步骤 问题定义——根据实际问题确定该由计算机完成的 任务，建立数学模型 算法设计——将任务分解成特定操作（承上启下） 算法表示——用形象的方法表达算法 程序编制——用选定的计算机语言编写程序 确定数据结构——根据原始数据以及输出形式，选 择合适的数据结构 语法检查/程序调试——静态/上机检查程序，纠错 文档编制——整理并写出文档资料 维护和再设计——处理程序运行过程中发现的新问题， 进行程序功能的扩充 例2.1: 求1×2×3×4×5 步骤1：先求1×2，得到结果2 步骤2：将步骤1得到的乘积2再乘以3，得到结果6 步骤3：将6再乘以4，得24 步骤4：将24再乘以5，得120 … … 如果要求1×2×…×1000，则要写999个步骤 2.2 简单算法举例 改进的算法： S1: 使p=1 S2: 使i=2 S3: 使p×i, 乘积仍然放在在变量p中，可表示为p×i→p S4: 使i的值+1，即i+1→i S5: 如果 i≤5, 转向S3； 否则，算法结束。 1×2×3×4×5 2 6 24 120… 被乘数: 初值1，积的结果用p 乘数分别为 i=2, 3, 4, 5 关键： p×i→p ； i+1→i 研判 i≤5 改进的算法： 如果计算100！只需将S5: