程序的灵魂-算法.ppt

《程序的灵魂-算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章程序的灵魂－算法C程序设计第二章程序的灵魂－算法著名计算机科学家沃思提出一个公式：程序=数据结构+算法由于采用结构化方法进行程设,且用某一种计算机语言表示,因此还可表示为：程序=数据结构+算法+程序设计方法+语言工具和环境算法:是灵魂，是解决“做什么”、“怎么做”数据结构：是加工对象程序设计方法：程序应当采用的结构化程序设计方法语言：是工具。2.1算法的概念1.算法：为解决一个问题而采取的方法及步骤，就称为一个算法。对于同一问题有不同的解题的方法。例如：求1+2+3+…+100。为了有效进行解题,不仅确保算法正

2、确,还应考虑算法的质量,即选择合适的算法2.算法的分类：数值算法,非数值算法1)数值算法：目的是求数值解，(例如:求方程的根,函数定积分等)算法成熟，把算法汇编成册存放在磁盘上,供用户调用.(如：数学程序库)2)非数值算法：用于事物管理领域，(如:图书检索,人事管理)种类繁多，要求各异，难以规范化。2．2简单算法举例例2.1：求1*2*3*4*5方法一：步骤1：先求1*2，得到结果2。步骤2：将步骤1得到的乘积2再乘以3，得到结果6。步骤3：将步骤2得到的乘积6再乘以4，得到结果24。步骤4：将步骤3得到的乘积24再

3、乘以5，得到最后结果120。2．2简单算法举例（续）方法二：步骤1：设P=1（P为乘数）。步骤2：设I=2（I为被乘数）。步骤3：使P*I，乘积仍放在变量P中，可表示为P=P*I。步骤4：使I的值加1，可表示为I=I+1。步骤5：判断：如果I不大于5，返回重新执行步骤3、4、5；否则算法结束。最后求得的P的值就是5！的值。2．2简单算法举例（续）例2.2有50个学生，要求将他们之中成绩在80分以上者打印出来．用n表示学生学号,n1代表第一个学生学号,ni代表第i个学生的学号,g代表学生成绩,gi代表第i个学生成绩．算

4、法如下：S1:1=>iS2:若gi≥80则打印ni和gi，否则不打印S3:i+1=>iS4:若i≤50返回s2，否则算法结束2．3算法的特性（1）有穷性：一个算法应包含有限的操作步骤，而不能是无限的（2）确定性：算法中每一步的操作步骤都是确定的，不能模棱两可（3）有零个或多个输入：在执行算法时从外界取的必要的信息(4）有一个或多个输出：即算法的求解(5）有效性：算法中每一个步骤都应当能有效执行2.4怎样表示一个算法2.4.1用自然语言表示算法算法可以用自然语言描述的。自然语言就是人们日常使用的语言，可以是汉语、英语或

5、其它语言。用自然语言表示通俗易懂，但文字冗长，容易出现歧义。自然语言表示的含义往往不太严格，要根据上下文才能准确判断其含义。此外，用自然语言描述分支和循环的算法，不是很直观。因此，除了简单问题，一般不采用自然语言描述算法。2.4.2用流程图表示算法用流程图表示：流程图是一种传统的算法表示法，它利用特定的几何图形框来代表各种不同性质的操作，用流程线来指示算法的执行方向。由于它简单直观，所以应用广泛。2.4.2用流程图表示算法美国标准化协会ANSI规定了一些常用的流程图符号，已为世界各国程序工作者普遍采用注释框输入输出框

6、处理框判断框流程线连接点起止框一、举例例1：求5!，其算法流程图如右所示。例2：将50名学生中成绩在80分以上的学生的学号及成绩打印出来。2.4.3三种基本结构和改进的流程图1.传统流程图的弊端传统流程图采用流程线指出各框的执行顺序，对流程线的使用没有严格限制。因此，使用者可以不受限制地使流程转来转去，使流程图变得毫无规律。三种基本结构：人们对传统流程图进行改进，规定几种基本的结构，然后由这些基本结构按一定规律组成算法结构，整个算法结构是由上而下地将各个基本结构顺序排列起来1)顺序结构：是最简单的一种基本结构，如右

7、图所示。2)选择结构：根据给定的条件p选择执行A或者B。成立不成立成立不成立3)循环结构(1)当型(while)循环结构(2)直到型(Until)循环成立成立不成立不成立3.三种基本结构的共同特点1)只有一个入口2)只有一个出口3)结构内的每一个部分都有机会被执行4)结构内不存在“死循环”已经证明，任何复杂的问题都可以通过由以上三种基本结构顺序组成的算法结构来解决。2.4.4用N-S流程图表示算法将全部算法写在一个矩形框内，在矩形内还可包含其它从属于它的框N和S是两位美国学者的英文名的第一个字母N-S流程图用以下符号

8、表示：PABAB成立不成立A当p1成立A直到p1成立1.顺序结构2.选择结构3.循环结构N-S图的使用特点:1、比文字描述更加直观、形象，易于理解；2、比传统的流程图紧凑易画3、废除流程线，整个算法结构是由各个基本结构按顺序组成。N-S流程图的上下顺序就是执行时的顺序。N-S图表示的算法都是结构化的算法。2.4.4用N-S流程图表示算法(续)2