《chap2C语言复习》由会员分享，可在线阅读，更多相关《chap2C语言复习（20页珍藏版）》请在金锄头文库上搜索。
1、第2章 程序的灵魂算法,2.1算法的概念 2.2简单算法举例 2.3算法的特性 2.4怎样表示一个算法,一个程序应包括两个方面的内容： 数据的描述 操作步骤，即动作的描述 作为程序设计人员，必须认真考虑和设计数据结构和操作步骤（即算法）。因此，著名计算机科学家沃思（Niklaus Wirth）提出一个公式： 数据结构+算法=程序,实际上，一个程序除了以上两个主要要素之外，还应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言表示。因此，可以这样表示: 程序算法+数据结构+程序设计方法+语言工具和环境,算法：为解决一个问题而采取的方法和步骤称为“算法”。 对于同一个问题可以有不同的解题
2、方法和步骤，也就是有不同的算法。算法有优劣，一般而言，应当选择简单的、运算步骤少的，也就是运算快、内存开销小的算法（算法的时空效率）。,2.1 算法的概念,例2.1 求1 2 3 4 5。 例2.2 有50个学生,要求将他们之中成绩在80分以上的学号和成绩输出。 例2.3 判定2000-2500年中的每一年是否闰年,将结果输出。 例2.4 求1-1/2+1/3-1/4+1/99-1/100 例2.5 对一个大于或等于3的正整数,判断它是不是一个素数。,2.2 简单算法举例,例2.1：求1*2*3*4*5,方法一： s1：先求1*2，得到结果2。 s2：将步骤1得到的乘积2再乘以3，得到结果6。
3、 s3：将步骤2得到的乘积6再乘以4，得到结果24。 s4：将步骤3得到的乘积24再乘以5，得到最后结果120。,想一想：若要求10000！怎么做,方法二： s1：设p=1（p为乘数）。 s2：设i=2（i为被乘数）。 s3：使p*i，乘积仍放在变量p中，可表示为p=p*i。 s4：使i的值加1，可表示为i=i+1 。 s5：如果i不大于5，返回重新执行步骤3、4、5； 否则算法结束。最后求得的p的值就是5！的值。,想一想1：若要求10000！是否简单了,想一想2：若要求13591113如何修改上述算法,算法的5大特性: (1)有穷性：一个算法应当包含有限的步骤，而不能是无限的步骤；同时一个算
4、法应当在执行一定数量的步骤后，算法结束，不能死循环。 事实上“有穷性”往往指“在合理的范围之内”的有限步骤。,2.3 算法的特性,(2)确定性 算法中的每一个步骤都应当是确定的，而不是含糊的、模棱两可的。不应当产生歧义。特别是算法用自然语言描述时应当注意这点。 例如：“将成绩优秀的同学名单打印输出”就是有歧义的。,(3)有0个或多个输入 所谓输入是指算法执行时从外界获取必要信息。（外界是相对算法本身的，输入可以是人工键盘输入的数据，也可以是程序其它部分传递给算法的数据） 例如：不需要输入任何信息，就可以计算出5！；（0个输入） 例如：如果要计算两个整数的最大公约数，则需要输入2个整数m，n。,
5、(4)有1个或多个输出 算法的输出：算法得到的结果。算法必须有结果，没有结果的算法没有意义。（结果可以显示在屏幕上，也可以是将结果数据传递给程序的其它部分） (5)有效性 算法的每个步骤都应当能有效执行，并能得到确定的结果。例如：b=0，则执行a/b是不能有效执行的。,1 正确性。算法应当满足具体问题的需求。“正确”一词大体可分为四个层次： a. 程序不含语法错误。 b. 程序对几组输入数据能够得出满足规格说明要求的结果。 c. 程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果。 d. 程序对于一切合法的输入数据都能产生满足规格说明要求的结果。,算法设计的要
6、求,2 可读性。算法主要是为了人的阅读和交流，可读性好有助于人对算法的理解。 3 健壮性。当输入数据非法时，算法也能适当做出反应或进行处理，而不会产生莫名其妙的输出结果。 4 效率与低存储量需求。效率指算法执行的时间； 存储量需求，算法执行过程中所需要的最大存储空间。,算法设计的要求,为了表示一个算法，可以用不同的方法。常用的算法表示方法：自然语言，传统流程图，结构化流程图（N-S流程图），伪代码、PAD图、计算机语言等。 (重点：传统流程图，N-S流程图),2.4 怎样表示一个算法,用流程图表示算法 流程图表示算法：用一些图框表示各种操作，用箭头表示算法流程。用图形表示算法直观形象，易于理解
7、。 美国标准化协会ANSI规定了一些常用的流程图符号，已为世界各国程序工作者普遍采用。,起止框：表示算法的开始和结束。一般内部只写“开始”或“结束”,输入输出框：表示算法请求输入需要的数据或算法将某些结果输出。一般内部常常填写“输入”,“打印/显示”,处理框：表示算法的某个处理步骤，一般内部常常填写赋值操作。,菱形框（判断框）：作用主要是对一个给定条件进行判断，根据给定的条件是否成立来决定如何执行其后的操作。它有一个入口，两个出口。,流程线：表示算法程序的流向。,连接点：用于将画在不同地方的流程线连接起来。同一个编号的点是相互连接在一起的，实际上同一编号的点是同一个点，只是画不下才分开画。使用连接点，还可以避免流程线的交叉或过长，使流程图更加清晰。,注释框：注释框不是流程图中必须的部分，不反映流程和操作，它只是对流程图中某些框的操作做必要的补充说明，以帮助阅读流程图的人更好地理解流程图的作用。,3种基本结构及改进的流程图,三种基本结构有以下共同特点： 1 只有一个入口。 2 只有一个出口。 3 结构内的每一部分都有机会被执行到，且路径是唯一的。 4 结构内没有死循环。,N-S流程图,作业,2.4、2.5,
