计算机导论算法简介.ppt

算 法 简 介 什么是程序什么是程序? ? “在数据的某些特定表示方式和结构的基础 上对抽象算法的具体表述” 程序程序: : 程序程序 = = 数据结构数据结构 + + 算法算法 数据结构（data structure）：是操作的对象是操作的对象， 在程序中指定的数据的类型和组织形式； 算法（algorithm）：对操作的描述对操作的描述，为解决一个 问题而采取的方法和步骤。 著名计算机科学家沃思提出的公式 程序的灵魂算法 广义地说，为解决一个问题而采取的方 法和步骤，就称为“算法”。 方法1：1+2，+3，+4， 一直加到100 方法2：(100+1)+(99+2)+(50+51) = 50*101 对同一个问题，可有不同的解题方法和步骤 例： 求 2.1 2.1 算法的概念算法的概念 计算的目的是对数据进行加工处理，以得到期望的结果。 其中算法是灵魂，解决算法是灵魂，解决“ “做什么做什么” ”和和“ “怎么做怎么做” ”的问题的问题。 因此，认真考虑和设计设计数据结构和操作步骤（算法）就 一个程序设计任务的关键所在。 程序 =数据结构数据结构 + + 程序设计方法程序设计方法 + + 语言工具和环境语言工具和环境 + + 算法算法 计算机程序是 用某种程序设 计语言描述的 解题算法 程序 要求： 在高级语言的学习中，一方面要熟练掌握语言的 语法语法, , 它是算法实现的基础, 另一方面必须认识到算法 算法 的重要性，加强思维训练，以写出高质量的程序。 计算机算法 数值运算算法：求解数值 非数值运算算法：事务管理领域 算法的概念算法的概念 为解决一个问题而采取的方法和步骤。 如：如：一个交响乐的乐谱就是一个乐曲的算法，菜谱 程序设计步骤程序设计步骤 问题定义根据实际问题确定该由计算机完成的 任务，建立数学模型 算法设计算法设计将任务分解成特定操作（承上启下）将任务分解成特定操作（承上启下） 算法表示用形象的方法表达算法 程序编制用选定的计算机语言编写程序 确定数据结构根据原始数据以及输出形式，选 择合适的数据结构 语法检查/程序调试静态/上机检查程序，纠错 文档编制整理并写出文档资料 维护和再设计处理程序运行过程中发现的新问题， 进行程序功能的扩充 例2.1: 求12345 步骤1：先求12，得到结果2 步骤2：将步骤1得到的乘积2再乘以3，得到结 果6 步骤3：将6再乘以4，得24 步骤4：将24再乘以5，得120 如果要求121000，则要写999个步 骤 2.2 2.2 简单算法举例简单算法举例 改进的算法：改进的算法： S1: 使p=1 S2: 使i=2 S3: 使pi, 乘积仍然放在在变量p中，可表示为pip S4: 使i的值+1，即i+1i S5: 如果 i5, 转向S3； 否则，算法结束。 12345 2 6 24 120 被乘数被乘数: : 初值1，积的结果用p 乘数分别为 i=2, 3, 4, 5 关键： pip ； i+1i 研判 i5 改进的算法：改进的算法： 如果计算100！只需将S5: 若 i5 改成 i100 即可。 如果该求1357911，算法也只需做很少的改动： S1: 1p S2: 3i S3: pip S4: i+2i S5: 若i11, 转向S3，否则，结束。 该算法不仅正确，而且是计算机较好的算法，因为计算 机是高速运算的自动机器，实现循环轻而易举。 如果再求 4914192429 呢？ S1: 4 4p S2: 9i S3: pip S4: i+5i S5: 若i29 ,转向S3，否则，结束。 问题： 如果，n表示学生学号，ni表示第 i个学生学号； g表示学生成绩， gi表示第 i个学生成绩； 则算法可表示如下： S1: 1i S2: 如果gi 80，则打印ni 和 gi。 S3: i+1i S4: 若i50, 转向S2，否则，结束。 【例2-2】有50个学生，要求将他们之中成绩在80分以 上者打印出来。 【例2-3】判定1985年2500年中的每一年是否闰年，将 结果输出。 1） 1985=y 2）若y能被4整除，但不能被100整除或y能被100 整除，又能被400整除，则输出y“是闰年”， 否则输出y“不是闰年” 3）下一年，即：y+1 = y 4) 当yy 3）下一年，即：y+1=y 4）当yB,则MAXA,否则 MAXB； 3）若CMAX，则 MAXC； 其中的2）、3）步无法直接转化为程序语句，可继续细化： 2.3 2.3 算法的特性算法的特性 有穷性：算法中每条指令的执行次数是有限的，算法中每条指令的执行次数是有限的， 执行每条指令的时间也是有限的。执行每条指令的时间也是有限的。 确定性：算法中的每一个步骤都应当是清晰的，算法中的每一个步骤都应当是清晰的， 无歧义的。无歧义的。 有零个或多个输入：输入是指在执行算法时需要输入是指在执行算法时需要 从外界取得必要的信息。从外界取得必要的信息。 有一个或多个输出：算法的目的是为了求解，算法的目的是为了求解，“ “解解 ” ” 就是输出。就是输出。 有效性：算法中的每一个步骤都应当能有效地执算法中的每一个步骤都应当能有效地执 行，并得到确定的结果行，并得到确定的结果 。 常用的算法表示有自然语言、流程图（传统流程图、结 构化流程图）、伪代码、PAD图。 1 1、传统流程图：、传统流程图：利用几何图形的框来代表各种不同性 质的操作，用流程线来指示算法的执行方向。 1）常见的流程图符号： 判断框输入输出框 执行框 连接框 起止框 2.42.4 算法的表示算法的表示 【例2-1】 流程图表示如下： 如果需要将最后结 果打印出来，可在 菱形框的下面加一 个输出框。 【例2-2】 流程图表示如下： 如果包括这个 输入数据的部 分，流程图为 【例2-3】 流程图表示如下： 不 【例2-4】 流程图表示如下： (-1)*signsign 开始 1sum sum+termsum 2deno 1sign sign*(1/deno)term deno+1deno deno100 结束 F Y 【例2-5】 流程图表示如下： 将例2.5判断素数的算法用流程图表示 【例2-5 】流程图表示如下： 输出MAX MAXC T MAXB MAXA FT AB 开始 输入A,B,C 结束 CMAX F 一个流程图包括： 1. 表示相应操作的框 2. 带箭头的流程线 3. 框内外必要的文字说明 2 2、改进的流程图、改进的流程图 1 1）算法的结构化描述）算法的结构化描述 经研究发现，任何复杂的算法都可以由顺序结构、选 择结构和循环结构这三种基本结构组成，因此构造一个 算法的时候，可以这三种结构作为基本单元，结构清晰 ，易于正确性验证，易于纠错，这种方法就是结构化方 法。 遵循这种方法的程序设计，就是结构化程序设计。 2 2）三种基本结构的流程图）三种基本结构的流程图 A B C A A、顺序结构顺序结构 B B、选择结构选择结构 条件 BA T F a） A 条件 T F b） 根据表达式的 值进行选择 ABMN p=p1p=p2p=pmp=pn 派生的多分支选择派生的多分支选择 三种基本结构的共同特点： l 只有一个入口； 只有一个出口； 结构内的每一部分都有机会被执行到； l 结构内不存在“死循环”。 C C、循环结构循环结构 a）while型 b）do - while 型 T 条件 A F F 条件 A T 3 3）用）用NSNS图描述算法图描述算法 NS图是由美国的I.Nassi和B.Shneiderman共同提出 的，其依据是既然任何算法都是由前面介绍的三种结构组 成，那么各基本结构之间的流程线就是多余的。NS图 也是算法的一种结构化描述方法。 NS图中，一个算法就是一个大矩形框，框内又包含 若干基本框。 三种基本结构的NS图描述如下： A A、顺序结构顺序结构 B B、条件结构条件结构 A B TF 条件 A B TF 条件 A C C、循环结构循环结构 当条件成立 A 直到条件成立 A 举例 【例2-6】 NS图 输入A、B、C AB TF maxA maxB Cmax TF maxC 输出max 1985=y y不能被4整除 输出 y“不 是闰 年” 是否 y不能被100整除 是否 输出 y“是 闰年” 否是 y能被400整除 输出 y“是 闰年” 输出 y“不 是闰 年” 【例2-3】 NS图表示如下： y+1=y 直到y2500 【例2-4 】 NS图表示如下： 1sum 2deno 1sign (-1)*signsign sign*(1/deno)term sum+termsum deno+1deno 直到deno100 3.PAD3.PAD（ProblemProblem AnalysisAnalysis Digram,HITACHI,1973Digram,HITACHI,1973） 3.PAD3.PAD（ProblemProblem AnalysisAnalysis Digram,HITACHI,1973Digram,HITACHI,1973） 读入a,b,c 计算 实根x1,x2 x=-c/b 实根x1= x2 虚根x1、 x2 根为任意值 无解 a0 b0 0 =0 c=0 结束 解一元二次方程 伪代码使用介于自然语言和计算机语言之间的文字和符 号来描述算法。 4 4、用伪代码、用伪代码(Pseudo Code)(Pseudo Code)描述算法描述算法 BEGIN sum= 0 t = 1 while t =100 sum=sum+t t = t+1 print t END 5 5、用计算机语言表示算法、用计算机语言表示算法 l 用计算机语言表示算法必须严格遵循所用语言的语法规则 【例2-1】求12345 用C+表示。 int main( ) int i,t; t=1; i=2; while(i=5) t=t*i; i=i+1; couttendl; return 0; 【例2-4】求级数的值。 int main() int sigh=1; float deno=2.0, sum=1.0, term; while(deno=100) sigh= -sigh; term= sigh/ deno; sum=sum+term; deno=deno+1; cout sumen