您好,欢迎访问三七文档
当前位置:首页 > 电子/通信 > 综合/其它 > 第2章-算法---程序的灵魂-谭浩强第五版
22一个程序主要包括以下两方面的信息:(1)对数据的描述。在程序中要指定用到哪些数据以及这些数据的类型和数据的组织形式这就是数据结构(datastructure)(2)对操作的描述。即要求计算机进行操作的步骤也就是算法(algorithm)33数据是操作的对象操作的目的是对数据进行加工处理,以得到期望的结果著名计算机科学家沃思(NikiklausWirth)提出一个公式:算法+数据结构=程序44一个程序除了算法和数据结构这主要要素外,还应当采用结构化程序设计方法进行程序设计,并且用某一种计算机语言表示算法、数据结构、程序设计方法和语言工具是一个程序设计人员应具备的知识55算法是解决“做什么”和“怎么做”的问题程序中的操作语句,是算法的体现不了解算法就谈不上程序设计662.1什么是算法2.2简单的算法举例2.3算法的特性2.4怎样表示一个算法2.5结构化程序设计方法77广义地说,为解决一个问题而采取的方法和步骤,就称为“算法”对同一个问题,可以有不同的解题方法和步骤为了有效地进行解题,不仅需要保证算法正确,还要考虑算法的质量,选择合适的算法(正确性+效率)88计算机算法可分为两大类别:数值运算算法非数值运算算法数值运算的目的是求数值解非数值运算包括的面十分广泛,最常见的是用于事务管理领域99例2.1求1×2×3×4×5可以用最原始的方法进行:步骤1:先求1*2,得到结果2。步骤2:将步骤1得到的乘积2再乘以3,得到结果6。步骤3:将6再乘以4,得24。步骤4:将24再乘以5,得120。这就是最后的结果。例2.1求1×2×3×4×5×…×1000太繁琐1010改进的算法:设变量p为被乘数变量i为乘数用循环算法求结果1111S1:使p=1,或写成1pS2:使i=2,或写成2iS3:使p与i相乘,乘积仍放在变量p中,可表示为:p*ipS4:使i的值加1,即i+1iS5:如果i不大于5,返回重新执行S3;否则,算法结束最后得到p的值就是5!的值若是1000,求什么?1212S1:使p=1,或写成1pS2:使i=2,或写成2iS3:使p与i相乘,乘积仍放在变量p中,可表示为:p*ipS4:使i的值加1,即i+1iS5:如果i不大于5,返回重新执行S3;否则,算法结束最后得到p的值就是5!的值若求1×3×5×7×9×1133221111相当于i≦111313例2.3判定2000—2500年中的每一年是否闰年,并将结果输出。闰年的条件:(1)能被4整除,但不能被100整除的年份都是闰年,如2008、2012、2048年(2)能被400整除的年份是闰年,如2000年不符合这两个条件的年份不是闰年例如2009、2100年1414设year为被检测的年份。算法表示如下:S1:2000yearS2:若year不能被4整除,则输出year的值和“不是闰年”。然后转到S6S3:若year能被4整除,不能被100整除,则输出year的值和“是闰年”。然后转到S6S4:若year能被400整除,则输出year的值和“是闰年”,然后转到S6S5:其他情况输出year的值和“不是闰年”S6:year+1yearS7:当year≤2500时,转S2,否则停止1515year不能被4整除非闰年year被4整除,但不能被100整除闰年year被100整除,又能被400整除闰年其他非闰年逐渐缩小判断的范围1616思考:如果把第一项也作为循环的一部分,算法如何修改?思考:对变量定义应该遵循什么原则?见名知意(便于阅读,便于维护和修改)1717一个有效算法应该具有以下特点:(1)有穷性。一个算法应包含有限的操作步骤,而不能是无限的。(2)确定性。算法中的每一个步骤都应当是确定的,而不应当是含糊的、模棱两可的。1818一个有效算法应该具有以下特点:(3)有零个或多个输入。所谓输入是指在执行算法时需要从外界取得必要的信息。(4)有一个或多个输出。算法的目的是为了求解,“解”就是输出。没有输出的算法是没有意义的。(5)有效性。算法中的每一个步骤都应当能有效地执行,并得到确定的结果。1919常用的方法有:自然语言传统流程图结构化流程图伪代码……20202.4.1用自然语言表示算法2.4.2用流程图表示算法2.4.3三种基本结构和改进的流程图2.4.4用N-S流程图表示算法2.4.5用伪代码表示算法2.4.6用计算机语言表示算法2121流程图是用一些图框来表示各种操作用图形表示算法,直观形象,易于理解起止框输入输出框处理框判断框流程线连接点注释框x≧0Y……N……一个入口两个出口2222流程图是用一些图框来表示各种操作用图形表示算法,直观形象,易于理解起止框输入输出框处理框判断框流程线连接点注释框③①②①③②③位置不够防止交叉2323例2.6将例2.1的算法用流程图表示。求1×2×3×4×5如果需要将最后结果输出:1ti5开始2it*iti+1i结束NY2424例2.6将例2.1的算法用流程图表示。求1×2×3×4×5如果需要将最后结果输出:1t输出ti5开始2it*iti+1i结束NY2525例2.8例2.3判定闰年的算法用流程图表示。判定2000—2500年中的每一年是否闰年,将结果输出。2626NYN开始2000yearyear不能被4整除year是闰年year不能被100整除year+1yearyear2500结束Yyear不能被400整除year不是闰年year是闰年year不是闰年YNYN2727通过以上几个例子可以看出流程图是表示算法的较好的工具一个流程图包括以下几部分:(1)表示相应操作的框(2)带箭头的流程线(3)框内外必要的文字说明流程线不要忘记画箭头,否则难以判定各框的执行次序28281.传统流程图的弊端传统的流程图用流程线指出各框的执行顺序,对流程线的使用没有严格限制使用者可以毫不受限制地使流程随意地转来转去,使人难以理解算法的逻辑29292.三种基本结构(1)顺序结构AB3030(2)选择结构ABYpNAYpN3131(3)循环结构①当型循环结构AYp1NYx5N0x输出x的值x+1x输出1,2,3,4,53232(3)循环结构②直到型循环结构AYp2NYx≧5N0x输出x的值x+1x输出1,2,3,4,53333以上三种基本结构,有以下共同特点:(1)只有一个入口(2)只有一个出口▪一个判断框有两个出口▪一个选择结构只有一个出口(3)结构内的每一部分都有机会被执行到。也就是说,对每一个框来说,都应当有一条从入口到出口的路径通过它(4)结构内不存在“死循环”3434N-S流程图用以下的流程图符号:ABABYNpA当p1成立A直到p2成立顺序结构选择结构循环结构(当型)循环结构(直到型)3535例2.11将例2.1的求5!算法用N-S图表示。直到i51t输出t2it*iti+1i3636例2.13将例2.3判定闰年的算法用N-S图表示直到year25002000yearyear+1year否是year%4为0否是输出year非闰年year%100不为0year%400为0是否输出year非闰年输出year闰年输出year闰年3737一个结构化的算法是由一些基本结构顺序组成的在基本结构之间不存在向前或向后的跳转,流程的转移只存在于一个基本结构范围之内一个非结构化的算法可以用一个等价的结构化算法代替,其功能不变如果一个算法不能分解为若干个基本结构,则它必然不是一个结构化的算法3838结构化程序设计强调程序设计风格和程序结构的规范化,提倡清晰的结构。结构化程序设计方法的基本思路是:把一个复杂问题的求解过程分阶段进行,每个阶段处理的问题都控制在人们容易理解和处理的范围内。3939采取以下方法保证得到结构化的程序:(1)自顶向下;(2)逐步细化;(3)模块化设计;(4)结构化编码。
本文标题:第2章-算法---程序的灵魂-谭浩强第五版
链接地址:https://www.777doc.com/doc-3688390 .html